LeetCode刷题实战2:用链表模拟加法

程序IT圈

共 2093字,需浏览 5分钟

 ·

2020-08-08 23:55


算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !


废话不多说,让我们一起来看看题目吧,今天要讲的是一道经典的算法题,虽然不难,但是很有意思,我们一起来看下题目:


You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. 

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

https://leetcode.com/problems/two-sum/


翻译


给定两个非空的链表,代表两个非负整数。这两个整数都是倒叙存储,要求返回一个链表,表示这两个整数的和。


样例

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.


解答


题目不难理解,思路也很容易想明白,其实就是模拟小学生打竖式计算加减的方法,来计算两个整数的加和。但是既然是加法,就可能涉及进位,比如两个两位数的和可能是一个三位数。还有一个难点是需要使用链表来实现,涉及链表,编码的复杂度会更大一些。


在开始编码之前,我们先仔细观察样例:



如果你熟悉C++ STL或者其他语言工具库的用法,想必应该很容易想到可以使用map。map是一个非常常用的容器,用来存储key-value格式的数据对。

我们发现,由于链表存储数字的顺序和常规的顺序相反,所以如果存在进位的情况,我们只需要在链表的结尾加上一个节点即可。通常的计算是从右往左,而在链表当中可以理解成从左往右,其实也就是按照链表遍历的顺序计算。这点想明白,并没有什么问题。

我们做一个总结,难点大概有三个:

1. 因为不是数组,所以我们无法拿到链表的长度。会出现两个链表长度不一致的情况
2. 返回结果也是一个链表,需要我们自己手动创建
3. 计算产生的进位处理

我们一个一个来分析,链表的长度未知很好处理,我们只需要判断当前节点的next节点是否为空,就可以知道链表后面是否还有后继。如果没有,那么就说明链表已经遍历到头了。

由于本题当中存在两个链表,我们需要同时判断它们是否结束:

while (l1 || l2) {    if (l1) l1 = l1->next;    if (l2) l2 = l2->next;}


手动创建链表也并不复杂,我们首先创建一个链表的节点,然后依次往节点后方插入节点即可。链表插入的方式也很简单,假设当前的节点是cur,待插入的节点是node,那么我们只需要用cur.next指向node,然后将cur赋值成node即可,如图:



cur->next = node;cur = node;


计算产生的进位问题就更简单了,由于我们是按位来计算加法,所以我们可以用一个变量标记之前位是否发生进位。如果发生,那么当前的计算结果加一。因为加法计算,最多的结果只能达到19(两位9再加上之前进位),所以进位最多只会增加1。最后,再判断一下当前位计算的结果是否产生进位即可。


int ret = l1->val + l2->val;if (exceed) ret++;if (ret > 9) {    ret -= 10;    exceed = true;}else exceed = false;


最后,我们只需要把上述说到的三点结合起来,就可以写出代码了。如果coding还是有困难,可以在公众号回复LeetCode2,获取代码。


还没有结束,在大多数语言当中,int都是有范围的。一般是32个二进制位,如果是int64则是64个二进制位。这是和计算机CPU的带宽是有关的,那有没有想过,超过64位二进制能表示的整数应该怎么办呢?


其实就是用类似本题当中的方法,通过链表将每一位串联起来,在计算加减乘除的时候,则是像人工打竖式那样去计算。这种算法称为高精度。感兴趣的同学,可以自行搜索,以后有机会,会在之后的文章里更新。


希望大家都能有所收获,如果喜欢本文,麻烦顺手转发或者点击下方“在看”。


上期推文:

LeetCode刷题实战1:在数组上遍历出花样



点个"
在看
",告诉我你曾来过
 
浏览 35
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报