杨辉三角
难度:
标签:
题目描述
给定一个非负整数 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
代码结果
运行时间: 15 ms, 内存: 15.9 MB
// Java Stream Solution for generating Pascal's Triangle
// Approach:
// 1. Use a list of lists to represent the triangle.
// 2. Use Stream.iterate to create each row.
// 3. Use a nested stream to generate each element of a row by summing elements from the previous row.
// 4. Collect the results into a list of lists.
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class PascalTriangleStream {
public List<List<Integer>> generate(int numRows) {
return Stream.iterate(
List.of(1),
row -> Stream.concat(
Stream.of(1),
IntStream.range(0, row.size() - 1)
.mapToObj(i -> row.get(i) + row.get(i + 1))
).collect(Collectors.toList())
).limit(numRows).collect(Collectors.toList());
}
}解释
方法:
这个题解采用了动态规划的思路。从第二行开始，每一行的数字都等于上一行相邻两个数字之和。具体来说，从第二行开始，每行的第一个和最后一个数字都是1，中间的每个数字等于上一行它左右两个数字之和。在编码实现时，用一个二维列表 ans 来保存结果，其中 ans[i] 表示第 i 行的数字。从第二行开始，每次遍历当前行的每个位置，如果是第一个或最后一个位置，直接添加1；如果是中间位置，将上一行左右两个位置的数字相加得到当前位置的数字。
时间复杂度:
O(numRows^2)
空间复杂度:
O(numRows^2)
代码细节讲解
🦆
为什么杨辉三角的每行第一个和最后一个数字总是1？
▷🦆
在题解中提到的动态规划方法中，有没有可能出现数组访问越界的问题？比如在尝试访问上一行不存在的元素时。
▷🦆
题解中提到了从第二行开始遍历，这种方法是否考虑了numRows为1的特殊情况？
▷