给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例:
输入: 3
输出: [1,3,3,1]
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
# j行的数据, 应该由j - 1行的数据计算出来.
# 假设j - 1行为[1,3,3,1], 那么我们前面插入一个0(j行的数据会比j-1行多一个),
# 然后执行相加[0+1,1+3,3+3,3+1,1] = [1,4,6,4,1], 最后一个1保留即可.
r = [1]
for i in range(1, rowIndex + 1):
r.insert(0, 0)
# 因为i行的数据长度为i+1, 所以j+1不会越界, 并且最后一个1不会被修改.
for j in range(i):
r[j] = r[j] + r[j + 1]
return r
模拟法(动态规划)
1,特判,若k==0k==0,返回[1][1]
2,初始化dp=[1,1]dp=[1,1],表示第二行
3,遍历区间[3,k+2)[3,k+2),表示从第三行开始遍历:
初始化cur=[1,0,...,0,1]cur=[1,0,...,0,1],长度为当前行数,从curcur第二个元素到倒数第二个元素,利用动态规划:cur[j]=dp[j-1]+dp[j]cur[j]=dp[j−1]+dp[j],将dpdp更新为curcur
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
if(rowIndex==0):
return [1]
dp=[1,1]
for i in range(3,rowIndex+2):
cur=[0]*(i)
cur[0]=cur[-1]=1
for j in range(1,i-1):
cur[j]=dp[j-1]+dp[j]
dp=cur
return dp
来源:力扣(LeetCode)
网友评论