119. Pascal's Triangle II.md

119. Pascal's Triangle II

思路

类似第118题，不过这里要求只输出第rowIndex行，而且尽量使用O(k)的空间。
我们可以依次迭代计算第0、第1...第rowIndex行结果，这是最外层循环，
在得到第i-1行结果时，可以从前往后依次更新数组里的值来得到第i行的结果，这是内层循环。
注意用一个pre来记录第i-1行里面第j个元素的前一个元素的值。

C++

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