資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告