Pascal's Triangle II

leetcode

原题链接

题意

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

思路：

1 这道题比较简单，属于基础的数组操作.
基本思路是每层保存前一行的指针, 然后当前航数据根据上一行来得到, 每个元素就是上一行两个相邻元素相加（第一个和最后一个元素是1）, 然后返回rowIndex行. 但是这种做法空间存储不是O(k)的, 看代码中的getRow2方法.

2 要使存储空间是O(k)的话, 那么就需要注意到rowIndex的奇妙之处了, rowIndex既可以代表第rowIndex行, 也可以代表第rowIndex行的rowIndex元素. 同理(rowIndex - 1)既可以代表第(rowIndex - 1)行, 也可以代表第(rowIndex - 1)行的(rowIndex - 1)元素. 另外可以modify/refresh实际的存储空间, 如getRow方法中的res数组, 所以可以做到存储空间为O(k)的, 具体看getRow方法.

。

code

class Solution {
public:
    // can modify res itself
    vector<int> getRow(int rowIndex) {
        if(rowIndex < 0) return vector<int>();
        vector<int>res(rowIndex + 1, 1);
        // i: index of layer/row
        for(int i = 1; i <= rowIndex; i++) {
            // j: index of element of i-th layer and (i-1)-th layer
            for(int j = i - 1; j >= 1; j--) {
                res[j] = res[j] + res[j - 1];
            }
        }
        return res;
    }
    // 
    vector<int> getRow2(int rowIndex) {
        vector<vector<int> > res;
        if(rowIndex < 0) {
            vector<int> zeroArr;
            return zeroArr;
        }
        vector<int> firstArr;
        firstArr.push_back(1);
        res.push_back(firstArr);
        if(rowIndex == 0) {
            return firstArr;
        } 
        for(int i = 1; i <= rowIndex; i++) {
            res.push_back(nextRow(res[i - 1]));
        }
        return res[rowIndex];
    }
    vector<int> nextRow(const vector<int>& pre) {
        int len = pre.size();
        vector<int> next(len + 1);
        next[0] = next[len] = 1;
        for(int i = 1; i < len; i++) {
            next[i] = pre[i - 1] + pre[i];
        }
        return next;
    }
};