สมมติว่าเรามีเมทริกซ์ไบนารี 2d เราต้องหาจำนวนทั้งหมดของเมทริกซ์ย่อยที่มีทั้งหมด 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,
-
ยกเลิก :=0
-
n :=ขนาดของ a
-
กำหนดอาร์เรย์ v ขนาด n
-
กำหนดหนึ่งสแต็ก st
-
สำหรับการเริ่มต้น i :=0, เมื่อ i
-
ในขณะที่ (st ไม่ว่างเปล่าและ a[องค์ประกอบด้านบนของ st]>=a[i]) ทำ -
-
ป๊อปจากเซนต์
-
-
ถ้า st ไม่ว่างเปล่า −
-
ก่อนหน้า :=องค์ประกอบด้านบนของ st
-
v[i] :=v[i] + v[ก่อนหน้า]
-
v[i] :=v[i] + a[i] * (i - ก่อนหน้า)
-
-
มิฉะนั้น
-
v[i] :=v[i] + a[i] * (i + 1)
-
-
ใส่ i ลงใน st
-
-
สำหรับแต่ละ i ใน v -
-
ret :=ret + ผม
-
-
รีเทิร์น
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
ยกเลิก :=0
-
n :=ขนาดของวี
-
m :=(ถ้า n ไม่ใช่ศูนย์ ดังนั้นขนาดของ v[0] มิฉะนั้น 0)
-
กำหนดอุณหภูมิอาร์เรย์ขนาด m
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
สำหรับการเริ่มต้น j :=0 เมื่อ j
-
temp[j] :=(ถ้า v[i, j] ไม่ใช่ศูนย์ ดังนั้น temp[j] + 1 มิฉะนั้น 0)
-
-
ret :=ret + getAns(ชั่วคราว)
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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
