友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
118. 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1 输出: [[1]]
提示:
-
1 <= numRows <= 30
思路分析
每行最后一个数字，右上方为空。所以，它必定是 1，可以单独添加，这样就不用判断右上角是否超过边界。
看题解，还发现另外一个解法：错位（每行前面补一个 0）相加，在每行前面补一个 0，在逐个相加。如下图：
-
一刷
-
二刷
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
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Pascal's Triangle.
*
* Memory Usage: 34 MB, less than 7.23% of Java online submissions for Pascal's Triangle.
*/
public List<List<Integer>> generate(int numRows) {
if (numRows < 1) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>(numRows);
result.add(Arrays.asList(1));
for (int i = 1; i < numRows; i++) {
List<Integer> parent = result.get(i - 1);
int length = parent.size() + 1;
List<Integer> current = new ArrayList<>(length);
current.add(1);
for (int j = 1; j < length; j++) {
int left = parent.get(j - 1);
int right = j >= parent.size() ? 0 : parent.get(j);
current.add(left + right);
}
result.add(current);
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-09 21:58:02
*/
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<>(numRows);
result.add(List.of(1));
for (int i = 1; i < numRows; i++) {
List<Integer> row = new ArrayList<>(i + 1);
row.add(1);
List<Integer> last = result.getLast();
for (int j = 1; j < i; j++) {
int left = last.get(j - 1);
// 最后一个数字，右上方为空，所以，
// 它必定是 1，可以单独添加，这样就少一个判断
int right = last.get(j);
row.add(left + right);
}
row.add(1);
result.add(row);
}
return result;
}