数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 程序：计算给定矩阵中 1 的正方形子矩阵的数量
假设我们有一个二维二进制矩阵，我们需要找到所有元素都为 1 的子矩阵的总数。
所以，如果输入是这样的
| 1 | 1 | 0 |
| 1 | 1 | 0 |
| 0 | 0 | 1 |
那么输出将是 10，因为有五个 1 x 1 矩阵，两个 2 x 1 矩阵，两个 1 x 2 矩阵，以及一个 2 x 2 矩阵。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 getAns()，它将接收一个数组 a，
ret := 0
n := a 的大小
定义一个大小为 n 的数组 v
定义一个栈 st
for 初始化 i := 0，当 i < a 的大小，更新（i 增加 1），执行：
while (st 不为空且 a[st 的栈顶元素] >= a[i])，执行：
从 st 中弹出
如果 st 不为空，则：
prev := st 的栈顶元素
v[i] := v[i] + v[prev]
v[i] := v[i] + a[i] * (i - prev)
否则
v[i] := v[i] + a[i] * (i + 1)
将 i 插入 st
对于 v 中的每个 i：
ret := ret + i
返回 ret
从主方法执行以下操作：
ret := 0
n := v 的大小
m := (如果 n 非零，则 v[0] 的大小，否则为 0)
定义一个大小为 m 的数组 temp
for 初始化 i := 0，当 i < n，更新（i 增加 1），执行：
for 初始化 j := 0，当 j < m，更新（j 增加 1），执行：
temp[j] := (如果 v[i, j] 非零，则 temp[j] + 1，否则为 0)
ret := ret + getAns(temp)
返回 ret
示例
让我们看看以下实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getAns(vector& a) {
int ret = 0;
int n = a.size();
vector<int> v(n);
stack<int> st;
for (int i = 0; i < a.size(); i++) {
while (!st.empty() && a[st.top()] >= a[i])
st.pop();
if(!st.empty()) {
int prev = st.top();
v[i] += v[prev];
v[i] += a[i] * (i - prev);
}
else{
v[i] += a[i] * (i + 1);
}
st.push(i);
}
for (int i : v) {
ret += i;
}
return ret;
}
int solve(vector<vector<int>>& v) {
int ret = 0;
int n = v.size();
int m = n ? v[0].size() : 0;
vector<int> temp(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp[j] = v[i][j] ? temp[j] + 1 : 0;
}
ret += getAns(temp);
}
return ret;
}
};
int solve(vector<vector<int>>& matrix) {
return (new Solution())->solve(matrix);
}
main(){
vector<vector> matrix = {
{1, 1, 0},
{1, 1, 0},
{0, 0, 1}
};
cout << solve(matrix);
}输入
{{1, 1, 0},{1, 1, 0},{0, 0, 1}};输出
10
更新于：2020-12-22
121 次浏览
广告