加载中...
1277-统计全为 1 的正方形子矩阵(Count Square Submatrices with All Ones)
发表于:2021-12-03 | 分类: 中等
字数统计: 1.4k | 阅读时长: 6分钟 | 阅读量:

原文链接: https://leetcode-cn.com/problems/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 * 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

通过代码

高赞题解

方法一:递推

本题和 221. 最大正方形 非常类似,使用的方法也几乎相同。

我们用 f[i][j] 表示以 (i, j) 为右下角的正方形的最大边长,那么除此定义之外,f[i][j] = x 也表示以 (i, j) 为右下角的正方形的数目为 x(即边长为 1, 2, ..., x 的正方形各一个)。在计算出所有的 f[i][j] 后,我们将它们进行累加,就可以得到矩阵中正方形的数目。

我们尝试挖掘 f[i][j] 与相邻位置的关系来计算出 f[i][j] 的值。

1277-1.png{:width=600}

如上图所示,若对于位置 (i, j)f[i][j] = 4,我们将以 (i, j) 为右下角、边长为 4 的正方形涂上色,可以发现其左侧位置 (i, j - 1),上方位置 (i - 1, j) 和左上位置 (i - 1, j - 1) 均可以作为一个边长为 4 - 1 = 3 的正方形的右下角。也就是说,这些位置的的 f 值至少为 3,即:

f[i][j - 1] >= f[i][j] - 1
f[i - 1][j] >= f[i][j] - 1
f[i - 1][j - 1] >= f[i][j] - 1

将这三个不等式联立,可以得到:

$$
\min\big(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]\big) \geq f[i][j] - 1
$$

这是我们通过固定 f[i][j] 的值,判断其相邻位置与之的关系得到的不等式。同理,我们也可以固定 f[i][j] 相邻位置的值,得到另外的限制条件。

1277-2.png{:width=600}

如上图所示,假设 f[i][j - 1]f[i - 1][j]f[i - 1][j - 1] 中的最小值为 3,也就是说,(i, j - 1)(i - 1, j)(i - 1, j - 1) 均可以作为一个边长为 3 的正方形的右下角。我们将这些边长为 3 的正方形依次涂上色,可以发现,如果位置 (i, j) 的元素为 1,那么它可以作为一个边长为 4 的正方形的右下角,f 值至少为 4,即:

$$
f[i][j] \geq \min\big(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]\big) + 1
$$

将其与上一个不等式联立,可以得到:

$$
f[i][j] = \min\big(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]\big) + 1
$$

这样我们就得到了 f[i][j] 的递推式。此外还要考虑边界(i = 0j = 0)以及位置 (i, j) 的元素为 0 的情况,可以得到如下完整的递推式:

$$
f[i][j] =
\begin{cases}
\text{matrix}[i][j] & ,\text{if} i == 0 \text{or} j == 0 \
0 & ,\text{if
} \text{matrix[i][j]} == 0 \
\min\big(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]\big) + 1 & ,\text{otherwise}
\end{cases}
$$

我们按照行优先的顺序依次计算 f[i][j] 的值,就可以得到最终的答案。

[sol1]
class Solution { public: int countSquares(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector<vector<int>> f(m, vector<int>(n)); int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (i == 0 || j == 0) { f[i][j] = matrix[i][j]; } else if (matrix[i][j] == 0) { f[i][j] = 0; } else { f[i][j] = min(min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1; } ans += f[i][j]; } } return ans; } };
[sol1]
class Solution: def countSquares(self, matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) f = [[0] * n for _ in range(m)] ans = 0 for i in range(m): for j in range(n): if i == 0 or j == 0: f[i][j] = matrix[i][j] elif matrix[i][j] == 0: f[i][j] = 0 else: f[i][j] = min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1 ans += f[i][j] return ans

复杂度分析

  • 时间复杂度:$O(MN)$。

  • 空间复杂度:$O(MN)$。由于递推式中 f[i][j] 只与本行和上一行的若干个值有关,因此空间复杂度可以优化至 $O(N)$。

统计信息

通过次数 提交次数 AC比率
20012 27518 72.7%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
上一篇:
1276-不浪费原料的汉堡制作方案(Number of Burgers with No Waste of Ingredients)
下一篇:
1278-分割回文串 III(Palindrome Partitioning III)
本文目录
本文目录