【LetMeFly】118.杨辉三角
力扣题目链接：https://leetcode.cn/problems/pascals-triangle/
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
方法一：动态规划
我们用vector<vector<int>> ans来存放杨辉三角。
初始化杨辉三角的第一行（ans.push_back({1})）
之后从第$2$行开始（下标$i$从$1$开始），不断生成每一行。
第i + 1行的生成方法为：
首先向这一行中添加第一个元素$1$（ans.push_back({1})）
然后从第$2$个元素开始（下标$j$从$1$开始），到这一行最后一个元素的前一个为止，第i + 1行的第j + 1个元素等于上一行的对应两个元素之和（ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]）
最后，再向这一行的末尾添加一个$1$即可。
如果不理解，可以参考杨辉三角的第$3$行的第$2$个元素$3$的生成来研究：
当计算到第$3$行的第$2$个元素时，$i=2,j=1$。此时$ans[i][j]=ans[i-1][j-1]+ans[i-1][j]=1+1=2$，说明第$3$行的第$2$个元素的值为$2$。
- 时间复杂度$O(size^2)$
- 空间复杂度$O(1)$，答案不计入算法空间复杂度
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans;
ans.push_back({1});
for (int i = 1; i < numRows; i++) {
ans.push_back({1});
for (int j = 1; j < i; j++) {
ans[i].push_back(ans[i - 1][j - 1] + ans[i - 1][j]);
}
ans[i].push_back(1);
}
return ans;
}
};
|
运行结果：耗时还挺少
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| '''
Author: LetMeFly
Date: 2025-08-01 23:51:32
LastEditors: LetMeFly.xyz
LastEditTime: 2025-08-02 00:01:53
'''
from typing import List
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = [[1] for _ in range(numRows)]
for i in range(1, numRows):
for j in range(1, i):
ans[i].append(ans[i - 1][j - 1] + ans[i - 1][j])
ans[i].append(1)
return ans
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import java.util.List;
import java.util.ArrayList;
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>(numRows);
ans.add(List.of(1));
for (int i = 1; i < numRows; i++) {
ans.add(new ArrayList<>(i + 1));
ans.get(i).add(1);
for (int j = 1; j < i; j++) {
ans.get(i).add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
}
ans.get(i).add(1);
}
return ans;
}
}
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
package main
func generate(numRows int) [][]int {
ans := make([][]int, numRows)
ans[0] = []int{1}
for i := 1; i < numRows; i++ {
ans[i] = make([]int, i + 1)
ans[i][0] = 1
for j := 1; j < i; j++ {
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]
}
ans[i][i] = 1
}
return ans
}
|
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
impl Solution {
pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
let size = num_rows as usize;
let mut ans = vec![vec![]; size];
for i in 0..size {
ans[i].resize(i + 1, 1);
for j in 1..i {
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
}
}
ans
}
}
|
同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125829159