Leetcode 118/119. Pascal's Triangle

Posted on | | 阅读数
Words count in article: 259 | Reading time ≈ 1

Question

Solution1

对与一二两层，考虑直接返回。从第三层开始，由上一层元素相加开始得到本层中间元素，头尾的1直接添加，然后把本层添加到总体上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0:
            return []
        target = [[1]]
        if numRows == 1:
            return target
        target.append([1, 1])
        if numRows ==2:
            return target
        else:
            for i in range(2, numRows):
                temp = [1]
                upper = target[i-1]
                for j in range(i-1):
                    temp.append(upper[j+0] + upper[j+1])
                temp.append(1)
                target.append(temp)
            return target

Solution2

优化了行数

1
2
3
4
5
6
7
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        target = [[1]*n for n in range(1, numRows+1)]
        for i in range(1, numRows+1):
            for j in range(0, i-2):
                target[i-1][j+1] = target[i-2][j] + target[i-2][j+1]
        return target

119题，给的是rowIndex，返回指定行，所以只是修改了一下上面的代码

1
2
3
4
5
6
7
8
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        numRows = rowIndex + 1
        target = [[1]*n for n in range(1, numRows+1)]
        for i in range(1, numRows+1):
            for j in range(0, i-2):
                target[i-1][j+1] = target[i-2][j] + target[i-2][j+1]
        return target[rowIndex]