首页 > 代码库 > Pascal's Triangle II

Pascal's Triangle II

2024-07-07 06:31:22   232人阅读

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?


从Pascal的定义可以知道第一行是一个1， 以后每行都可以有上一行的两个元素相加而得，如果我们这样来看
1
11
121
1331
。。。。

可以得到这样一个公式, 即每一个元素的值都自己头顶上的元素以及之前的一个元素之和: cur[i] = pre[i] + pre[i - 1]
由此可以直接得到下边的第二个方法，用两个数组来交替表示当前行和上一行，然后用上一行的值来算出当前行的值，时间复杂度是n*n, 空间复杂度是2*n.

时间复杂度上来说，除非用直接表示第n行的数学公式来算低n行的值，总是要n*n的复杂度； 那么空间复杂度呢？ 是不是2*n就是最好的呢（以及比native的n*n小很多了)？ 答案是肯定的，实际上从上边的公式可以看出，当前行的每一个元素都是只和上一行的两个元素有关，如果我们从后向前计算当前行的值，则可以直接在一个数组上完成计算，详见下边的方法1的代码。 

Note：返回值用move来减少一次vector copy的消耗，可以参见C++11的right value以及move forward相关概念。


class Solution {
public:
    vector<int> getRow(int rowIndex) {
        if (rowIndex < 0) {
            throw new invalid_argument("Index must not be negative");
        }
        
        // 1
        
        vector<int> ret(rowIndex + 1, 1);
        for (int i = 3; i <= rowIndex + 1; ++i) {
            for (int j = i - 2; j > 0; --j) {
                ret[j] += ret[j - 1];
            }
        }
        return move(ret);
        
        
        // 2
        /*
        vector<vector<int>> ret(2, vector<int>());
        int pre = 0, cur = 1;
        for (int i = 0; i <= rowIndex; ++i) {
            ret[cur].assign(i + 1, 1);
            for (int j = 1; j < i; ++j) {
                ret[cur][j] = ret[pre][j] + ret[pre][j - 1];
            }
            swap(pre, cur);
        }
        
        
        return move(ret[pre]);
        */
    }
};


联系
我们