leetcode-1277. 统计全为 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
    public int countSquares(int[][] matrix) {
        int n1 = matrix.length;
        int n2 = matrix[0].length;

        int[][] dp = new int[n1][n2];

        // 初始化dp
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < n1; i++) {
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        }
        for (int i = 1; i < n2; i++) {
            dp[0][i] = dp[0][i-1] + matrix[0][i];
        }

        for (int i = 1; i < n1; i++) {
            for (int j = 1; j < n2; j++) {
                if (matrix[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i-1][j-1];
                }else {
                    // 加入i,j 这个节点后能构成多少个矩形
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i-1][j-1] + judge(matrix, i, j);
                }

            }
        }

        return dp[n1 - 1][n2 - 1];
    }

    public int judge(int[][] matrix, int x, int y) {
        int count = 0;
        //最多能构成的矩形的长度
        int len = Math.min(x, y);
        for (int i = 0; i <= len; i++) {
            // 判断x-1， y-i 到y
            boolean b = true;
            for (int j = y-i; j <= y; j++) {
                if (matrix[x - i][j] == 0) {
                    b = false;
                    break;
                }
            }

            if (!b) {
                return count;
            }

            for (int j = x - i; j <= x; j++) {
                if (matrix[j][y-i] == 0) {
                    b = false;
                    break;
                }
            }

            if (!b) {
                return count;
            }

            if (b) {
                count ++;
            }
        }
        return count;
    }
}