数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中统计全为 1 的正方形子矩阵
假设我们有一个大小为 m x n 的二进制矩阵。我们需要统计所有元素都为 1 的正方形子矩阵的数量。例如，如果矩阵如下所示：
| 0 | 1 | 1 | 1 |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 |
那么将有 15 个正方形。10 个单个元素的正方形，4 个包含四个元素的正方形，以及 1 个包含九个元素的正方形。
为了解决这个问题，我们将遵循以下步骤：
- 设置 ans := 0，n := 行数，m := 列数
- 对于 i 的范围从 0 到 m – 1
- ans := ans + matrix[n – 1, i]
- 对于 i 的范围从 0 到 n – 1
- ans := ans + matrix[i, m – 1]
- ans := ans – matrix[n – 1, m - 1]
- 对于 i 的范围从 n – 2 逆序到 0
- 对于 j 的范围从 m – 2 逆序到 0
- 如果 matrix[i, j] = 1，则
- matrix[i, j] := 1 + min(matrix[i + 1, j + 1], matrix[i, j + 1], matrix[i + 1, j])
- 否则 matrix[i,j] := 0
- ans := ans + matrix[i, j]
- 如果 matrix[i, j] = 1，则
- 对于 j 的范围从 m – 2 逆序到 0
- 返回 ans
让我们看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int ans = 0;
int n = matrix.size();
int m = matrix[0].size();
for(int i = 0; i < m; i++)ans += matrix[n-1][i];
for(int i = 0; i < n; i++)ans += matrix[i][m-1];
ans -= matrix[n-1][m-1];
for(int i = n - 2;i >= 0; i--){
for(int j = m-2 ;j >= 0; j--){
matrix[i][j] = matrix[i][j] == 1? 1 + min({matrix[i+1][j+1],matrix[i] [j+1],matrix[i+1][j]}) : 0;
ans += matrix[i][j];
}
}
return ans;
}
};
main(){
vector<vector<int>> v = {{0,1,1,1},{1,1,1,1},{0,1,1,1}};
Solution ob;
cout << (ob.countSquares(v));
}输入
[[0,1,1,1], [1,1,1,1], [0,1,1,1]]
输出
15
更新于: 2020年5月2日
137 次浏览
广告