leetCode 119. Pascal's Triangle II 数组

发布时间：2020-07-17 15:57:30 阅读：648 作者：313119992 栏目：编程语言

开发者测试专用服务器限时活动，0元免费领，库存有限，领完即止！点击查看>>

119. Pascal's Triangle II

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?

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> curVec;
        vector<int> nextVec;
        if(rowIndex < 0)
            return curVec;
        for(int i = 0;i <= rowIndex; i++)
        {
            for(int j = 0;j<=i;j++)
            {
                if(j == 0)
                    nextVec.push_back(1);
                else
                {
                    if(j >= curVec.size())
                        nextVec.push_back(curVec[j-1]);
                    else
                        nextVec.push_back(curVec[j] + curVec[j-1]);
                }
            }
            curVec.swap(nextVec);
            nextVec.clear();
        }
        return curVec;
    }
};

使用思路：

The basic idea is to iteratively update the array from the end to the beginning.

从后到前来更新结果数组。

参考自：https://discuss.leetcode.com/topic/2510/here-is-my-brief-o-k-solution

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

2016-08-12 10:46:10

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

向AI问一下细节

leetCode 119. Pascal's Triangle II 数组

猜你喜欢

最新资讯

相关推荐

开发者交流群：

相关标签