leetcode 1277

问题

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

分析

思路1: 对于每一个坐标求以 (i, j) 为右下角坐标，是否存在大小为k的正方形，k从1递增直到遇到第一个不满足条件的正方形或者正方形超出矩阵范围。时间复杂度 $O(n^3)$。

思路2: $dp[i][j]$ 表示以 $A[i][j]$ 为右下角的最大全1的正方形的边长，同时它要求表示以$A[i][j]$ 为右下角的所有全1的正方形的数量。于是，我们有状态转移方程:
$$
dp[i][j] = min(dp[i-1][j-1], \;dp[i][j-1],\;dp[i-1][j]) + 1
$$
可以证明，假设 $dp[i][j] == k$ ，那么 $min(dp[i][j-1], \; dp[i][j-1],\; dp[i-1][j]) $ 至少为 $k-1$。如果当$min(dp[i][j-1], \; dp[i][j-1],\; dp[i-1][j])$ 为 $k-1$ 时，那么 $dp[i][j] == k$ 于是可以证明上述状态转移方程是成立的。

代码1

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
32
33
34
35
36
37
38
39
40
41
42
43
44
// O(n^3)
class Solution {
public:
    int sumRange(vector<vector<int>>& matrix, int x0, int y0, int x1, int y1) {
        int ans = matrix[x1][y1];
        if (y0 > 0) ans -= matrix[x1][y0-1];
        if (x0 > 0) ans -= matrix[x0-1][y1];
        if (x0>0 && y0>0) ans += matrix[x0-1][y0-1];
        return ans;
    }
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        for (int j = 1; j < n; ++j) {
            matrix[0][j] += matrix[0][j-1];
        }
        for (int i = 1; i < m; ++i) {
            matrix[i][0] += matrix[i-1][0];
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                matrix[i][j] += matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1];
            }
        }
        
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 1, x0 = i, y0 = j;
                     x0 >= 0 && y0 >= 0;
                     x0--, y0--, k++) {
                    if (sumRange(matrix, x0, y0, i, j) == k*k) {
                        ans++;
                    } else {
                        break;
                    }
                }
            }
        }
        return ans;
        
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// O(n^2)
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] != 0 && i != 0 && j != 0)
                    matrix[i][j] = 1+ min(matrix[i-1][j-1], 
                        min(matrix[i-1][j], matrix[i][j-1]));
                ans += matrix[i][j];
            }
        }
        return ans;
    }
};