# [LeetCode] 750. Number Of Corner Rectangles 边角矩形的数量

2021年09月15日 阅读数：1

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.html

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.java

Example 1:python

```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:post

```Input: grid =
[[1, 1, 1, 1]]
Output: 0
Explanation: Rectangles must have four distinct corners. ```

Note:优化

1. The number of rows and columns of `grid` will each be in the range `[1, 200]`.
2. Each `grid[i][j]` will be either `0` or `1`.
3. The number of `1`s in the grid will be at most `6000`.

Java:htm

```class Solution {
public int countCornerRectangles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int ans = 0;
for (int x = 0; x < m; x++) {
for (int y = x + 1; y < m; y++) {
int cnt = 0;
for (int z = 0; z < n; z++) {
if (grid[x][z] == 1 && grid[y][z] == 1) {
cnt++;
}
}
ans += cnt * (cnt - 1) / 2;
}
}
return ans;
}
}　　```

Python:

```def countCornerRectangles(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n = len(grid)
m = len(grid[0])
res = 0
for i in xrange(n):
for j in xrange(i + 1, n):
np = 0
for k in xrange(m):
if grid[i][k] and grid[j][k]:
np += 1

res += np * (np - 1) / 2
return res　```

Python:

```# Time:  O(n * m^2), n is the number of rows with 1s, m is the number of cols with 1s
# Space: O(n * m)
class Solution(object):
def countCornerRectangles(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
rows = [[c for c, val in enumerate(row) if val]
for row in grid]
result = 0
for i in xrange(len(rows)):
lookup = set(rows[i])
for j in xrange(i):
count = sum(1 for c in rows[j] if c in lookup)
result += count*(count-1)/2
return result
```

C++: 暴力，很差

```class Solution {
public:
int countCornerRectangles(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), res = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) continue;
for (int h = 1; h < m - i; ++h) {
if (grid[i + h][j] == 0) continue;
for (int w = 1; w < n - j; ++w) {
if (grid[i][j + w] == 1 && grid[i + h][j + w] == 1) ++res;
}
}
}
}
return res;
}
};　　```

C++:

```// Time:  O(m^2 * n), m is the number of rows with 1s, n is the number of cols with 1s
// Space: O(m * n)
class Solution {
public:
int countCornerRectangles(vector<vector<int>>& grid) {
vector<vector<int>> rows;
for (int i = 0; i < grid.size(); ++i) {
vector<int> row;
for (int j = 0; j < grid[i].size(); ++j) {
if (grid[i][j]) {
row.emplace_back(j);
}
}
if (!row.empty()) {
rows.emplace_back(move(row));
}
}
int result = 0;
for (int i = 0; i < rows.size(); ++i) {
unordered_set<int> lookup(rows[i].begin(), rows[i].end());
for (int j = 0; j < i; ++j) {
int count = 0;
for (const auto& c : rows[j]) {
count += lookup.count(c);
}
result += count * (count - 1) / 2;
}
}
return result;
}
};
```

C++:

```class Solution {
public:
int countCornerRectangles(vector<vector<int>>& grid) {
int ans = 0;
for (int r1 = 0; r1 + 1 < grid.size(); ++r1) {
for (int r2 = r1 + 1; r2 < grid.size(); ++r2) {
int counter = 0;
for (int c = 0; c < grid[0].size(); ++c) {
if (grid[r1][c] == 1 && grid[r2][c] == 1) {
++counter;
}
}
ans += counter * (counter - 1) / 2;
}
}
return ans;
}
};
```