leetcode 750

问题

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:

1
2
3
4
5
6
7
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:

1
2
3
4
5
6
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:

1
2
3
4
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 1s in the grid will be at most 6000.

分析-方法1

遍历每一行，再在每一行中，遍历判断每一对可以作为 corner rectangle 的底部两个“顶点”的情况下能够产生多少个 corner rectangle ，结果累计到答案中即可。代码中 $mp[i][j]$ 表示已经遍历过的行中，行数相同的情况下，第 $i$ 列和第 $j$ 列同时为 1 的情况的个数。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countCornerRectangles(vector<vector<int>>& grid) {
        // unordered_map<int, int> mp;
        int mp[201][201] = {};
        int ans = 0;
        int m = grid.size();
        int n = m==0? 0: grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) if (grid[i][j] == 1) {
                for (int k = j+1; k < n; ++k) if (grid[i][k] == 1) {
                    ans += mp[j][k];
                    mp[j][k]++;
                 }
            }
        }
        return ans;
    }
};

分析-方法2

先确定“上底”和“下底”，然后再这个“上底”和“下底”确定的情况下，能够画多少条“高”。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countCornerRectangles(vector<vector<int>>& grid) {
        int ans = 0;
        int m = grid.size();
        int n = m==0? 0: grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = i+1; j < m; ++j) {
                int counter = 0;
                for (int k = 0; k < n; ++k) {
                    if (grid[i][k] == 1 && grid[j][k] == 1)
                        counter++;
                }
                ans += counter*(counter-1)/2;
            }
        }
        return ans;
    }
};