LeetCode_动态规划_中等_1277.统计全为 1 的正方形子矩阵

水深无声 2023-10-06 22:44 10阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个 m \* n 的矩阵，矩阵中的元素不是 0 就是 1，**请你统计并返回其中完全由 1 组成的正方形子矩阵的个数。**

**示例 1：**

输入：matrix =
    [
      [0,1,1,1],
      [1,1,1,1],
      [0,1,1,1]
    ]
    输出：15
    解释： 
    边长为 1 的正方形有 10 个。
    边长为 2 的正方形有 4 个。
    边长为 3 的正方形有 1 个。
    正方形的总数 = 10 + 4 + 1 = 15.

**示例 2：**

输入：matrix = 
    [
      [1,0,1],
      [1,1,0],
      [1,1,0]
    ]
    输出：7
    解释：
    边长为 1 的正方形有 6 个。 
    边长为 2 的正方形有 1 个。
    正方形的总数 = 6 + 1 = 7.

**提示：**  
1 <= arr.length <= 300  
1 <= arr\[0\].length <= 300  
0 <= arr\[i\]\[j\] <= 1

## 2.思路 ##

（1）暴力穷举法  
此题与[LeetCode\_动态规划\_中等\_221. 最大正方形][LeetCode_221.]这题类似，只不过本题需要求正方形所有可能边长的情况。使用暴力穷举法时，用变量 sum 来累加每一个符合条件正方形个数即可。

（2）动态规划

相关题目：  
[LeetCode\_动态规划\_中等\_221.最大正方形][LeetCode_221.]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int countSquares(int[][] matrix) {
        
            int m = matrix.length;
            int n = matrix[0].length;
            int sum = 0;
            //正方形的最大边长为Math.min(m, n)
            int edge = Math.min(m, n);
            //从边长为 edge 的正方形开始穷举
            for (int i = edge; i >= 1; i--) {
        
            	//遍历边长为 i 的正方形在 matrix 中的所有位置
                for (int j = i; j <= m; j++) {
        
                    for (int k = i; k <= n; k++) {
        
                        if (isSquare(matrix, j - i, k - i, j - 1, k - 1)) {
        
                            //找到只包含 '1' 的正方形，其边长为 i
                            sum++;
                        }
                    }
                }
            }
            return sum;
        }
    
        //判断 matrix 中左上角顶点坐标为(x1,y1)、右下角顶点坐标为(x2,y2)的正方形是否只包含‘1’
        public boolean isSquare(int[][] matrix, int x1, int y1, int x2, int y2) {
        
            for (int i = x1; i <= x2; i++) {
        
                for (int j = y1; j <= y2; j++) {
        
                    if (matrix[i][j] == 0) {
        
                        return false;
                    }
                }
            }
            return true;
        }
    }

//思路2————动态规划
    public int countSquares(int[][] matrix) {
        
        int m = matrix.length;
        int n = matrix[0].length;
        /*
        	dp[i][j]:表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值
        	此外，它表示以 (i, j) 为右下角的正方形的数目为 x（即边长为 1, 2, ..., x 的正方形各一个）
    	*/
        int[][] dp = new int[m][n];
        //sum 记录完全由 1 组成的正方形子矩阵的个数，初始值为 0
        int sum = 0;
        for (int i = 0; i < m; i++) {
        
            for (int j = 0; j < n; j++) {
        
                if (matrix[i][j] == 1) {
        
                    if (i == 0 || j == 0) {
        
                        dp[i][j] = 1;
                    } else {
        
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                }
                //如果 matrix[i][j] == '0'，则当前位置不可能在由 1 组成的正方形中，所以 dp[i][j] = 0，即 dp 数组初始的默认值
                sum += dp[i][j];
            }
        }
        return sum;
    }

[LeetCode_221.]: https://blog.csdn.net/weixin_43004044/article/details/124857619