LeetCode 119. Pascal's Triangle II

题目

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?

思路

交替使用两个数组即可。

代码

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        rowIndex++;
        if(rowIndex < 1){
            return vector<int>();
        }
        vector<int> temp0(rowIndex, 0);
        vector<int> temp1(rowIndex, 0);
        vector<int>* pCurrRow = &temp0;
        vector<int>* pLastRow = &temp1;
        for(int i=0; i<rowIndex; i++){
            (*pCurrRow)[0] = 1;
            for(int col=1; col<=i; col++){
                (*pCurrRow)[col] = (*pLastRow)[col-1] + (*pLastRow)[col];
            }
            vector<int>* pTemp = pLastRow;
            pLastRow = pCurrRow;
            pCurrRow = pTemp;
        }
        return (*pLastRow);
    }
};