草庐IT

【JS】2.两数相加

PaturNax 2023-03-28 原文

2.两数相加

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

提示:

  • 每个链表中的节点数在范围 [1, 100]
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

思路:

  1. 首先创建一个哑节点dummy,通过cur指针指向该哑节点,那么之后该cur指针的操作可用dummy.next来表示最终的链表结果
  2. 接着当任意一个链表不为空的情况下,对这两个链表当前节点的值进行相加,由于要注意到数值相加到10就要进一位的情况,所以要加个变量carry来取整除数和余数来辅助判断cur指向的下一个节点的值应该是多少
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode(null),
    cur = dummy,
    carry = 0;
    while(l1 != null || l2 != null){
        const l1Val = (l1!=null) ? l1.val : 0;
        const l2Val = (l2!=null) ? l2.val : 0;
        const sumVal = carry + l1Val + l2Val;
		//取整除数,不仅消除要超过10以上的数值影响,还可以判断是否要进一位到sumVal
        carry = Math.floor(sumVal/10);
        //取余数作为链表的下一个节点
        cur.next = new ListNode(sumVal % 10);        
        //cur向右移动
        cur = cur.next;
        
        if(l1){
            l1 = l1.next;
        }
        if(l2){
            l2 = l2.next;
        }
        //如果最后溢出1的话,就添加为1的节点即可。
        if(carry>0){
            cur.next=new ListNode(carry);
        }
    }
    return dummy.next;
};

复杂度分析

  • 时间复杂度:\(O(\max(m,n))\),其中 \(m\)\(n\) 分别为两个链表的长度。我们要遍历两个链表的全部位置,而处理每个位置只需要 \(O(1)\) 的时间。
  • 空间复杂度:\(O(1)\)。注意返回值不计入空间复杂度。

