119.PascalsTriangleII.md

tags: Array

#[LeetCode 118] Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,

Return [1,3,3,1].

Note: Could you optimize your algorithm to use only O(k) extra space?

Diffculty Easy

Similar Problems [LeetCode 118] Pascal's Triangle E

Analysis

这道题仅需要得到的第 k 层的集合，而且只能使用 O(k) 的空间。因此只能使用一位数组滚动计算。 由于第 i 个元素等于上一行的 res[i] + res[i + 1]，因此我们在每一行，从后往前扫，相当于第 i 个元素是 res[i - 1] + res[i]。 时间复杂度依然是 O(N^2)，但是空间复杂度是 O(K)。

这里的遍历方式跟 [LeetCode 115] Distinct Subsequences 的一维滚动数组的遍历方式相似，都是从右往左遍历，以避免遍历过程中数据被修改。

Solutions

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        if (rowIndex < 0) return {};
        vector<int> res(rowIndex + 1);
        res[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            for (int j = res.size() - 2; j >= 0; --j)
                res[j + 1] += res[j];
        }
        res.back() = 1;
        return res;
    }
};

Reference