119. 杨辉三角 II

Posted on | In
Words count in article: 175 | Reading time ≈ 1

题目

给定一个非负索引 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%