119. 杨辉三角 II

题目

给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。

杨辉三角

示例1:

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

示例2:

1
2
输入: rowIndex = 0
输出: [1]

示例3:

1
2
输入: rowIndex = 1
输出: [1,1]

提示:

  • 0 <= rowIndex <= 33

进阶:

你可以优化你的算法到 O(k) 空间复杂度吗?

解法

解法一:

迭代法

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> getRow(int rowIndex) {
List<Integer> first = new ArrayList<>();
List<Integer> second = new ArrayList<>();

for (int i = 0;i <= rowIndex;i++) {
first = new ArrayList<>();
for (int j = 0;j <= i;j++) {
if (0 == j || j == i) {
first.add(1);
} else {
first.add(second.get(j - 1) + second.get(j));
}
}
second = first;
}
return first;
}
0%