LEETCODE 1504. Count Submatrices With All Ones 解题思路分析

题目大意:

统计全 1 子矩形

给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ,请你返回有多少个 子矩形 的元素全部都是 1 。

示例 1:

输入:mat = [[1,0,1],
            [1,1,0],
            [1,1,0]]
输出:13
解释:
6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2:

输入:mat = [[0,1,1,0],
            [0,1,1,1],
            [1,1,1,0]]
输出:24
解释:8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24

示例 3:

输入:mat = [[1,1,1,1,1,1]]
输出:21

示例 4:

输入:mat = [[1,0,1],[0,1,0],[1,0,1]]
输出:5

提示:

  • 1 <= rows <= 150
  • 1 <= columns <= 150
  • 0 <= mat[i][j] <= 1

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

解题思路分析:

我们之前讲过一道类似的题目,LEETCODE 1277. Count Square Submatrices with All Ones 解题思路分析,那一题统计的是正方形,而本题统计的是矩形,两者本质上没用区别。与上一题同理,我们可以采用DP动态规划或者前缀和的方式解题。本题我们以前缀和方式为例。

  1. 首先我们对矩阵进行数据初始化。即求出每一行以及每一列上的前缀和。
  2. 遍历矩阵每一个点(两层循环),并以该点最为起点(row, col),向右下方向画矩形(两层循环,分别循环矩形的宽width和高height),注意矩形范围不能越界。起始时width和height分别为0,即当前点自身是一个矩形。
  3. 当width扩大一格后,实际上是增加了(row, col+width)到(row+height, col+width)这一部分的面积(宽为1,高为height),我们通过前缀和数组求出该区域和是否等于height,如果等于,返回结果加一即可。
  4. height扩大一格的操作同理。

实现代码:

public int numSubmat(int[][] mat) {
    int[][] preSumRow=new int[mat.length][mat[0].length]; // 每一行前缀和
    int[][] preSumCol=new int[mat[0].length][mat.length]; // 每一列前缀和
    for(int r=0;r<mat.length;r++){
        for(int c=0;c<mat[0].length;c++){
            if(c==0) preSumRow[r][c]=mat[r][c];
            else preSumRow[r][c]=preSumRow[r][c-1]+mat[r][c];
        }
    }
    for(int c=0;c<mat[0].length;c++){
        for(int r=0;r<mat.length;r++){
            if(r==0) preSumCol[c][r]=mat[r][c];
            else preSumCol[c][r]=preSumCol[c][r-1]+mat[r][c];
        }
    }
    int res=0;
    for(int r=0;r<mat.length;r++){ // 循环每一点
        for(int c=0;c<mat[0].length;c++){
            for(int rl=0;rl+r<mat.length;rl++){ // 以当前点为顶点,向下扩大一格
                for(int cl=0;cl+c<mat[0].length;cl++){ // 以当前点为顶点,向右扩大一格
                    int row=r+rl,col=c+cl;
                    // 通过前缀和数组求出新增区域面积,如果该面积与新增面积相同,代表区域内都是1
                    if((c==0&&preSumRow[row][col]==cl+1||c>0&&preSumRow[row][col]-preSumRow[row][c-1]==cl+1)
                      &&(r==0&&preSumCol[col][row]==rl+1||r>0&&preSumCol[col][row]-preSumCol[col][r-1]==rl+1)){
                        res++; // 返回结果加一
                    }else{
                        break;
                    }
                }
            }
        }
    }
    return res;
}

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

Runtime: 80 ms, faster than 16.67% of Java online submissions for Count Submatrices With All Ones.

Memory Usage: 39.8 MB, less than 100.00% of Java online submissions for Count Submatrices With All Ones.

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

发表评论

您的电子邮箱地址不会被公开。