leetcode304. 二维区域和检索 (二维前缀)

二维区域和检索

题目

给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。

leetcode304. 二维区域和检索 (二维前缀)

上图子矩阵左上角 (row1, col1) = (2, 1) ,右下角(row2, col2) = (4, 3),该子矩形内元素的总和为 8。

示例:

给定 matrix = [
[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) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

提示:

你可以假设矩阵不可变。
会多次调用 sumRegion 方法。
你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

思路:类比一维前缀,这里显然是二维的前缀和问题,我们如何求解一个二维的前缀和呢,
下面给出思路:

首先引入二维前缀

leetcode304. 二维区域和检索 (二维前缀)
比如:我们要求以上矩阵元素的和:
实际上:是由以下关系求出 (o->d 指以o为左上顶点,d为右下顶点 )

S ( o − > d ) = S ( o − > c ) + S ( o − > b ) − S ( o − > a ) + S ( d ) S (o->d)=S (o->c)+S (o->b)-S (o->a)+S(d) S(o−>d)=S(o−>c)+S(o−>b)−S(o−>a)+S(d)

S (o->a) 是重叠部分,需要减去)


这样,我们就可以由二维前缀算出以(r1,c1)为左上顶点,(r2,c2)为右下顶点的矩阵的和了

(这里的row,col是指下标,对应行列需要+1)

p r e s u m [ r o w 2 + 1 ] [ c o l 2 + 1 ] − p r e s u m [ r o w 1 ] [ c o l 2 + 1 ] − p r e s u m [ r o w 2 + 1 ] [ c o l 1 ] + p r e s u m [ r o w 1 ] [ c o l 1 ] presum[row2+1][col2+1]-presum[row1][col2+1]-presum[row2+1][col1]+presum[row1][col1] presum[row2+1][col2+1]−presum[row1][col2+1]−presum[row2+1][col1]+presum[row1][col1]

leetcode304. 二维区域和检索 (二维前缀)

二维前缀的模板


        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
    return presum[row2+1][col2+1]-presum[row1][col2+1]-presum[row2+1][col1]+presum[row1][col1]

题目code

class NumMatrix {
   static int[][] presum;
    public NumMatrix(int[][] matrix) {
      
        presum=new int[matrix.length+1][matrix[0].length+1];
        for(int i=1;i<=matrix.length;i++){
            for(int j=1;j<=matrix[0].length;j++){
                presum[i][j]=presum[i][j-1]+presum[i-1][j]-presum[i-1][j-1]+matrix[i-1][j-1];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return presum[row2+1][col2+1]-presum[row1][col2+1]-presum[row2+1][col1]+presum[row1][col1];
    }
}

上一篇:ALINK(二十):数据处理(六)数值型数据处理(二)标准化 (StandardScalerPredictBatchOp/StandardScalerTrainBatchOp )


下一篇:C语言重构【304】二维区域和检索 - 矩阵不可变