未分類

Pascal's Triangle

Array, Go, LeetCode

Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle.

For example:

Given numRows = 5, Return

1
2
3
4
5
6
7
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
提示 解題應用
Array Array/Slice

Default:

1
2
3
func generate(numRows int) [][]int {
}

解答思路:

只要了解巴斯卡三角形規律是如何，應該都可以輕易的完成本題，以每一列來說就是頭與尾皆為1，而中間n的值就是前一列n-1的值與n的值相加，知道規則之後，如此一來應該不需要多大的功夫就可以解出來了。

程式碼解說:

首先先初始化一個二階陣列，之後第一個迴圈就是開始執行需要的巴斯卡三角形共要幾列，這邊我從0來開始計算以方便我們在二元陣列時能直接用index值來指定該列的陣列，因為最初僅初始化二階陣列，然而實際上二階陣列裡並沒有任何一個陣列，所以在確定需要的巴斯卡三角形列數之後，就接著在裡頭新增相同數目的陣列，之後第二個迴圈就是執行該列的陣列中有多少個值，列如第一列就只有1個，第二列有2個…以此類推，一樣也是從0開始方便直接在陣列用index值指定哪一項的值，前置工作都完成後再來就只要判斷如果是該列的頭與尾也就是index值的0與目前在巴斯卡三角形的第幾列再減1，此時就將1新增至該列的陣列之中，至於中間的n值正如先前所說，不過就是前一列n-1的值與n的值相加，一樣也插入該列的陣列後就完成了

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

完整程式碼:

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

總結:

巴斯卡三角形的規律以每列來說就是頭與尾皆為1，而中間n的值就是前一列n-1的值與n的值相加。

分享到