資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢矩陣中元素和等於特定值的子矩陣數量
假設我們得到一個包含整數值的矩陣。我們需要找到矩陣中的子矩陣，其中子矩陣的元素之和等於給定的目標和值。我們返回子矩陣的數量。
因此，如果輸入如下所示：
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 |
並且目標值為5，則輸出將為3。
元素和等於6的子矩陣數量為2。
為了解決這個問題，我們將遵循以下步驟：
- n := mat的大小
- m := (如果n等於0，則為0，否則為mat[0]的大小)
- 如果m > n，則：
- 定義一個維度為m x n的二維陣列transpose（轉置）
- 初始化i := 0，當i < n時，更新（i加1），執行：
- 初始化j := 0，當j < m時，更新（j加1），執行：
- transpose[j, i] := mat[i, j]
- 初始化j := 0，當j < m時，更新（j加1），執行：
- 返回solve(transpose, sumTarget)
- ans := 0
- 初始化p := 0，當p < m時，更新（p加1），執行：
- 定義一個數組arr
- 初始化q := p，當q < m時，更新（q加1），執行：
- 初始化i := 0，當i < n時，更新（i加1），執行：
- arr[i] := arr[i] + mat[i, q]
- 定義一個包含鍵值對{0, 1}的map pcnt
- pref := 0
- 初始化i := 0，當i < n時，更新（i加1），執行：
- pref := pref + arr[i]
- tmp := (pref - sumTarget)在pcnt中的位置
- 如果tmp不等於pcnt的末尾位置，則：
- (pcnt[pref]加1)
- 初始化i := 0，當i < n時，更新（i加1），執行：
- 返回ans
示例
讓我們看看以下實現，以便更好地理解：
#include<bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>>& mat, int sumTarget) {
int n = mat.size();
int m = n == 0 ? 0 : mat[0].size();
if (m > n) {
vector<vector<int>> transpose(m, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
transpose[j][i] = mat[i][j];
}
}
return solve(transpose, sumTarget);
}
int ans = 0;
for (int p = 0; p < m; p++) {
vector<int> arr(n);
for (int q = p; q < m; q++) {
for (int i = 0; i < n; i++) {
arr[i] += mat[i][q];
}
unordered_map<int, int> pcnt = {{0, 1}};
int pref = 0;
for (int i = 0; i < n; i++) {
pref += arr[i];
auto tmp = pcnt.find(pref - sumTarget);
if (tmp != end(pcnt)) ans += tmp->second;
pcnt[pref]++;
}
}
}
return ans;
}
int main() {
vector<vector<int>> mat = {{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}};
cout<< solve(mat, 5) <<endl;
return 0;
}輸入
{{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}, 5輸出
3
更新於: 2021年10月16日
229 次檢視
廣告