[algorithm] sword finger offer2 golang interview question 13: sum of numbers of two-dimensional submatrix

[ Algorithm ] The finger of the sword offer2 golang Interview questions 13： Sum of numbers of two-dimensional submatrix

subject 1:

Ideas 1: Violent simulation

Violent simulation

Code

type NumMatrix struct {
    
    Matrix [][]int
}
func Constructor(matrix [][]int) NumMatrix {
    
    return NumMatrix{
    Matrix: matrix}
}
//start: 17:05
// Sum of elements of two-dimensional submatrix 
// Ideas :  Traverse each row of the submatrix and accumulate values 
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    
    // Processing parameters  todo

    // matrix 
    // That's ok i, Column j
    sum := 0
    for i:=row1; i <= row2; i++ {
    
         for j:=col1; j <= col2; j++{
    
             sum += this.Matrix[i][j]
         } 
    }
    return sum
}


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

Ideas 2: Calculate the value of each area in advance, and then finally calculate

For example, calculate the blue area 1 The value of can be equal to the red area 2 Subtract the green area 3 And other areas 4 and 5

When we construct, we record the values of the upper left to lower right positions of the rectangle, and then obtain the time complexity of each region O(1)

Code 2

type NumMatrix struct {
    
    sums [][]int
}


func Constructor(matrix [][]int) NumMatrix {
    
    // first line 
    for j:=1; j < len(matrix[0]); j++{
    
        matrix[0][j] = matrix[0][j-1] + matrix[0][j]
    }
    
    // The first 2-n That's ok 
    for i:=1; i < len(matrix); i++ {
    
        sum := 0
         for j:=0; j < len(matrix[0]); j++{
    
             sum += matrix[i][j]
             matrix[i][j] = sum + matrix[i-1][j]
         } 
    }

    return NumMatrix{
    sums: matrix}
}

//start: 17:05
// Sum of elements of two-dimensional submatrix 
// Ideas 2:  Calculate ahead of time (0,0) To each point sum Then the second calculation can O(1)
//a1 - a2 - a3 -a4
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    
    a1 := this.sums[row2][col2]
    a2 := 0
    a3 := 0
    a4 := 0

    if row1 >= 1 {
    
        a2 = this.sums[row1-1][col1]
        if col1 >= 1 {
    
            a2 = this.sums[row1-1][col1-1]
        }
    }
    if row1 >= 1 {
    
        a3 = this.sums[row1-1][col2] - a2
    }
    if col1 >= 1 {
    
        a4 = this.sums[row2][col1-1] - a2
    }

    return a1 - a2 - a3 - a4
}


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