119. 杨辉三角 II

Introduction

Question: 119. 杨辉三角 II

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

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

示例:

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

进阶：

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

解法一

Analysis

与 LC118-pascals-triangle 几乎一致，修改部分代码即可。

Implement

vector<int> getRow(int rowIndex) {
    // vector<vector<int>> res;
    vector<int> prev;
    for(int i = 0;i <= rowIndex; i++) {
        // res.push_back(vector<int>(i + 1, 1));
        vector<int> vec(i+1, 1);
        for(int j = 1; j < i;j++) {
            // res[i][j] = res[i-1][j] + res[i-1][j-1];
            vec[j] = prev[j] + prev[j-1];
        }
        swap(prev, vec);
    }
    return prev;
}