class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
}
};
1277. 统计全为 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 <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1原站题解
golang 解法, 执行用时: 56 ms, 内存消耗: 6.9 MB, 提交时间: 2022-11-16 11:07:58
func countSquares(matrix [][]int) (res int) {
// m := make(map[int]int)
m := make([]int, 301)
for i:=0; i<len(matrix); i++{
for j:=0; j<len(matrix[i]); j++{
// 求出当前状态的能组成的正方体的大小
if i!=0 && j!=0 && matrix[i][j] == 1{
matrix[i][j] = min(matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1])+1
}
// map记录对应大小的正方体的个数
if matrix[i][j]>0{
m[matrix[i][j]]++
}
}
}
for i,v :=range m{
if v!=0{
res += i*v
}
}
return res
}
func min(a,b,c int) int{
if c<a {a = c}
if a<b{return a}
return b
}
python3 解法, 执行用时: 180 ms, 内存消耗: 16.5 MB, 提交时间: 2022-11-16 11:06:08
'''
我们用 f[i][j] 表示以 (i, j) 为右下角的正方形的最大边长，那么除此定义之外，
f[i][j] = x 也表示以 (i, j) 为右下角的正方形的数目为 x（即边长为 1, 2, ..., x 的正方形各一个）。
在计算出所有的 f[i][j] 后，我们将它们进行累加，就可以得到矩阵中正方形的数目。
'''
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