有关【JS】2.两数相加的更多相关文章

  1. ruby-on-rails - Assets 管道损坏 : Not compiling on the fly css and js files - 2

    我开始了一个新的Rails3.2.5项目,Assets管道不再工作了。CSS和Javascript文件不再编译。这是尝试生成Assets时日志的输出:StartedGET"/assets/application.css?body=1"for127.0.0.1at2012-06-1623:59:11-0700Servedasset/application.css-200OK(0ms)[2012-06-1623:59:11]ERRORNoMethodError:undefinedmethod`each'fornil:NilClass/Users/greg/.rbenv/versions/1

  2. ruby-on-rails - Rails - 理解 application.js 和 application.css - 2

    rails新手。只是想了解\assests目录中的这两个文件。例如,application.js文件有如下行://=requirejquery//=requirejquery_ujs//=require_tree.我理解require_tree。只是将所有JS文件添加到当前目录中。根据上下文,我可以看出requirejquery添加了jQuery库。但是它从哪里得到这些jQuery库呢?我没有在我的Assets文件夹中看到任何jquery.js文件——或者直接在我的整个应用程序中没有看到任何jquery.js文件?同样,我正在按照一些说明安装TwitterBootstrap(http:

  3. node.js - 如何在 Travis CI 上的一个项目中运行 Node.js 和 Ruby 测试 - 2

    我有一个包含多个组件的存储库,其中大部分是用JavaScript(Node.js)编写的,一个是用Ruby(RubyonRails)编写的。我想要一个.travis.yml文件来触发一个运行每个组件的所有测试的构建。根据thisTravisCIGoogleGroupthread,目前还没有官方支持。我的目录结构是这样的:.├──构建服务器├──核心├──扩展├──网络应用├──流浪文件├──package.json├──.travis.yml└──生成文件我希望能够运行特定版本的Ruby(2.2.2)和Node.js(0.12.2)。我已经有了一个make目标,所以maketest在每

  4. node.js - 从未编写过任何自动化测试,我应该如何开始行为驱动开发? - 2

    按照目前的情况,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visitthehelpcenter指导。关闭9年前。多年来,我一直在使用多种语言进行编程,并且认为自己总体上相当擅长。但是,我从未编写过任何自动化测试:没有单元测试,没有TDD,没有BDD,什么都没有。我已经尝试开始为我的项目编写适当的测试套件。我可以看到在进行任何更改后能够自动测试项目中所有代码的理论值(value)。我可以看到像RSpec和Mocha这样的测试框架应该如何使设置和运行所述测试变得相当容易

  5. ruby-on-rails - 将 Angular JS 与 Rails 集成 - 2

    我需要一些指导来了解如何将Angular整合到rails中。选择Rails的原因:我喜欢他们偏执的做事方式。还有迁移,gem真的很酷。使用angular的原因:我正在研究和寻找最适合SPA的框架。Backbone似乎太抽象了。我不得不在Angular和Ember之间做出选择。我首先开始阅读Angular,它对我来说很有意义。所以我从来没有去读过关于ember的文章。使用Angular和Rails的原因:我研究并尝试使用小型框架,例如grape、slim(是的,我也使用php)。但我觉得需要坚持项目的长期范围。我个人喜欢用Rails的方式做事。这就是我需要帮助的地方,我在Rails4中有

  6. node.js - 如何比较图像并确定哪个内容更多? - 2

    目标:我想从动画GIF中抓取最佳帧并将其用作静态预览图像。我相信最好的帧是显示最多内容的帧-不一定是第一帧或最后一帧。以这张动图为例:--这是第一帧:--这是第28帧:很明显,第28帧很好地代表了整个GIF。我如何以编程方式确定一帧是否比另一帧具有更多像素/内容?如果您能向我指出任何想法、想法、包/模块或文章,我们将不胜感激。 最佳答案 实现此目的的一种直接方法是估计entropy每个图像的帧,并选择具有最大熵的帧。在信息论中,熵可以被认为是图像的“随机性”。单一颜色的图像是非常可预测的,分布越平坦,越随机。这与Arthur-R描述

  7. css - Less.js LoadError - 没有这样的文件要加载 - less 在 main .less 文件上 - 2

    我正在尝试在一个新元素中测试less.js。我100%确定javascript文件加载正常,但我的css文件夹中的less文件一直出现此错误。我打算在启动之前使用less.app编译它,但我宁愿让less.js在开发期间进行编译。由于它是.less或其他文件而不允许浏览器访问该文件是否存在问题?谢谢(运行ubuntu11.04和ruby​​v1.9.2,在firefox和chrome中同样的错误)这是我的head.haml文件,我在其中链接到less.js和app.less(它们都在正确的文件夹中)%link{:rel=>"stylesheet/less",:type=>"text/c

  8. ruby - I18n::InvalidLocaleData:I18n gem 在 js 导出中有问题 - 2

    我正在OSX10.13.4上使用Rails3.2.22.4、Ruby2.2.7开发一个应用程序。有多个翻译文件,例如。en.yml,sq.yml基于国家。从下面的ruby​​mine执行命令时,加载网页时出现错误。rake--tracei18n:js:export来自en.yml的yaml内容已经过验证并且是正确的。从文件中删除后引发错误的特定行将在其他一些.yml文件中给出错误。正在使用当前版本的gemi18n(0.9.5)。Rails服务器启动但加载Web应用程序第一页时因同样的错误而中断。代码遇到i18n翻译代码时抛出错误,当错误从一个文件转移到另一个文件时,yml格式不是问题。

  9. ruby - 将 Ember.js 与简单的 Sinatra 后端集成 - 2

    有很多文档介绍如何构建和创建以Rails作为后端的Ember.js应用程序。流行的解决方案是使用gems作为ember-rails和ember-source或合二为一的ember-appkit-rails。但是我正在尝试创建一个简单的Sinatra应用程序,该应用程序以Ember.js作为前端来处理仅JSON后端。我发现的少数资源似乎有点过时,所以我正在寻找简单的方法来做到这一点。所以我的问题是:我如何将Ember.js与简单的Sinatra后端集成?如何执行此操作的示例将不胜感激。 最佳答案 有一个verysimplerepoon

  10. ruby - 如何在 Node.js/RoR 中监控 20 个网站(Ping 或 HTTP)的正常运行时间 - 2

    每5分钟(例如)ping20个网站的列表以了解该网站是否响应HTTP202的最佳方法是什么?最简单的想法是将20个URLS保存在数据库中,然后运行数据库并对每个URL执行ping操作。但是,当一个人不回答时会发生什么?之后的人会怎样?此外,是否有更好但更简单的解决方案?恐怕该列表会增长到20000个网站,然后没有足够的时间在我需要ping的5分钟内全部ping通它们。基本上,我是在描述PingDom、UptimeRobot等的工作原理。我正在使用node.js和RubyonRails构建这个系统。我也倾向于使用MongoDB来保存所有ping和监控结果的历史记录。建议?非常感谢!

随机推荐