【問(wèn)題描述】
給定一個(gè)非負(fù)索引 k盒粮，其中 k ≤ 33疟丙，返回楊輝三角的第 k 行余黎。
在楊輝三角中重窟，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。
PascalTriangleAnimated2.gif
【示例】
輸入: 3
輸出: [1,3,3,1]
【進(jìn)階】
你可以優(yōu)化你的算法到 O(k) 空間復(fù)雜度嗎惧财？
【思路1】
1巡扇、時(shí)間復(fù)雜度O(nlogn)
2扭仁、空間復(fù)雜度O(n+k)
func getRow(_ rowIndex: Int) -> [Int] {
if rowIndex == 0 {
return [1]
} else if rowIndex == 1 {
return [1,1]
} else {
var arr = [[Int]]()
arr.append([1])
arr.append([1,1])
for num in 2...rowIndex {
var tmp = [Int]()
let preArr = arr[num-1]
for i in 0...num {
if i == 0 || i == num {
tmp.append(1)
} else {
tmp.append(preArr[i]+preArr[i-1])
}
}
arr.append(tmp)
}
return arr[rowIndex]
}
}
【思路2】
1、因?yàn)橹恍枰祷亟o定行數(shù)數(shù)組即可厅翔，不需要保留整個(gè)數(shù)組
2乖坠、所以只需要一直迭代循環(huán)即可，需要給出邊界為0的值
3刀闷、當(dāng)rowIndex=0,return [1]
4熊泵、空間復(fù)雜度O(k)
5、時(shí)間復(fù)雜度O(nlogn)
func getRow(_ rowIndex: Int) -> [Int] {
var result = Array.init(repeating: 0, count: rowIndex+1)
result[0] = 1
for i in 0...rowIndex {
var tmp = i
while tmp > 0 {
result[tmp]+=result[tmp-1]
tmp-=1
}
}
return result
}
