前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode: Pascal's Triangle II

Leetcode: Pascal's Triangle II

作者头像
卡尔曼和玻尔兹曼谁曼
发布2019-01-22 17:26:37
3080
发布2019-01-22 17:26:37
举报
文章被收录于专栏:给永远比拿愉快

题目: 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),则可以使用一个临时的vector保存上次计算的结果,然后迭代这计算最终结果。 最后注意index k是从0开始的。

C++参考代码:

代码语言:javascript
复制
class Solution
{
public:
    vector<int> getRow(int rowIndex)
    {
        vector<int> result;
        if (rowIndex < 0)
        {
            return result;
        }

        result.push_back(1);
        if (rowIndex == 0)
        {
            return result;
        }

        result.push_back(1);
        if (rowIndex == 1)
        {
            return result;
        }

        vector<int> previous;
        vector<int>::size_type size;

        for (int i = 2; i <= rowIndex; i++)
        {
            previous = result;
            size = previous.size();
            result[0] = 1;
            for (vector<int>::size_type j = 1; j < size; j++)
            {
                result[j] = previous[j - 1] + previous[j];
            }
            /*
            这里我原来写的语句是result[size] = 1;可是结果一直不对,后来调试发现vector下标越界。
            我想可能英文是上一次循环结果result的下表最大为size-1,我这里使用下标size,vector不会动态申请空间。
            所以最后结论是使用push_back()方法,vector就可以动态申请空间了。
            */
            result.push_back(1);
        }
        return result;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015年03月08日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档