好资源导航 » 文章资讯 » 范围总和查询 2D - C++ 中的不可变

范围总和查询 2D - C++ 中的不可变

2023-06-21 16:23:03 77

假设我们有一个称为矩阵的二维矩阵，我们必须使用(row1,col1)和右下角使用(row2,col2)找到由矩形左上角定义的元素的总和。

所以如果矩阵是这样的-

3014256321120154101710305

上面的蓝色矩形由(2,1)和(4,3)定义，它包含和8。

因此，如果我们执行一些查询，如sumRegion(2,1,4,3),sumRegion(1,1,2,2),sumRegion(1,2,2,4)，它们将分别返回8,11,12。

示例（C++）

让我们看看以下实现以获得更好的理解-

#include 
using namespace std;
class NumMatrix {
   public:
   vector < vector > dp;
   NumMatrix(vector>& matrix) {
      int n = matrix.size();
      if(!n) return;
      int m = matrix[0].size();
      dp = vector < vector >(n, vector  (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> 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

返回顶部
514930285
czq8825@qq.com

范围总和查询 2D - C++ 中的不可变

示例（C++）

输入

热门推荐

随机推荐