首页 🍒LeetCode,🐶算法

题目

5nMUiilpZ3.png
提示:
你可以假设矩阵不可变。
会多次调用 sumRegion 方法。
你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

思路

和上一题一样如果把计算过程放在sumRegion方法中会浪费大量时间,所以依旧用到前缀和。
二维数组中求preSum:
preSum[i][j] = preSum[i − 1][j] + preSum[i][j − 1] − preSum[i − 1][j − 1] + matrix[i][j]
如果不明白可以去看LeetCode题解
求一部分的preSum:
preSum[row2][col2] − preSum[row2][col1 − 1] − preSum[row1 − 1][col2] + preSum[row1 − 1][col1 − 1]

class NumMatrix {
public:
    vector<vector<int>> pre;

    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty()) return ;
        pre.resize(matrix.size() + 1);
        for(int i = 0; i <= matrix.size(); i++) {
            pre[i].resize(matrix[0].size() + 1);
        }
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return pre[row2 + 1][col2 + 1] - pre[row2 + 1][col1] - pre[row1][col2 + 1] + pre[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */



文章评论