119. 杨辉三角 II
https://leetcode-cn.com/problems/pascals-triangle-ii/
解法一:迭代
与118题思路一样
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
if rowIndex == 0:
return[1]
elif rowIndex == 1:
return [1, 1]
row = [1,1]
for i in range(2, rowIndex+1):
new_row = [1] * (i+1)
for j in range(1, i):
new_row[j] = row[j-1] + row[j]
row = new_row
return row
解法二:组合数
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res = [0] * (rowIndex+1)
num, j = 1, 1
res[0] = 1
if rowIndex == 0:
return res
#用组合数C(rowIndex,k),k从1到rowIndex的一半,剩下一半对称
mid = rowIndex // 2
for i in range(1, mid+1):
num *= (rowIndex + 1 - i)
num //= j
j += 1
res[i] = num
if rowIndex % 2 == 0:
res[mid+1:] = res[mid-1::-1]
else:
res[mid+1:] = res[mid::-1]
return res
最后更新于