专栏首页给永远比拿愉快Leetcode: Pascal's Triangle II

Leetcode: 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?

思路分析: 还是杨辉三角的问题。题目要求使用额外空间为O(k),则可以使用一个临时的vector保存上次计算的结果,然后迭代这计算最终结果。 最后注意index k是从0开始的。

C++参考代码:

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;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode: Reverse Integer

    Example1: x = 123, return 321 Example2: x = -123, return -321 题目提示: Have ...

    卡尔曼和玻尔兹曼谁曼
  • Leetcode: Binary Tree Level Order Traversal II

    Given a binary tree, return the bottom-up level order traversal of its nodes' va...

    卡尔曼和玻尔兹曼谁曼
  • Leetcode: Binary Tree Level Order Traversal

    Given a binary tree, return the level order traversal of its nodes' values. (ie,...

    卡尔曼和玻尔兹曼谁曼
  • Leetcode 118. Pascal's Triangle

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • 【leetcode】Plus One

    Given a number represented as an array of digits, plus one to the number.

    阳光岛主
  • Leetcode: Add Binary

    题目: Given two binary strings, return their sum (also a binary string).

    卡尔曼和玻尔兹曼谁曼
  • 医院时钟系统(子母钟系统)是智慧医疗的重中之重

    一、系统概述:随着人民生活水平的提高和我国医疗卫生事业的发展,人们对医疗水平的要求越来越高,国家也逐年加大对新建医院和现有医院改造的投资,尤其在医疗设施的更新、...

    NTP网络同步时钟
  • 从 PageRank Example 谈 Spark 应用程序调优

    在做PageRank测试时,发现有很多有趣的调优点,想到这些调优点可能对用户来说是普遍有效的,现把它整理出来一一分析,以供大家参考。

    涂小刚
  • 从 PageRank Example 谈 Spark 应用程序调优

    最近做了关于Spark Cache性能测试,开始是拿BigData-Benchmark中Spark KMeans来作为测试基准,分别测试各种Cache下应用程序...

    王知无
  • 从 PageRank Example 谈 Spark 应用程序调优

    场景描述:最近做了关于Spark Cache性能测试,开始是拿BigData-Benchmark中Spark KMeans来作为测试基准,分别测试各种Cache...

    暴走大数据

扫码关注云+社区

领取腾讯云代金券