题目
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?
解题思路
- 第一行：1
- 第二行：1，2
- 第row行：
第一个数1，
第i(1 < i <= row/2 +1)个数row[i] = preRow[i-1] + preRow[i],
剩余的数等于前(row-1)/2个数的逆序
代码
func getRow(rowIndex int) []int {
row := []int{1}
if 0 == rowIndex {
return row
}
row = append(row, 1)
if 1 == rowIndex {
return row
}
var newRow []int
for i := 2; i <= rowIndex; i++ {
newRow = []int{1}
for j := 1; j < i/2 + 1; j++ {
tmp := row[j-1] + row[j]
newRow = append(newRow, tmp)
}
fmt.Printf("1newRow:%+v\n", newRow)
for k := (i-1)/2; k >= 0; k-- {
newRow = append(newRow, newRow[k])
}
fmt.Printf("2newRow:%+v\n", newRow)
row = newRow
}
return row
}
