30杨辉三角II

2020-08-07  本文已影响0人  Jachin111

给定一个非负索引 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)

上一篇下一篇

猜你喜欢

热点阅读