杨辉三角 II
题目
难度级别：简单
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 3 输出: 1,3,3,1
进阶：
你可以优化你的算法到 O(k) 空间复杂度吗？
解题思路
法一
解法与杨辉三角思路一样。
const getRow = function(rowIndex) {
let res = [1]
if (rowIndex === 0) return res
for (let j = 0; j < rowIndex; j++) {
const currentLine = [1]
const len = res.length
for (let i = 0; i < len; i++) {
if (i + 1 === len)
currentLine.push(1)
else
currentLine.push(res[i] + res[i + 1])
}
res = currentLine
}
return res
};法二
通过动态规划，因为当前元素的值等于他的左上角于右上角之和（除开左右2边元素），考虑到不占用额外空间，所以可以采用在杨辉三角前一位补零，然后每次遍历到的当前元素，就修改为当前元素索引与它的索引+1之和，最后一位不做遍历修改。
例：
[0,1,3,3,1], 第3层
[0+1,1+3,3+3,3+1,1] 第四层 即 [1,4,6,4,1]const getRow = function(rowIndex) {
let res = [1]
if (rowIndex === 0) return res
for (let j = 0; j < rowIndex; j++) {
res.unshift(0)
for (let i = 0; i < j + 1; i++) {
res[i] = (res[i] + res[i + 1])
}
}
return res
};题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/pascals-triangle-ii
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
