杨辉三角 II
难度:
标签:
题目描述
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3 输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0 输出: [1]
示例 3:
输入: rowIndex = 1 输出: [1,1]
提示:
0 <= rowIndex <= 33
进阶：
你可以优化你的算法到 O(rowIndex) 空间复杂度吗？
代码结果
运行时间: 19 ms, 内存: 16.1 MB
// 使用Java Stream的题解代码和注释
// 思路: 利用Java Stream的特性，我们可以通过流式操作来生成杨辉三角的每一行。
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SolutionStream {
public List<Integer> getRow(int rowIndex) {
return IntStream.rangeClosed(0, rowIndex)
.mapToObj(i -> comb(rowIndex, i))
.collect(Collectors.toList());
}
private int comb(int n, int k) {
long res = 1;
for (int i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return (int) res;
}
}解释
方法:
该题解采用动态规划的思路。通过观察杨辉三角的特点，可以发现每一行的数字都可以由上一行的数字计算得到。第 i 行的第 j 个数等于第 i-1 行的第 j-1 个数和第 j 个数之和。因此，可以通过迭代的方式，从第 0 行开始，逐行计算杨辉三角的每个数字，直到计算出第 rowIndex 行的数字。
时间复杂度:
O(rowIndex^2)
空间复杂度:
O(rowIndex)
代码细节讲解
🦆
在实现中，对于每一行的元素赋值时，使用`if j == 0 or j == i`分别处理首尾元素，这种处理方式是否有可能导致边界错误？例如，在特定的`rowIndex`下是否会有遗漏或重复赋值的情况？
▷🦆
考虑到`rowIndex`的最大值为33，当前算法在最大值输入情况下的处理效率如何？是否有必要考虑进一步优化？
▷🦆
该题解在描述中提到从第0行开始逐行计算杨辉三角的每个数字，是否有考虑从第`rowIndex`行直接开始逆向构建的可能性，这种方法是否可行？
▷