Leetcode刷题练Python – 两数相加

题目:两数相加(中等难度)

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

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

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

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807


 

知识点:单向链表

这道题看似是做加法,其实是考察对单向链表的操作能力。首先,我们要看看什么是单向链表。乍一看它跟Python的列表跟相似,其实它有很多不同于列表的特点:

  • 链表的链接方向是单向的;

  • 对链表的访问要通过从头部开始,依序往下读取;

  • 不能像列表那样通过角标访问元素;

  • 不能向上访问链表,只能单向向下读取;列表前后访问很方便。

 

链表的是由一个个节点链接在一起的,每个节点有两部分:

  • 第一部分是节点本身的信息;

  • 第二部分是下一个节点的信息。

这个结构如下图所示:

Leetcode刷题练Python - 2. 两数相加

链表的结束就是next的值为空(NULL)。到此为止,我们就可以根据单向链表的结构来遍历它了,伪代码如下:

Leetcode刷题练Python - 2. 两数相加

用一个节点指针p指向当前节点,如果p不为空则说明当前节点有值,打印该值,然后让p指向当前节点的next,循环往复,直到p为空也就到了链表的尾部,整个链表就遍历完。

 

解题思路

了解完单向链表,我们再来看看题目。这道题其实就是实现我们小学学的加法运算:从个位开始,按位相加,满十进一。题目的加数和被加数用链表表示,为什么要用链表表示呢?我们知道,计算机中的整数位数是有限制的,比如C语言中无符号32位二进制整数(unsigned int)最大是2的32次方,64位的是2的64次方,直接两个int相加有可能出现溢出,比如32为整数就不能表示 (2**32 – 1) +  2 这两个数的和。而用链表表示就可以实现任意位数的加法。

 

但是,Python里面的整数可以很大,到底有多大呢?查了一圈得出结论,基本上确定跟你的内存有关系,你的内存足够大,它的整数就足够大。Python的大整数(bignum)就是C语言实现的突破了int_32, int_64限制的结构体。

 

大致估算一下 1GB 内存可以表示多大的整数呢? 1GB 也就是2**30字节,每个字节有8位,一共可以有 2**30 * 8 位(bit) 也就是 8589934592,除去结构体占用些内存,去个零头就算 8000000000,那么这么多二进制位可以表示的整数就是 2**8000000000 这么大!! 虽然你的内存远远超过了1GB,但是我劝你不要用Python执行下面这条语句:

print(2**8000000000)

 

在Python里,你可以轻易得到 2**1000000 即 2 的100万次方这个整数(有轻微卡顿,它要算一下),但是一屏占不下,只好接了个 2 的一万次方的图给大家感受一下“大数”:

Leetcode刷题练Python - 2. 两数相加

既然Python可以支持“无限大”的整数,于是就有了这个思路:

 

思路一:(奇葩型思路)链表 -> 整数相加 -> 链表

(1)分别把两个链表转换成整数,无论链表多长都可以转换为整数(别超过内存),这个转换算法也有两种:

(a)把链表转换为字符串,字符串再转换成整数:

(1->2->3->4) -> ‘1234’ -> ‘4321’ -> 4321

(b)链表按位相加直接转换为整数:

(1->2->3->4) -> 1 + 2*10 + 3*100 + 4*1000 -> 4321

 

(2)两个整数相加,把和变为链表返回。

有兴趣的童鞋可以实现一下这个思路,主要是练习链表的遍历、字符串反转、字符串转换为链表这几项。

 

这个思路利用了Python支持大整数的特点。其实这个题目也可以引申一下,“求两个数字字符串表示的整数的和,返回和的字符串”,这个引申可以直接利用这个奇葩思路,当然出题者的初衷应该不在于此。

 

可能出题者认为下面的思路才算比较正常的:按位相加,满十进一。

 

 

 

思路二:(正常型思路)按位相加,满十进一

这个思路很正常,不做过多解释,直接看代码:

Leetcode刷题练Python - 2. 两数相加

代码优化方面,20-22行可以替换为:

 carry, val = divmod(v1+v2+carry, 10) 

后来看到别人写的更简短的代码,思路一样,行数更少(9行):

Leetcode刷题练Python - 2. 两数相加

 

 

 

思路三: 思路二的进阶,支持多个数(不止两个)相加

Leetcode刷题练Python - 2. 两数相加

估计你已经看出它和思路二的不同了,它用来一个list把加数包装起来,循环中,下一个节点为空就不再放入list,这样当list为空时加数就都遍历到尾部了,循环也就结束。这个“用list封装”的点,可以支持多个链表相加,不管是10个还是100个,都放到list里面去既可以了。

 

在leetcode上刷题,同一段代码,不同时间提交,测试结果有时候会相差很多,不知道有没有童鞋遇到同样的现象?有可能是服务器的“忙”或“闲”导致的吧,这个不用太计较。要计较的是,不同实现方法带来的效率的不同。

未经允许不得转载:996ICU » Leetcode刷题练Python – 两数相加

赞 (0) 打赏