LeetCode Problem: Pascal’s Triangle II

By | 2013 年 1 月 17 日

Follow the algorithm in LeetCode Problem: Pascal’s Triangle, we can simple return the required row from the result.
从上一个题的算法LeetCode Problem: Pascal’s Triangle,可以得到一个简单的方法就是,在上一题的基础上,最后返回需要的行即可。

But, we can optimize this to use constant extra space, even better than the required O(k) extra space in the problem description below.
题目要求最好能用O(k)的额外空间,但是我们可以做的更好,甚至只用常数的额外空间就好了。

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

Take the above two rows as example, we can see that, the element in the last row is only relative to the element above it and the one before the element above it. So we can generate the last row from the previous row in backward order in place.Thus, we do not need the extra spaces.
拿上面这两行为例,每一个元素其实只与它上面一个和左上那一个元素相关。也就是说,如果要生成元素的下标是i的话,它只和i和i-1相关。所以我们可以用从后往前的顺序原地生成后一行。这样就不用任何辅助空间了。



Pascal’s Triangle II Oct 29 ’12
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?



Code, 16ms pass large test set

class Solution {
public:
    vector getRow(int rowIndex) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector ret;
        if(rowIndex < 0) return ret;
        for(int ir = 0; ir <= rowIndex; ++ir) {
            //put an 1 at the end of this row
            ret.push_back(1);
            //handle the rest of elements backward
            for(int ic = ir - 1; ic > 0; --ic) {
                ret[ic] = ret[ic] + ret[ic - 1];
            }
        }
        return ret;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注