[数组]杨辉三角 II

119. 杨辉三角 II

题目描述

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

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

示例:

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

解题思路

• 方法1:
  对每一行单独处理：首、尾分别添加一个0然后对应位置求和就可以得到新的一行。
  只用设置一个列表res即可，每循环一次就覆盖res一次即可。最终循环结束，返回res即可。
• 方法2:
  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保留即可.

代码实现

• 方法1:

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        res = [1]
        if rowIndex == 0:
            return res
        for i in range(1, rowIndex + 1):
            new_row = [a + b for a, b in zip([0] + res, res + [0])]
            res = new_row
        return res

• 方法2:

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        res = [1]
        for i in range(1, rowIndex + 1):
            res.insert(0, 0)
            for j in range(i):
                res[j] = res[j] + res[j + 1]
        return res