119 杨辉三角 II

本文最后更新于：2022年4月9日 中午


给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

img

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

1
2
输入: 3
输出: [1,3,3,1]

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

Solution

  • 初始化一个列表，遍历列表，从第1行开始填充。
  • 在下一行开始时，在列表的第一个位置插入0填充，遍历时，将第一个数与第二个数相加，结果赋值给第一个数。
1
2
3
4
5
6
7
8
9
10
# @lc code=start
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = [1]
        for i in range(rowIndex):
            res.insert(0, 0)
            for j in range(len(res)-1):
                res[j] = res[j+1] +res[j]
        return res
# @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！