原题地址：杨辉三角 II
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 3
输出: [1,3,3,1]
进阶：
你可以优化你的算法到 $O(k)$ 空间复杂度吗？
解答
与 前一题 的求解思路一致，只是因为只需要返回第k行，所以我们也不用保存整个杨辉三角，只用保存上一行的值即可。
具体的实现如下：
/**
* @param {number} rowIndex
* @return {number[]}
*/
const getRow1 = function(rowIndex) {
// 与上一题不同，本题的行数是从0开始计算的
// 第0行只有一个1
let result = [1];
// 从第1行开始处理
for (let i = 1; i <= rowIndex; i ++) {
// 第i行的长度为i+1，左右两边的值为1
let array = new Array(i + 1).fill(1);
// 处理除两端外剩余的值
for (let j = 1; j < i; j ++) {
// 等于上一行左右两边的值之和
array[j] = result[j - 1] + result[j]
}
// 保存当前行用于计算下一行
result = array;
}
return result;
};
测试：
let start = new Date();
const test = getRow1;
console.log(test(0)); // [ 1 ]
console.log(test(3)); // [ 1, 3, 3, 1 ]
console.log(test(5)); // [ 1, 5, 10, 10, 5, 1 ]
console.log(new Date().getTime() - start.getTime()); // 10
时间复杂度： 与前一题相同，时间复杂度为$O(K^2)$
空间复杂度： 不用保存整个杨辉三角，只用保存一行，空间复杂度为$O(K)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Sep 17,2019