Jianbo Dai's

lc118.杨辉三角

 
  • Aug 03, 2020

题目链接

在把以前leetcode美国账号的题都在中国账号上重新刷一遍。这题目就很简单了吧不用多说。也贴了一下官方的题解实现比我好看多了2333.这个算法的时间复杂度是O（N^2），空间复杂度是O（N^2）。

class Solution:
    def generate1(self, numRows: int) -> List[List[int]]:
        res = []
        if numRows == 0:
            return res
        elif numRows == 1:
            return [[1]]
        elif numRows == 2:
            return [[1], [1, 1]]
        res = [[1], [1, 1]]
        for i in range(1, numRows-1):
            new = [1]
            for j in range(i):
                new.append(res[i][j]+res[i][j+1])
            new += [1]
            res.append(new)
        return res

    def generate2(self, num_rows):
        triangle = []
        for row_num in range(num_rows):
            row = [None for _ in range(row_num+1)]
            row[0], row[-1] = 1, 1
            for j in range(1, len(row)-1):
                row[j] = triangle[row_num-1][j-1] + triangle[row_num-1][j]
            triangle.append(row)
        return triangle
Search