未分類

Range Sum Query 2D - Immutable

DynamicProgramming, Go, LeetCode

Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

For example:

1
2
3
4
5
6
7
8
9
10
11
Given 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

Note:

  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Default:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type NumMatrix struct {
    
}
func Constructor(matrix [][]int) NumMatrix {
    
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    
}
/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */

解答思路:

要找出一平面上矩形範圍內所有值的總合，既然有給該矩形的最左上角與最右下角座標，那麼就只要用巢狀迴圈便能遍歷該範圍內的所有值，唯一要注意的就是每次都需要檢查取值的座標是否仍落在平面上，最後雖然題目要求以物件的方式來完成，不過因為資料與行為都非常單純，所以就沒有什麼大問題。

程式碼解說:

題目要求以物件的方式來完成，所以一開始先定義好平面的結構(僅包含二元陣列的資料)與初始化的函數(將帶入的二元陣列做物件的初始化並回傳)

1
2
3
4
5
6
type NumMatrix struct {
	matrix [][]int
}
func Constructor(matrix [][]int) NumMatrix {
	return NumMatrix{matrix}
}

接著要找出一平面上矩形範圍內所有值的總合，既然有給該矩形的最左上角與最右下角座標(二元陣列的index值)，那麼就只要用巢狀迴圈便能遍歷該範圍內的所有值(row1→row2;col1→col2)，唯一要注意的就是每次都需要檢查取值的座標是否仍落在平面上，最後待範圍內的值都加總完畢便向上回傳總合結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	var sum int
	for i := row1; i <= row2; i++ {
		if i >= len(this.matrix) {
			break
		}
		for j := col1; j <= col2; j++ {
			if j >= len(this.matrix[0]) {
				break
			}
			sum += this.matrix[i][j]
		}
	}
	return sum
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type NumMatrix struct {
	matrix [][]int
}
func Constructor(matrix [][]int) NumMatrix {
	return NumMatrix{matrix}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	var sum int
	for i := row1; i <= row2; i++ {
		if i >= len(this.matrix) {
			break
		}
		for j := col1; j <= col2; j++ {
			if j >= len(this.matrix[0]) {
				break
			}
			sum += this.matrix[i][j]
		}
	}
	return sum
}

總結:

要找出一平面上矩形範圍內所有值的總合，既然有給該矩形的最左上角與最右下角座標，那麼就只要用巢狀迴圈便能遍歷該範圍內的所有值，唯一要注意的就是每次都需要檢查取值的座標是否仍落在平面上，最後雖然題目要求以物件的方式來完成，不過因為資料與行為都非常單純，所以就沒有什麼大問題。

分享到