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.

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

LEETCODE 1277. Count Square Submatrices with All Ones 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 1504. Count Submatrices With All Ones 解题思路分析 - 関小君刷题记関小君刷题记

发表评论

邮箱地址不会被公开。