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

LeetCode:Pascal's Triangle II

Given an index k, return thekth row of the Pascal‘s triangle.


For example, given k = 3,


Return [1,3,3,1].


Note:


Could you optimize your algorithm to use onlyO(k) extra space?


解题思路:


    由于计算杨辉三角时,只用到相邻的两行的数据,所以我们可以反向计算,就能以O(k)


的时间复杂度解决问题了.


解题代码:

class Solution {
public:
    vector<int> getRow(int rowIndex) 
    {
        vector<int> res;
        for (int i = 0; i <= rowIndex; ++i)
        {
            for (int j = i - 1; j > 0; --j)
                res[j] = res[j] + res[j-1];
            res.push_back(1);
        }
        return res;
    }
};