文档章节

算法实战(二)两数相加

o
 osc_g8254g7s
发布于 2019/08/19 23:15
字数 882
阅读 0
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

一.前言

  今天开始第二题,有句话写给自己也写给大家,Rome wasn’t built in one day!算法很难,刷题的过程也很痛苦,但是只要我们能坚持下去,以后的收获将会是巨大的。希望我们都能够坚持下去,人人都能成为大神。

二.题目

  题目:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

     如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

  示例:输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)

     输出:7 -> 0 -> 8

       原因:342 + 465 = 807

三.解题思路

  这道题的解题思路其实十分明确,从两个链表的头开始相加,结果保存在新链表中。有两点要注意的,一个是就是要注意有进位的情况出现,所以我们需要定义一个全局变量来表示本次计算是否产生了进位。另外一点就是要考虑链表不等长的情况,容易出现空指针异常。话不多说,代码如下:(为了防止有人看不懂,注释写的很仔细,请大家见谅

  

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 class Solution {
10     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
11         //创建一个新的链表用于保存相加之后的结果
12         ListNode result = new ListNode(0);
13         //创建一个指针,用来指向当前所在的节点
14         ListNode cur = result;
15         //创建一个全局变量,用来表示本次计算是否产生进位,初始值为0
16         int advance = 0;
17         //只要两个链表有一个不为空,就会一直循环,跳出循环时,表示两个链表都已经走完,则计算完毕
18         while(l1 != null || l2 != null){
19             //定义sum变量,用来保存两数相加(包含上一次计算所产生的进位)的结果
20             int sum;
21             //根据链表长度,sum的值可分为三种结果
22             if(l1 != null && l2 != null){
23                 sum = l1.val + l2.val + advance;
24             }else if(l1 != null){
25                 sum = l1.val + advance;
26             }else{
27                 sum = l2.val + advance;
28             }
29             //sum如果超过了10,则要产生进位
30             if(sum >= 10){
31                 sum -= 10;
32                 advance = 1;
33             }else{
34                 advance = 0;
35             }
36             //l1指向下一个节点
37             if(l1 != null){
38                 l1 = l1.next; 
39             }
40             //l2指向下一个节点
41             if(l2 != null){
42                 l2 = l2.next;
43             }
44             //将本次计算结果,保存在当前节点中
45             cur.val = sum;
46             //判断是否两个计算链表都为空
47             if(l1 == null && l2 == null){
48                 //如果两个链表为空,但是本次计算产生了进位,那么进位就作为下一个节点的值
49                 //如果没有产生进位,则表示计算结束,当前节点为最后节点,直接跳出循环
50                 if(advance != 0){
51                     cur.next = new ListNode(advance);
52                 }
53                 break;
54             }
55             //只要还有一个计算链表不为空,就表示还会有计算结果,所以cur要继续往下走
56             cur.next = new ListNode(0);
57             cur = cur.next;
58         }
59         //计算结束,返回结果链表
60         return result;
61     }
62 }

    这是我的解法,如果大家有更好的思路和算法,欢迎和我分享,谢谢!

   

o
粉丝 0
博文 499
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

程序员职场:拥有一个学位将会在你的职业生涯中更加顺利!

1、作为程序员为什么要拥有学位? 很多情况下,作为程序员,学位是进入大公司的敲门砖。 现在很多大的科技公司,学位是硬性要求。 一般都是本科以上的学历,甚至有的必须是硕士以上学历。 如...

IT技术分享社区
03/03
7
0
varchar和nvarchar有什么区别? - What is the difference between varchar and nvarchar?

问题: Is it just that nvarchar supports multibyte characters? 只是nvarchar支持多字节字符吗? If that is the case, is there really any point, other than storage concerns, to us......

技术盛宴
24分钟前
5
0
用flutter给图片加个好看的遮罩层【flutter20个实例之六】

一、老套路,先看样式 左起图一是我业务中的样式,左起图二、三是下方源码展示样式(复制可直接运行,无额外组件引入) 二、讲解 1.结构拆分 我们先看下页面布局结构,首先肯定是有个GridVie...

一代码农码一代
25分钟前
9
0
世界上最美的瀑布在这里,太美了!

亲近大自然,高山流水遇知音,倾听心灵的声音。。。 声明:文章及图片、视频来自网络,如有版权方面的疑问请和我们联系,我们将在24小时内删除。 本文分享自微信公众号 - Python提升课堂(DJXY0...

花儿开放
2014/08/17
0
0
商城小程序制作流程

随着商城小程序的火爆,很多商家都迫不及待的想制作商城小程序,下面就和大家分享一下商城小程序制作流程? 第1步: 注册并认证小程序账号 注册并认证小程序账号,打开百度搜索,“微信公众平...

木鱼小铺小程序1
36分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部