目录

0119:杨辉三角 II

力扣第 119 题

题目

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 0 <= rowIndex <= 33

进阶:

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

相似问题:

分析

迭代即可。

解答

1
2
3
4
5
6
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = [1]
        for _ in range(rowIndex):
            res = [1]+[a+b for a,b in pairwise(res)]+[1]
        return res

31 ms

*附加

也可以利用数学知识,杨辉三角的第 k 行其实就是:

$$[ C_k^0, C_k^1, …, C_k^k ]$$

可以直接递推写出每一项。

1
2
3
4
5
6
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = [1]
        for i in range(1,rowIndex+1):
            res.append(res[-1]*(rowIndex+1-i)//i)
        return res

31 ms