学步园

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Given an index k, return the k^th 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?

思路：

两道题其实可以一起解决。先解决第二个问题。以0为第一行的行号，Pascal三角下一行的第k个元素等于上一行第k-1个元素和第k个元素的和。如果k=0或者k大于上一行最后一个元素的序号，那么这个元素的值由0代替。综上，可以先初始化第0行，然后反复生成下一行即可。

第一个问题可以通过每生成一行，就保存这一行的数据来实现。

题解：

只给出第二个问题的解法。

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        // we use one extra position to store 0
        // this does not hurt as poping back
        // is almost free in std::vector
        vector<int> ret_triangle(rowIndex + 2);
        
        fill(begin(ret_triangle), end(ret_triangle), 0);
        ret_triangle[0] = 1;
        
        auto generate_pascal=[&ret_triangle]()->void 
        {
            int iter = 0;
            int left = 0;
            int right = ret_triangle[iter];
            
            while(right != 0)
            {
                ret_triangle[iter] = left + right;
                left = right;
                
                // the extra 0 is helpful when we deal with the last row of the triangle
                right = ret_triangle[++iter];
            }
            
            ret_triangle[iter] = left + right;
        };
        
        for(int i = 0; i < rowIndex; ++i)
            generate_pascal();
        
        // pop the unused position
        ret_triangle.pop_back();
        
        return ret_triangle;
    }
};