1277. Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix =
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.

Constraints:

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

这道题说是给了一个 m by n 大小的二维数组,只有0和1,现在问有多少个只包含1的正方形子数组。这里需要满足两个条件,一个是正方形的子数组,另一个是都必须包含1。既然都是包含1,而且还是正方形,那么就可以快速的知道这个正方形子数组的数字之和,正好等于该正方形边长的平方,那么一个比较直接的检测方法就是遍历每个正方形子数组,检查其数字之和是否为边长的平方。为了能快速的获得任意一个子数组的数字之和,可以建立累加和数组,在一维子数组问题中这个很常见,二维数组中其实也差不了太多,只不过更新的时候稍微麻烦一点。这里的二维累加和数组行和列数各多一个,可以防止越界,更新的方法就是原数组的数字加上累加和数组对应位置的左边,上边,和左上边的数字之和。更新好了累加和数组之和,就可以来找正方形子数组了,遍历原数组中的所有位置,当作正方形的左上顶点,然后在可允许的范围内,遍历正方形的长度,然后根据累加和数组快速计算出子数组数字之和,跟正方形边长的平方比较,若相等,则结果 res 自增1即可,参见代码如下:

解法一:

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size(), res = 0;
        vector<vector<int>> sums(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                sums[i][j] = matrix[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = 0; i + k <= m && j + k <= n; ++k) {
                    if (sums[i + k][j + k] - sums[i - 1][j + k] - sums[i + k][j - 1] + sums[i - 1][j - 1] == (k + 1) * (k + 1)) {
                        ++res;
                    }
                }
            }
        }
        return res;
    }
};

上面的方法虽然可以通过建立累加和数组来提高效率,但仍是立方级的时间复杂度。这里可以使用动态规划 Dynamic Programming 来降到平方级的复杂度,这里定义一个二维 dp 数组,其中 dp[i][j] 表示以 (i, j) 为右下顶点的最大的正方形子数组的边长,同时正好也是以 (i, j) 为右下顶点的正方形子数组的个数,这个不理解的童鞋可以举些例子观察一下。那么只要求出每个位置的 dp 值,然后都加起来,就是题目要求的所有的正方形子数组的个数。dp 数组可以直接就初始化为 matrix,因为每个为1的点,正好也是一个边长为1的正方形子数组,满足 dp 的定义。然后就要进行状态转移了,更新的位置必须要是 dp 值大于0的地方,并且不能是第一行或者第一列,不然正方形边长不可能超过1。更新的状态转移方程就是看当前位置的左边,上边,和左上边三个位置中的最小值,并加上1。若那三个位置的值都不为0的话,就保证了必然有大于1的正方形存在,就算最小值为0,加上1后,至少 dp 的值不会改变(因为初始化时赋值为1了),每次更新完 dp 值后,将其加到结果 res 中即可,参见代码如下:

解法二:

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size(), res = 0;
        vector<vector<int>> dp = matrix;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dp[i][j] > 0 && i > 0 && j > 0) {
                    dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                }
                res += dp[i][j];
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1277

类似题目:

Minimum Cost Homecoming of a Robot in a Grid

Count Fertile Pyramids in a Land

参考资料:

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/441306/JavaC%2B%2BPython-DP-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation