資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中求和為目標值的子矩陣數量
假設我們有一個矩陣和一個目標值，我們需要找到和等於目標值的非空子矩陣的數量。這裡，子矩陣 [(x1, y1), (x2, y2)] 是所有單元格 matrix[x][y] 的集合，其中 x 的範圍在 x1 和 x2 之間，y 的範圍在 y1 和 y2 之間。兩個子矩陣 [(x1, y1), (x2, y2)] 和 [(x1', y1'), (x2', y2')] 不同，如果它們的一些座標不同：例如，如果 x1 與 x1' 不相同。
因此，如果輸入如下所示：
| 0 | 1 | 0 |
| 1 | 1 | 1 |
| 0 | 1 | 0 |
並且目標值為 0，則輸出將為 4，這是因為有四個僅包含 0 的 1x1 子矩陣。
為了解決這個問題，我們將遵循以下步驟：
ans := 0
col := 列數
row := 行數
初始化 i := 0，當 i < row 時，更新（i 增加 1），執行以下操作：
初始化 j := 1，當 j < col 時，更新（j 增加 1），執行以下操作：
matrix[i, j] := matrix[i, j] + matrix[i, j - 1]
定義一個 map m
初始化 i := 0，當 i < col 時，更新（i 增加 1），執行以下操作：
初始化 j := i，當 j < col 時，更新（j 增加 1），執行以下操作：
清空 map m
m[0] := 1
sum := 0
初始化 k := 0，當 k < row 時，更新（k 增加 1），執行以下操作：
current := matrix[k, j]
如果 i - 1 >= 0，則執行以下操作：
current := current - matrix[k, i - 1]
sum := sum + current
ans := ans + m[target - sum]
m[-sum] 增加 1
返回 ans
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int
target) {
int ans = 0;
int col = matrix[0].size();
int row = matrix.size();
for(int i = 0; i < row; i++){
for(int j = 1; j < col; j++){
matrix[i][j] += matrix[i][j - 1];
}
}
unordered_map <int, int> m;
for(int i = 0; i < col; i++){
for(int j = i; j < col; j++){
m.clear();
m[0] = 1;
int sum = 0;
for(int k = 0; k < row; k++){
int current = matrix[k][j];
if(i - 1 >= 0)current -= matrix[k][i - 1];
sum += current;
ans += m[target - sum];
m[-sum]++;
}
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}};
cout << (ob.numSubmatrixSumTarget(v, 0));
}輸入
{{0,1,0},{1,1,1},{0,1,0}}, 0輸出
4
190 次檢視
