首页 > 其他 > 详细

LeetCode:Pascal's Triangle II

时间:2014-06-22 21:30:14      阅读:407      评论:0      收藏:0      [点我收藏+]

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?


解题思路:


    由于计算杨辉三角时,只用到相邻的两行的数据,所以我们可以反向计算,就能以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;
    }
};



LeetCode:Pascal's Triangle II,布布扣,bubuko.com

LeetCode:Pascal's Triangle II

原文:http://blog.csdn.net/dream_you_to_life/article/details/32715163

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!