题目描述
给你一个 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
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | 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, row in enumerate(matrix):
for j, v in enumerate(row):
if v == 0:
continue
if i == 0 or j == 0:
f[i][j] = 1
else:
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1
ans += f[i][j]
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] f = new int[m][n];
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
continue;
}
if (i == 0 || j == 0) {
f[i][j] = 1;
} else {
f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1;
}
ans += f[i][j];
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int ans = 0;
vector<vector<int>> f(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) continue;
if (i == 0 || j == 0)
f[i][j] = 1;
else
f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
ans += f[i][j];
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | func countSquares(matrix [][]int) int {
m, n, ans := len(matrix), len(matrix[0]), 0
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
for i, row := range matrix {
for j, v := range row {
if v == 0 {
continue
}
if i == 0 || j == 0 {
f[i][j] = 1
} else {
f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1
}
ans += f[i][j]
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function countSquares(matrix: number[][]): number {
const [m, n] = [matrix.length, matrix[0].length];
const f = Array.from({ length: m }, () => Array(n));
const dfs = (i: number, j: number): number => {
if (i === m || j === n || !matrix[i][j]) return 0;
f[i][j] ??= 1 + Math.min(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1));
return f[i][j];
};
let ans = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
ans += dfs(i, j);
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function countSquares(matrix) {
const [m, n] = [matrix.length, matrix[0].length];
const f = Array.from({ length: m }, () => Array(n));
const dfs = (i, j) => {
if (i === m || j === n || !matrix[i][j]) return 0;
f[i][j] ??= 1 + Math.min(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1));
return f[i][j];
};
let ans = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
ans += dfs(i, j);
}
}
return ans;
}
|