LC 119. 杨辉三角 II
题目描述
这是 LeetCode 上的 119. 杨辉三角 II ,难度为 简单。
给定一个非负索引 k
,其中 k ≤ 33
,返回杨辉三角的第 k
行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例:1
2
3输入: 3
输出: [1,3,3,1]
进阶:
- 你可以优化你的算法到 $O(k)$ 空间复杂度吗?
动态规划
动态规划裸题。
定义 $f[i][j]$ 为杨辉三角中第 $i$ 行第 $j$ 列的值,然后根据杨辉三角规则(每个数是它左上方和右上方的数的和)进行转移,初始化有 $f[0][0] = 1$。
Java 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public List<Integer> getRow(int idx) {
int[][] f = new int[idx + 1][idx + 1];
f[0][0] = 1;
for (int i = 1; i < idx + 1; i++) {
for (int j = 0; j < i + 1; j++) {
f[i][j] = f[i - 1][j];
if (j - 1 >= 0) f[i][j] += f[i - 1][j - 1];
if (f[i][j] == 0) f[i][j] = 1;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < idx + 1; i++) ans.add(f[idx][i]);
return ans;
}
}
C++ 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
vector<int> getRow(int idx) {
vector<vector<int>> f(idx + 1, vector<int>(idx + 1, 0));
f[0][0] = 1;
for (int i = 1; i < idx + 1; i++) {
for (int j = 0; j < i + 1; j++) {
f[i][j] = f[i - 1][j];
if (j - 1 >= 0) f[i][j] += f[i - 1][j - 1];
if (f[i][j] == 0) f[i][j] = 1;
}
}
vector<int> ans;
for (int i = 0; i < idx + 1; i++) ans.push_back(f[idx][i]);
return ans;
}
};
Python 代码:1
2
3
4
5
6
7
8
9
10
11
12class Solution:
def getRow(self, idx: int) -> List[int]:
f = [[0] * (idx + 1) for i in range(idx + 1)]
f[0][0] = 1
for i in range(1, idx + 1):
for j in range(i + 1):
f[i][j] = f[i - 1][j]
if j - 1 >= 0:
f[i][j] += f[i - 1][j - 1]
if f[i][j] == 0:
f[i][j] = 1
return [f[idx][i] for i in range(idx + 1)]
TypeScript 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14function getRow(idx: number): number[] {
const f: number[][] = new Array(idx + 1).fill(0).map(() => new Array(idx + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i < idx + 1; i++) {
for (let j = 0; j < i + 1; j++) {
f[i][j] = f[i - 1][j];
if (j - 1 >= 0) f[i][j] += f[i - 1][j - 1];
if (f[i][j] == 0) f[i][j] = 1;
}
}
const ans: number[] = [];
for (let i = 0; i < idx + 1; i++) ans.push(f[idx][i]);
return ans;
};
- 时间复杂度:$O(n^2)$
- 空间复杂度:$O(n^2)$
滚动数组
滚动数组优化十分机械,直接将滚动的维度从 i
改造为 i % 2
或 i & 1
即可。
i & 1
相比于 i % 2
在不同架构的机器上,效率会更稳定些。
Java 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public List<Integer> getRow(int idx) {
int[][] f = new int[2][idx + 1];
f[0][0] = 1;
for (int i = 1; i < idx + 1; i++) {
for (int j = 0; j < i + 1; j++) {
f[i & 1][j] = f[(i - 1) & 1][j];
if (j - 1 >= 0) f[i & 1][j] += f[(i - 1) & 1][j - 1];
if (f[i & 1][j] == 0) f[i & 1][j] = 1;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < idx + 1; i++) ans.add(f[idx & 1][i]);
return ans;
}
}
C++ 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
vector<int> getRow(int idx) {
vector<vector<int>> f(2, vector<int>(idx + 1, 0));
f[0][0] = 1;
for (int i = 1; i < idx + 1; i++) {
for (int j = 0; j < i + 1; j++) {
f[i & 1][j] = f[(i - 1) & 1][j];
if (j - 1 >= 0) f[i & 1][j] += f[(i - 1) & 1][j - 1];
if (f[i & 1][j] == 0) f[i & 1][j] = 1;
}
}
vector<int> ans;
for (int i = 0; i < idx + 1; i++) ans.push_back(f[idx & 1][i]);
return ans;
}
};
Python 代码:1
2
3
4
5
6
7
8
9
10
11
12class Solution:
def getRow(self, idx: int) -> List[int]:
f = [[0] * (idx + 1) for i in range(2)]
f[0][0] = 1
for i in range(1, idx + 1):
for j in range(i + 1):
f[i & 1][j] = f[(i - 1) & 1][j]
if j - 1 >= 0:
f[i & 1][j] += f[(i - 1) & 1][j - 1]
if f[i & 1][j] == 0:
f[i & 1][j] = 1
return [f[idx & 1][i] for i in range(idx + 1)]
TypeScript 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14function getRow(idx: number): number[] {
const f: number[][] = new Array(2).fill(0).map(() => new Array(idx + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i < idx + 1; i++) {
for (let j = 0; j < i + 1; j++) {
f[i & 1][j] = f[(i - 1) & 1][j];
if (j - 1 >= 0) f[i & 1][j] += f[(i - 1) & 1][j - 1];
if (f[i & 1][j] == 0) f[i & 1][j] = 1;
}
}
const ans: number[] = [];
for (let i = 0; i < idx + 1; i++) ans.push(f[idx & 1][i]);
return ans;
};
- 时间复杂度:$O(n^2)$
- 空间复杂度:$O(n)$
一维优化
只有第 i
行的更新只依赖于 i - 1
行,因此可以直接消除行的维度。
但需要注意,为了防止在计算当前行的第 j
列时,所依赖于前一行的第 j - 1
列被覆盖,我们需要调整列循环的方向(从大到小转移)。
Java 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public List<Integer> getRow(int idx) {
int[] f = new int[idx + 1];
f[0] = 1;
for (int i = 1; i < idx + 1; i++) {
for (int j = i; j >= 0; j--) {
if (j - 1 >= 0) f[j] += f[j - 1];
if (f[j] == 0) f[j] = 1;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < idx + 1; i++) ans.add(f[i]);
return ans;
}
}
C++ 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
vector<int> getRow(int idx) {
vector<int> f(idx + 1, 0);
f[0] = 1;
for (int i = 1; i < idx + 1; i++) {
for (int j = i; j >= 0; j--) {
if (j - 1 >= 0) f[j] += f[j - 1];
if (f[j] == 0) f[j] = 1;
}
}
vector<int> ans;
for (int i = 0; i < idx + 1; i++) ans.push_back(f[i]);
return ans;
}
};
Python 代码:1
2
3
4
5
6
7
8
9
10
11class Solution:
def getRow(self, idx: int) -> List[int]:
f = [0] * (idx + 1)
f[0] = 1
for i in range(1, idx + 1):
for j in range(i, 0, -1):
if j - 1 >= 0:
f[j] += f[j - 1]
if f[j] == 0:
f[j] = 1
return [f[i] for i in range(idx + 1)]
TypeScript 代码:1
2
3
4
5
6
7
8
9
10
11
12
13function getRow(idx: number): number[] {
const f: number[] = new Array(idx + 1).fill(0)
f[0] = 1;
for (let i = 1; i < idx + 1; i++) {
for (let j = i; j >= 0; j--) {
if (j - 1 >= 0) f[j] += f[j - 1];
if (f[j] == 0) f[j] = 1;
}
}
const ans: number[] = [];
for (let i = 0; i < idx + 1; i++) ans.push(f[i]);
return ans;
};
- 时间复杂度:$O(n^2)$
- 空间复杂度:$O(n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.119
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!