Given a grid where each entry is only 0 or 1, find the number of corner rectangles.
A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.
Example 1:
Input: grid = [[1, 0, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0], [1, 0, 1, 0, 1]] Output: 1 Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].
Example 2:
Input: grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]] Output: 9 Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.
Example 3:
Input: grid = [[1, 1, 1, 1]] Output: 0 Explanation: Rectangles must have four distinct corners.
Note:
- The number of rows and columns of
grid
will each be in the range[1, 200]
. - Each
grid[i][j]
will be either0
or1
. - The number of
1
s in the grid will be at most6000
.
A:
首先考虑的是遍历所有的top left, and bottom right corner. 对其每个pair, 看是否构成了 corner rectangle. ( LTE)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Solution { public: int countCornerRectangles(vector<vector<int>>& grid) { int m = grid.size(); if(m==0){ return 0; } int n = grid[0].size(); vector<pair<int,int>> V; for(int i=0;i<m ; i++){ for(int j =0; j<n; j++){ if(grid[i][j]) V.push_back(make_pair(i,j)); } } int res = 0; for(int i = 0;i<V.size();i++){ for(int j = i+1; j<V.size();j++){ if(V[i].first == V[j].first || V[i].second == V[j].second) continue; // make sure V[i] is on the left side of V[j] ( as it is guaranteed to be on the top of V[j]) if(V[i].second > V[j].second) continue; if(grid[V[i].first][V[j].second] && grid[V[j].first][V[i].second]){ ++res; } } } return res; } }; |
Mistakes:
没有检查 ,top left 的位置要在bottom right的左边。
***********************上面的超时了, 思路2 **********************
想象每一行,我们所有的 1, 两两可以组成一条线段。map成一个数字。 那么以后,如果想和他组成corner rectangle, 必须下面的row, 也有column 值组成这样的线段。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | class Solution { public: int countCornerRectangles(vector<vector<int>>& grid) { int m = grid.size(); if(m==0){ return 0; } int n = grid[0].size(); unordered_map<int,int> M; for(int i =0;i<m;i++){ // for each row, mapping possible line vector<int> V; for(int j=0;j<n; j++){ if(grid[i][j]){ V.push_back(j); } } // for each pair of 1 in current line for(int k = 0; k<V.size(); k++){ for(int t = k+1; t<V.size(); t++){ M[V[k] * 201 + V[t]]++; } } } int res = 0; for(auto& it : M){ res += it.second * (it.second - 1) / 2; } return res; } }; |
No comments:
Post a Comment