LeetCode题解 | [简单-滚动数组] 119. 杨辉三角 II

119. 杨辉三角 II

题目

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

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

示例:

输入: 3
输出: [1,3,3,1]

进阶：

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

思路

使用滚动数组，即下一次的值由当前数组生成，同时存储于当前数组，只需要注意从右往左进行迭代，这样就不会影响后续值的生成。

代码

//2021/2/2
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> v;
        if (rowIndex == 0) {
            v.push_back(1);
        } else {
            v.push_back(1);
            v.push_back(1);
            if (rowIndex > 1) {
                for (int k = 2; k <= rowIndex; k++) {
                    for (int i = k-1; i > 0; i--) {
                        v[i] = v[i] + v[i-1];
                    }
                    v.push_back(1);
                }
            }
        }

        return v;
    }
};