119. 杨辉三角 II
119. 杨辉三角 II
题目
Given an integer rowIndex
, return the rowIndexth
(0-indexed) row of the Pascal 's triangle.
In Pascal 's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3
Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0
Output: [1]
Example 3:
Input: rowIndex = 1
Output: [1,1]
Constraints:
0 <= rowIndex <= 33
Follow up: Could you optimize your algorithm to use only O(rowIndex)
extra space?
题目大意
给定一个非负索引 rowIndex
,返回「杨辉三角」的第 rowIndex
行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
提示:
0 <= rowIndex <= 33
进阶:
你可以优化你的算法到 O(rowIndex)
空间复杂度吗?
解题思路
杨辉三角的性质:
- 杨辉三角第
i
行的第j
个元素可以通过 前一行 的第j-1
和第j
个元素相加得到。arr[j] = arr[j] + arr[j-1]
- 每一行的第一个和最后一个元素永远是
1
。 - 第
k
行有k+1
个元素,索引从0
开始。
初始化数组 创建一个长度为
rowIndex + 1
的数组arr
,并将所有元素初始化为1
(因为每行的两端元素始终为1
)。遍历行数 从第 2 行开始(
i = 2
),因为第 0 行和第 1 行的元素都是1
。动态更新当前行 从索引
i - 1
到1
,逐步更新数组元素。从右向左更新数组,避免当前元素被覆盖,影响后续计算。返回结果 遍历完成后,
arr
就是第rowIndex
行的结果。
复杂度分析
- 时间复杂度:
O(rowIndex^2)
,需要两层遍历。 - 空间复杂度:
O(rowIndex)
,使用了一个数组arr
来保存计算过程和结果。
代码
/**
* @param {number} rowIndex
* @return {number[]}
*/
var getRow = function (rowIndex) {
// 初始化一个长度为 rowIndex + 1 的数组,所有元素为 1
let arr = new Array(rowIndex + 1).fill(1);
// 从第 2 行开始遍历,计算每一行的中间元素
for (let i = 2; i <= rowIndex; i++) {
// 从右向左更新数组,避免当前元素被覆盖
for (let j = i - 1; j > 0; j--) {
arr[j] += arr[j - 1];
}
}
// 返回第 rowIndex 行
return arr;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
118 | 杨辉三角 | [✓] | 数组 动态规划 | 🟢 | 🀄️ 🔗 |
2221 | 数组的三角和 | 数组 数学 组合数学 1+ | 🟠 | 🀄️ 🔗 |