119.Pascal's Triangle II

Tags: Easy Array

Links: https://leetcode.com/problems/pascals-triangle-ii/

---

Given a non-negative index k where k ≤ 33, return the *k*th index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

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

---

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> res;
        if (rowIndex == 0) return {1};
        vector<int> pre = {1, 1};
        if (rowIndex == 1) return pre;

        for (int i = 2; i <= rowIndex; ++i) {
            res.resize(i + 1, 1);
            for (int j = 1; j < i; ++j) {
                res[j] = pre[j - 1] + pre[j];
            }
            pre = res;
        }
        return res;
    }
};

此种方法是利用一个pre数组来记录上一行的数，其实还可以继续精简代码，只利用一个数组来完成。

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> res(rowIndex + 1, 0);
        res[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            for (int j = i; j >= 1; --j)
                res[j] += res[j - 1];
        }

        return res;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Pascal's Triangle II.
Memory Usage: 8.5 MB, less than 90.32% of C++ online submissions for Pascal's Triangle II.

此种方法利用了组合数的公式： $$ C_n^i = C_{n -1 }^{i - 1} + C_{n -1}^ i $$ 所以更新的时候需要逆序更新。