119. Pascal's Triangle II

Given a non-negative index k where k ≤ 33, return the kth 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?

思路

思路和上一题一样，只不过这里不需要存每一行的数据。

注意：和上一题相比，这里的 rowIndex + 1 = numRows

C++11

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

ac结果：

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

Update 2019.03.07

思路一致，和之前写的代码差不多，区别在于之前是直接对res初始化赋值，分配好内存了，现在是通过追加的方式。理论上来说，之前提前分配内存的方法更有效率，后一种代码更简洁。

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

ac结果：

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