資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中二維範圍求和 - 不可變
假設我們有一個名為 matrix 的二維矩陣，我們需要找到由左上角 (row1, col1) 和右下角 (row2, col2) 定義的矩形內的元素之和。
如果矩陣如下所示：
| 3 | 0 | 1 | 4 | 2 |
| 5 | 6 | 3 | 2 | 1 |
| 1 | 2 | 0 | 1 | 5 |
| 4 | 1 | 0 | 1 | 7 |
| 1 | 0 | 3 | 0 | 5 |
上面用藍色表示的矩形，由 (2,1) 和 (4,3) 定義，其總和為 8。
因此，如果我們執行一些查詢，例如 sumRegion(2, 1, 4, 3)，sumRegion(1, 1, 2, 2)，sumRegion(1, 2, 2, 4)，它們將分別返回 8、11、12。
為了解決這個問題，我們將遵循以下步驟：
定義一個名為 dp 的矩陣。
初始化任務如下
n := 行數。如果 n 為 0，則返回，
m := 列數
dp := 另一個大小為 n x m 的矩陣
對於範圍從 0 到 n 的 i
對於範圍從 0 到 m 的 j
當 j – 1 < 0 時，將 dp[i, j] 設定為 matrix[i, j]，否則將其設定為 (dp[i, j - 1] + matrix[i, j])
對於範圍從 1 到 n 的 i
對於範圍從 0 到 m 的 j
將 dp[i, j] 增加 dp[i – 1, j]
對於查詢方法，這將採用 row1、col1、row2、col2
ret := dp[row2, col2]
sub1 := 當 row1 – 1 < 0 時為 0，否則為 dp[row1 – 1, col2]
sub2 := 當 col1 – 1 < 0 時為 0，否則為 dp[row2, col1 - 1]
如果 row1 – 1 < 0 或 col1 – 1 < 0，則
add := 0
否則 add := dp[row1 – 1, col1 – 1]
返回 ret – sub1 – sub2 + add
示例（C++）
讓我們看看以下實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
public:
vector < vector <int>> dp;
NumMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
if(!n) return;
int m = matrix[0].size();
dp = vector < vector <int>>(n, vector <int> (m));
for(int i = 0; i < n; i++){
for(int j = 0 ;j < m; j++){
dp[i][j] = j - 1 < 0 ? matrix[i][j] : dp[i][j - 1] + matrix[i][j];
}
}
for(int i = 1; i < n; i++){
for(int j = 0; j < m; j++){
dp[i][j] += dp[i - 1][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int ret = dp[row2][col2];
int sub1 = row1 - 1 < 0 ? 0 : dp[row1 - 1][col2];
int sub2 = col1 - 1 < 0 ? 0 : dp[row2][col1 - 1];
int add = row1 - 1 < 0 || col1 - 1 < 0 ? 0 : dp[row1 - 1][col1 - 1];
return ret - sub1 - sub2 + add;
}
};
main(){
vector<vector<int>> mat = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
NumMatrix ob(mat);
cout << ob.sumRegion(2,1,4,3) << endl;
cout << ob.sumRegion(1,1,2,2) << endl;
cout << ob.sumRegion(1,2,2,4) << endl;
}輸入
[[3,0,1,4,2], [5,6,3,2,1], [1,2,0,1,5], [4,1,0,1,7], [1,0,3,0,5]] sumRegion(2,1,4,3) sumRegion(1,1,2,2) sumRegion(1,2,2,4)
輸出
8 11 12
349 次檢視
