0119._Pascals_Triangle-II.md

119. Pascal's Triangle II

难度：Easy

内容

题目链接：https://leetcode.com/problems/pascals-triangle-ii/description/

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

代码

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;
    }
};

来源：https://github.com/xiaqunfeng/leetcode