LEETCODE 1277. Count Square Submatrices with All Ones 解题思路分析

题目大意：

统计全为 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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1277

解题思路分析：

解法一：动态规划

这又是一道动态规划DP，或者说是递归加记忆数组的题目。先不考虑0和1的限制，单纯考虑矩阵中的任意一点，以它为顶点向右下方能够构建出正方形的个数取决于，它到底边和右边的最小长度。假如最小长度为3的话，那么当前点就可以构建出3个正方形，边长分别为1，2和3。不过本题要求，不仅要构建出正方形，并且正方形内所有点都必须为1，这就需要使用到动态规划来思考问题。

对于任意一点，如果它的值为0，那么肯定无法构建出合理的正方形。如果为1时，先看它能构建出的所有格子都为1的最大正方形边长是多少，这个最大边长取决于当前点下方一格，右方一格，以及右下方一格能够构建出的合理正方形的最大边长，三个边长的最小值加一即为当前格子能够构建的最大边长。这样描述可能比较抽象，我们举个例子，看下图：

比如当前点是坐标为(1, 1)的浅蓝色格子，通过肉眼我们可以看出，当前格子下方(1, 2)能够构建出的最大合理正方形是红色边框区域，其边长为2，而当前格子右侧格子(2, 1)能画出的最大边长也为2，即深蓝色边框区域。最后右下点(2, 2)的最大边长为绿色区域，边长是3。因此，从(1, 1)点开始向右下方能构建出的最大正方形边长应该是min(2, 2, 3)+1，即3 (背景为黄色的区域)。

综上所述，在求某一点能够构建出的最大正方形边长时，我们可以从当前点开始递归，如果当前点为0，直接返回0，如果当前点是1，则：

f(x, y) = min(f(x+1, y), f(x, y+1), f(x+1, y+1))+1;

递归的终止条件为，当前点如果是在底边或者右边时，由于最多只能构建出1 x 1的正方形（没有足够的空间构建出更大的正方形），当前点的返回值应该为arr[x][y]。

最后，我们以每一个点作为起点计算出，以该点向右下能够构建出的最大正方形边长，所有结果的和即是返回结果。

实现代码：

Integer[][] memo; // 记忆数组
public int countSquares(int[][] matrix) {
    memo=new Integer[matrix.length][matrix[0].length];
    int res=0; // 返回结果
    // 遍历所有点
    // 求出以每一点为顶点向右下方能画出的最大正方形边长
    for(int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            // 求和
            res+=help(matrix,i,j);
        }
    }
    return res;
}
int help(int[][] matrix, int r, int c){
    // 如果记忆数组不为空，直接返回
    if(memo[r][c]!=null) return memo[r][c];
    // 如果当前点在下边或者右边时，返回当前值
    if(r==matrix.length-1||c==matrix[0].length-1){
        return matrix[r][c];
    }
    // 如果当前点为0，直接返回0
    if(matrix[r][c]==0) return 0;
    // 下方格子能画出的最大正方形边长
    int bottom = help(matrix, r+1,c);
    // 右方格子能画出的最大正方形边长
    int right = help(matrix, r,c+1);
    // 右下方格子能画出的最大正方形边长
    int bottomRight = help(matrix, r+1,c+1);
    // 三者的最小值加一为当前返回结果
    int res=Math.min(bottom,Math.min(right,bottomRight))+1;
    memo[r][c]=res; // 将结果存入记忆数组
    return res;
}

本题解法执行时间为12ms。

Runtime: 12 ms, faster than 47.17% of Java online submissions for Count Square Submatrices with All Ones.

Memory Usage: 58.2 MB, less than 100.00% of Java online submissions for Count Square Submatrices with All Ones.

---

解法二：前缀和

其实本题还有一个更加容易思考的解题思路。即使用前缀和来解题。我们需要首先对数组进行预处理，即统计出每一行以及每一列上的前缀和。统计前缀和的目的是，当我们想确定某一行或者某一列上某个区间内是否全是1，那么我们只要通过该行或者列的前缀和数组计算出该区间的和，然后查看该区间和是否等于区间长度即可。这一点会在接下来的思路中使用到。

解题时我们依旧使用二层循环来遍历数组中每一个点，如果当前点是0，跳过。如果当前点是1，返回结果加一（当前点自身是一个合理子矩阵），同时，我们以该点为起点，向右下方向各扩大一格（变为2*2的子矩阵），继续查看当前子矩阵是否都是1，此时我们无须重新遍历子矩阵中每一个点，只查看新增加的部分是否都是1即可。实际上新增的部分是当前子矩阵的最下一行以及最右一列，如果用代码来表示：

设k为从起点开始增加的边长。

新增行起始位置：matrix[当前行+k][当前列]
新增行终点位置：matrix[当前行+k][当前列+k]

新增列起始位置：matrix[当前行][当前列+k]
新增列终点位置：matrix[当前行+k][当前列+k]

我们使用前缀和数组可以轻松的计算出上述两个区间内1的个数，如果该个数等于区间长度，那么当前子矩阵为一个合理矩阵，返回结果加一，同时边长加一继续扩大子矩阵范围。反之，当前矩阵不合理，无须再继续扩大，退出当前循环，返回上层循环，继续查看矩阵中下一个点。重复上述过程，直到循环完矩阵中每一个点。

实现代码：

public int countSquares(int[][] matrix) {
    // 每一行前缀和
    int[][] presumPerRow=new int[matrix.length][matrix[0].length];
    // 每一列前缀和
    int[][] presumPerCol=new int[matrix.length][matrix[0].length];
    for(int r=0;r<matrix.length;r++){
        for(int c=0;c<matrix[0].length;c++){
            if(c==0)presumPerRow[r][c]=matrix[r][c];
            else presumPerRow[r][c]=presumPerRow[r][c-1]+matrix[r][c];
        }
    }
    for(int c=0;c<matrix[0].length;c++){
        for(int r=0;r<matrix.length;r++){
            if(r==0)presumPerCol[r][c]=matrix[r][c];
            else presumPerCol[r][c]=presumPerCol[r-1][c]+matrix[r][c];
        }
    }
    int res=0; // 返回结果
    // 循环每一点
    for(int r=0;r<matrix.length;r++){
        for(int c=0;c<matrix[0].length;c++){
            // 当前点为0，跳过
            if(matrix[r][c]==0) continue;
            // 返回结果加一
            res++;
            // 以当前点为顶点向右下不断扩大边长。（注意不要越界）
            for(int k=1;r+k<matrix.length&&c+k<matrix[0].length;k++){
                int n1=presumPerRow[r+k][c+k]-(c==0?0:presumPerRow[r+k][c-1]);
                if(n1!=k+1)break;
                int n2=presumPerCol[r+k][c+k]-(r==0?0:presumPerCol[r-1][c+k]);
                if(n2!=k+1)break;
                res++;
            }
        }
    }
    return res;
}

本题解法执行时间为7ms。

Runtime: 7 ms, faster than 33.85% of Java online submissions for Count Square Submatrices with All Ones.

Memory Usage: 49.3 MB, less than 100.00% of Java online submissions for Count Square Submatrices with All Ones.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1277-count-square-submatrices-with-all-ones-解题思路分析/