数据结构
网络
关系数据库管理系统
操作系统
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 次查看
