☆打卡算法☆LeetCode 119. 杨辉三角 II 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个非负索引 rowIndex ，返回 杨辉三角的第 rowIndex 行。”

题目链接：

来源：力扣（LeetCode）

链接： 119. 杨辉三角 II

2、题目描述

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex **行。

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

示例 1：
输入: rowIndex = 3
输出: [1,3,3,1]

示例 2：
输入: rowIndex = 0
输出: [1]

二、解题

1、思路分析

上一题是根据行数，生成「杨辉三角」的前 numRows 行。

这一题是根据行数，返回「杨辉三角」的第 rowIndex 行。

解法基本一致都是根据「杨辉三角」的性质，一行一行的计算杨辉三角。

2、代码实现

代码参考：

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;
    }
}

3、时间复杂度

时间复杂度 ： O(rowIndex²)

空间复杂度： O(1)

不考虑返回值的空间占用，只需要常数级的空间复杂度。

三、总结

注意到对第 i+1i+1 行的计算仅用到了第 ii 行的数据，因此可以使用滚动数组的思想优化空间复杂度。