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

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


示例

输入: rowIndex = 3

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

解析

1)最容易想到的方法,就是把完整的杨辉三角生成出来,再取最后一行;

2)生成完整三角的方法直观好懂,但只想要一行,我们却生成了整个结构,空间复杂度略高;

3)先这样处理吧,后面再优化。

代码示例

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        lst = [[1]]
        for i in range(rowIndex-1):
            prev = lst[-1]
            lst.append([m+n for m,n in zip([0]+prev, prev+[0])])
        return lst[-1]

执行用时:36 ms, 在所有 Python3 提交中击败了 72.50% 的用户.

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/378