0119：杨辉三角 II

2015-04-29 约 242 字预计阅读 1 分钟次阅读

力扣第 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

目录

0119：杨辉三角 II

题目

分析

解答

*附加