力扣第119题-杨辉三角II

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

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

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:

输入: rowIndex = 0
输出: [1]
示例 3:

输入: rowIndex = 1
输出: [1,1]

提示:

0 <= rowIndex <= 33

！！！注意和杨辉三角那一题不一样的是，这道题的rorIndex是从0开始的，这一点要注意！

2.1 暴力解法

思路：还是两层循环，第一层循环为层数，第二层循环将这一层的每一个元素都添加到这一层的数组中去。

代码实现：

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        # 方法1： 暴力解法 时间复杂度O(N^2) 空间复杂度O(N^2)
        origin_lst = []
        for row in range(rowIndex + 1):
            origin_lst.append([])
            for j in range(row + 1):
                if j == 0 or j == row:
                    origin_lst[row].append(1)
                else:
                    origin_lst[row].append(origin_lst[row-1][j-1] + origin_lst[row-1][j])
        return origin_lst[rowIndex]

2.2 两个滚动数组

因为题目只要求返回一行的数据即可，所以我们只需要将上一行的数据记录下来，再计算接下来一行的数据，依次循环直到得到我们想要的那一行数据即可。

代码实现：

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        # 方法二：暴力解法优化 -- 降低空间复杂度到O(N)
        if rowIndex == 0:
            return [1]
        prior_lst = [1]
        for row in range(rowIndex + 1):
            next_lst = []
            for j in range(row + 1):
                if j == 0 or j == row:
                    next_lst.append(1)
                else:
                    next_lst.append(prior_lst[j - 1] + prior_lst[j])
            if row == rowIndex:
                return next_lst
            else:
                prior_lst = next_lst