未分類

Pascal's Triangle II

Array, Go, LeetCode

Pascal’s Triangle II

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:

Could you optimize your algorithm to use only O(k) extra space?

提示 解題應用
Array Array/Slice

Default:

1
2
3
func getRow(rowIndex int) []int {
}

解答思路:

這題是巴斯卡三角形的進階題，說穿了只是多了一個對儲存空間的要求，這次你只能使用一個陣列，而且長度只能是要求列數的長度，第1列陣列長度就只能1，第2列陣列長度就只能2，題目給的是列的index值，所以要記得長度要+1，基本上就只不過是重覆使用同一個陣列罷了，只是原本巴斯卡三角形某列的中間第n項值為前一列的第n-1項值加上第n項值，在只有一個陣列而重覆使用的狀況下，原本第n項的值會被之後第n-1項值加上第n項值給覆蓋，問題在於求n+1項值需要用上第n項值加上第n+1項值時，因為先前的第n項已經被覆蓋而失去了原本的值，導致後面的項目無法求出正確的值，此時最好的做法就是從列的最後頭開始求值，因為每一列項目數都比前一列長度多出1，所以如果從最後開始算，新的第n項值就會擺到最後一個多出的位置，此時可以避免覆蓋掉需要用到的原始值，就可以放心的往前求出結果。

程式碼解說:

大致上與前一題求巴斯卡三角形類似，不過因為這次給的是列的index值而非第幾列，所以空間上要記得多補1，第一個迴圈因為同樣是index值就可以多個”等於”，至於關鍵就在於第二個迴圈上，為了不覆蓋需要用到的原始值所以要從後頭開始擺新的值，而最後頭的index值當然就是該列列數的index值，所以就直接將第一個迴圈的i值直接給第二個迴圈初始化即可，再來就只要從最後頭做到開頭index為0時就完成了

1
2
3
4
5
6
7
8
9
10
11
result := make([]int, rowIndex+1)
for i := 0; i <= rowIndex; i++ {
	for j := i; j >= 0; j-- {
		if j == 0 || j == i {
			result[j] = 1
		} else {
			result[j] = result[j-1] + result[j]
		}
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
func getRow(rowIndex int) []int {
	result := make([]int, rowIndex+1)
	for i := 0; i <= rowIndex; i++ {
		for j := i; j >= 0; j-- {
			if j == 0 || j == i {
				result[j] = 1
			} else {
				result[j] = result[j-1] + result[j]
			}
		}
	}
	return result
}

總結:

巴斯卡三角形在只有一個陣列而重覆使用的狀況下，原本第n項的值會被之後第n-1項值加上第n項值給覆蓋，問題在於求n+1項值需要用上第n項值加上第n+1項值時，因為先前的第n項已經被覆蓋而失去了原本的值，導致後面的項目無法求出正確的值，此時最好的做法就是從列的最後頭開始求值，因為每一列項目數都比前一列長度多出1，所以如果從最後開始算，新的第n項值就會擺到最後一個多出的位置，此時可以避免覆蓋掉需要用到的原始值，就可以放心的往前求出結果。

分享到