前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >杨辉三角 II

杨辉三角 II

作者头像
_kyle
修改2023-09-23 20:10:30
4570
修改2023-09-23 20:10:30
举报
文章被收录于专栏:kyle的专栏

题目

难度级别:简单

给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 3 输出: 1,3,3,1

进阶:

你可以优化你的算法到 O(k) 空间复杂度吗?

解题思路

法一

解法与杨辉三角思路一样。

代码语言:javascript
复制
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之和,最后一位不做遍历修改。

例:

代码语言:javascript
复制
 [0,1,3,3,1],  第3层
 [0+1,1+3,3+3,3+1,1] 第四层 即 [1,4,6,4,1]
代码语言:javascript
复制
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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
    • 示例:
    • 进阶:
    • 解题思路
      • 法一
        • 法二
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档