LeetCode *304. 二维区域和检索 - 矩阵不可变（前缀和）

SakuraTears

发布于 2022-01-13 14:39:22

1450

发布于 2022-01-13 14:39:22

文章被收录于专栏：从零开始的Code生活

题目

提示：你可以假设矩阵不可变。会多次调用 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);
 */

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021年03月03日，如有侵权请联系 cloudcommunity@tencent.com 删除

matrix