lintcode665. 平面范围求和 -不可变矩阵

太过爱你忘了你带给我的痛 2023-07-25 14:04 113阅读 0赞

给一 二维矩阵,计算由左上角 (row1, col1) 和右下角 (row2, col2) 划定的矩形内元素和.

样例
    样例1
    
    输入：
    [[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
    解释：
    给出矩阵
    [
      [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) = 2 + 0 + 1 + 1 + 0 + 1 + 0 + 3 + 0 = 8
    sumRegion(1, 1, 2, 2) = 6 + 3 + 2 + 0 = 11
    sumRegion(1, 2, 2, 4) = 3 + 2 + 1 + 0 + 1 + 5 = 12
    样例2
    
    输入：
    [[3,0],[5,6]]
    sumRegion(0, 0, 0, 1)
    sumRegion(0, 0, 1, 1)
    输出：
    3
    14
    解释：
    给出矩阵
    [
      [3, 0],
      [5, 6]
    ]
    sumRegion(0, 0, 0, 1) = 3 + 0 = 3
    sumRegion(0, 0, 1, 1) = 3 + 0 + 5 + 6 = 14
    注意事项
    你可以假设矩阵不变
    对函数 sumRegion 的调用次数有很多次
    你可以假设 row1 ≤ row2 并且 col1 ≤ col2

思路：先看一维情况的求法  
我们可以求出一维矩阵从0到达所有地方的和。  
假设有矩阵【1，2，3，4，5】，那么和矩阵则为【1，3，6，10，15】  
将和矩阵前添加一个0，则为【0，1，3，6，10，15】  
那么此时，要求区间【i，j】的和即只需要求sum【j+1】-sum【i】即可  
那么将二维平面看成多个一维矩阵，即可得到。所以我们只需要求出二维平面中每一行的在【i，j】区间的和，然后把每一行的和相加即可。

class NumMatrix {
        
    public:
        vector<vector<int>>tmp;
        NumMatrix(vector<vector<int>> matrix) {
        
            int len = matrix.size();
            int len1=matrix[0].size();
            vector<vector<int>>sum(len,vector<int>(len1+2,0));
            for(int i = 0; i < len; i++)
            {
        
                int s=0;
                for (int j = 0; j < len1; j++) {
        
                    s+=matrix[i][j];
                    sum[i][j+1]=s;
                }
            }
            tmp=sum;
        }
        
        int sumRegion(int row1, int col1, int row2, int col2) {
        
            int res=0;
            for(int i =row1;i<=row2;i++)
            {
        
                res+=tmp[i][col2+1]-tmp[i][col1];
            }
            return res;
        }
    };
    
    /**
     * Your NumMatrix object will be instantiated and called as such:
     * NumMatrix obj = new NumMatrix(matrix);
     * int param_1 = obj.sumRegion(row1,col1,row2,col2);
     */