[LeetCode] 每日一题 119. 杨辉三角 II
题目链接
题目描述
给定一个非负索引 rowIndex
,返回「杨辉三角」的第 rowIndex
行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
示例输入
示例 1
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2
输入: rowIndex = 0
输出: [1]
示例 3
输入: rowIndex = 1
输出: [1,1]
提示
0 <= rowIndex <= 33
解题思路
题目要求返回杨辉三角的第 rowIndex
行。杨辉三角的特点是:每个位置的数字是其左上方和右上方两个数字之和。对于第 rowIndex
行的数字,可以通过 组合数公式 来计算
组合数公式的定义:第
rowIndex
行的第m
个元素等于C(rowIndex, m)
初始值
C(rowIndex, 0) = 1
,接着根据公式依次计算每个元素
这样我们可以在 O(rowIndex) 时间内计算出所有的元素,并避免使用额外空间
代码实现
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> row = new ArrayList<Integer>();
row.add(1);
for (int i = 1; i <= rowIndex; ++i) {
row.add(0);
for (int j = i; j > 0; --j) {
row.set(j, row.get(j) + row.get(j - 1));
}
}
return row;
}
}
复杂度分析
时间复杂度:O(rowIndex)
线性遍历从 0 到
rowIndex
,每一步计算组合数所需时间为常数,因此时间复杂度为 O(rowIndex)
空间复杂度:O(rowIndex)
结果列表
row
占用的空间为 O(rowIndex)
总结
本题通过 线性递推 的方式,利用组合数公式高效地求解杨辉三角的第 rowIndex
行。代码简单且易于理解。与其他构造整个杨辉三角的解法相比,这种方法显著减少了时间和空间开销,非常适合只需要返回单行结果的场景
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。
License:
CC BY 4.0