【Leetcode】Pascal's Triangle II

【Leetcode】Pascal's Triangle II

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

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?

思路:最简单的方法就是依照【Leetcode】Pascal’s Triangle 的方式自顶向下依次求解,但会造成空间的浪费。若仅仅用一个vector存储结果。在下标从小到大的遍历过程中会改变vector的值,如[1, 2, 1] 按小标从小到大累计会变成[1, 3, 4, 1]不是所求解,因此能够採取两种解决方法,简单的一种则是使用两个vector,一个存上一层的值。一个存本层的值,然后再进行交换。第二种方法则是按下标从大到小进行遍历,则会避免上述问题。

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117724.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • eureka集群高可用配置[通俗易懂]

    eureka集群高可用配置[通俗易懂]网上讲这个东西的很多,抄来抄去的,大部分类似,多数没讲明白为什么那么配置。譬如eureka.client.register-with-eureka和fetch-registry是否要配置,配不配区别在哪里;eureka的客户端添加service-url时,是不是需要把所有的eureka的server地址都写上,还是只需要写一个server就可以了(因为server之间已经相互注册了)?如果写上了所…

  • 商品管理系统_营销系统四大系统

    商品管理系统_营销系统四大系统题目:商品管理系统语言和环境实现语言Java环境要求JDK8,IDEA,Tomcat7,MySQL功能要求项目开发使用SSM(Mybatis+Spring+Springmvc)实现商品

  • linux mail发送邮件_linux命令行收发email

    linux mail发送邮件_linux命令行收发email一、mail命令1.配置 vim /etc/mail.rc文件尾增加以下内容 setfrom=1968089885@qq.com smtp=”smtp.qq.com”setsmtp-auth-user=”1968089885@qq.com”smtp-auth-password=”123456″setsmtp-auth=login说

    2022年10月20日
  • 16进制浮点数的表示方法

    16进制浮点数的表示方法16进制浮点数的表示方法,根据IEEE的标准,分为32位和64位两种,参数分别如下:             符号位     指数位           尾数位           指数偏移量 32位    1[31]    8[23-30]        23[0-22]          127  64位    1[63]    11[52-62]   

  • Python中range()函数的用法

    Python中range()函数的用法函数原型:range(start,end,scan):参数含义:start:计数从start开始。默认是从0开始。例如range(5)等价于range(0,5);end:技术到end结束,

  • CSP考试总结_考试总结300字

    CSP考试总结_考试总结300字t1模拟很难受,要加大这方面练习,要习惯用草稿理清思路t2和去年一样的东西,也是高精的坑,考前应该补一下高精t3比较正常,这种大数据结构只有考虑暴力,打正解很容易浪费时间并且上头t4无能

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号