未分類

Range Sum Query - Mutable

BinaryIndexedTree, Go, LeetCode, SegmentTree

Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

For example:

1
2
3
4
5
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

Default:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
type NumArray struct {
    
}
func Constructor(nums []int) NumArray {
    
}
func (this *NumArray) Update(i int, val int)  {
    
}
func (this *NumArray) SumRange(i int, j int) int {
    
}
/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * obj.Update(i,val);
 * param_2 := obj.SumRange(i,j);
 */

解答思路:

這題有點出乎意料之外，因為被歸類在中等難度本以為又會用上什麼技巧，沒想到就單純只是要實作物件的方法，包含初始化物件結構、更新物件資料(陣列)特定index的值與加總資料陣列上兩個index範圍內的值。

程式碼解說:

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

1
2
3
4
5
6
type NumArray struct {
	array []int
}
func Constructor(nums []int) NumArray {
	return NumArray{nums}
}

更新物件資料函數就是先取出物件中的陣列資料，接著在需要修改的index位置賦予想要的值

1
2
3
func (this *NumArray) Update(i int, val int) {
	this.array[i] = val
}

計算範圍總合的函數就是利用一迴圈將index範圍i至j內的陣列資料做加總，待結束後便向上回傳總合結果

1
2
3
4
5
6
7
func (this *NumArray) SumRange(i int, j int) int {
	var sum int
	for index := i; index <= j; index++ {
		sum += this.array[index]
	}
	return sum
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type NumArray struct {
	array []int
}
func Constructor(nums []int) NumArray {
	return NumArray{nums}
}
func (this *NumArray) Update(i int, val int) {
	this.array[i] = val
}
func (this *NumArray) SumRange(i int, j int) int {
	var sum int
	for index := i; index <= j; index++ {
		sum += this.array[index]
	}
	return sum
}

總結:

本題單純只是要實作物件的方法，包含初始化物件結構、更新物件資料(陣列)特定index的值與加總資料陣列上兩個index範圍內的值。

分享到