题目描述

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

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

示例

示例 1:

输入: rowIndex = 3

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

示例 2:

输入: rowIndex = 0

输出: [1]

示例 3:

输入: rowIndex = 1

输出: [1,1]

提示:

0 <= rowIndex <= 33

解题思路

1. 递推解法（空间复杂度 O(k²)）

  • 创建二维数组存储所有行
  • 每个位置的值是上一行相邻两个数的和
  • 边界位置都是1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#递推解法（空间复杂度O(k^2)）

class Solution:

    def getRow(self, rowIndex: int) -> List[int]:

        C = [[1] * (i + 1) for i in range(rowIndex + 1)]

        for i in range(0, rowIndex + 1):

            for j in range(1, i):

                C[i][j] = C[i - 1][j - 1] + C[i - 1][j]

        return C[rowIndex]

#滚动数组解法（空间复杂度O(k)）   

class Solution:

    def getRow(self, rowIndex: int) -> List[int]:

        cur,pre = [],[]

        for i in range(rowIndex + 1):

            cur = [1] * (i + 1)

            for j in range(1,i):

                cur[j] = pre[j - 1] + pre[j]

            pre = cur

        return pre