leetcode304 二维区域和检索 - 矩阵不可变 golang

lucasgao · · 329 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

第一次，站长亲自招 Gopher 了>>>

304. 二维区域和检索 - 矩阵不可变

解题思路

image.png

和昨天的一样，利用 sum[i][j]表示 num[0][0]+... nums[i-1][j-1]的数值即可

具体可以参考 https://www.jianshu.com/p/e11b76a1eb4f

注意点

做预处理的时候，先按照行处理，再按照列处理。一定切记不可重复计算。
统计区域和因为 sum[r][c] 被重复减掉了，需要加回来。

代码

type NumMatrix struct {
    A [][]int
}


func Constructor(matrix [][]int) NumMatrix {
    n := NumMatrix{}
    if len(matrix)==0{
        return n
    }
    r,c := len(matrix),len(matrix[0])
    A := make([][]int,r+1)
    A[0]=make([]int,c+1)
    for i:=1;i<len(A);i++{
        A[i]=make([]int,c+1)
        for j:=1;j<len(A[i]);j++{
            A[i][j]=A[i][j-1]+matrix[i-1][j-1]
        }
    }
    for j:=1;j<len(A[0]);j++{
        for i:=1;i<len(A);i++{
            A[i][j]+=A[i-1][j]
        }
    }
    n.A = A
    return n
}


func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return this.A[row2+1][col2+1]+this.A[row1][col1]-this.A[row2+1][col1]-this.A[row1][col2+1]
}


/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */

有疑问加站长微信联系（非本文作者）