Python 版 LeetCode 刷题笔记 #2 两数相加
Python 版 LeetCode 刷题笔记 #2 两数相加
今天的题目难度是中等，由于之前没接触过链表，看完题目一脸懵逼。Python 语法里哪有这个？这个自定义的 ListNode 要怎么用？在完成了整个计算过程后，我仍是花了一段时间琢磨明白如何正确返回这个类型。
题目
中文题目
第 2 题 两数相加：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807英文题目
Question 2 Add Two Numbers: 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.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.思路
题目内容还是容易理解的，输入两个所谓的链表 2->4->3 和 5->6->4，按照计算规则我们得到 7->0->8 就可以了。问题是这个链表要如何表示？Python 中也没有链表这个概念和结构，是要自己定义吗？尤其是看到答题区默认的格式：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:先看注释部分，这是对单个 ListNode 类的一个定义，其中有 val 和 next 属性表示该节点的值和链表的下一个值。拿我们题目中的 2->4->3 来说，2 是一个 ListNode，它的值 val 是 2，它的 next 是下一个 val 值为 4 的 ListNode；然后 val 值为 4 的 ListNode 的 next 值又是 val 值为 3 的 ListNode。这样所谓的链表就是一串相连的 ListNode。
再看我们要来完善的函数 addTwoNumbers，根据其后元信息也表明，输入的是两个 ListNode 实例，返回的也是一个 ListNode。也就是在我们能拿到结果 7 0 8 后，也要把它转化为这么一个 ListNode 才可以。
具体到计算过程，我们要提取出 243 和 564 来计算结果，最初的思路就是按照其规则，将 243 和 564 分别逆向得到 342 和 465 计算出和 807，再将结果逆向成 708 最终转化为 ListNode 即可。涉及到三位数的计算，为了方便，我们可以采用将数字转化为字符串 "243", 然后对其[::-1] 即可获取逆向的字符串了：
test="243"
target = test[::-1] # target = "342"此外，既然题目中为我们定义了 ListNode，那么我们就要利用 ListNode 的属性来获取我们想要的数据，比如输入的 l1，我们可以通过 l1.val 获取到第一位数字 2，l1.next 获取到第二位 ListNode，再通过其 val 获取到数字 4，逐渐完成我们的整个计算。
代码
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# 按照思路，将输入的 ListNode 全链转化为字符串
l1_str=""
# 通过 while 循环，将 ListNode 全链中的值都拼接到我们建立的字符串中
while l1!=None:
l1_str+=str(l1.val)
l1=l1.next
# 此时 l1_str 是"243"，我们要将其转化为 l1_val 342
l1_val = int(l1_str[::-1])
# 同样的思路对 l2 也来一遍
l2_str=""
while l2!=None:
l2_str+=str(l2.val)
l2=l2.next
# 获取到最终的 l2_val 为 465
l2_val = int(l2_str[::-1])
# 计算得到和 807
result = l1_val+l2_val
# 将和转化成字符串并逆向，得到结果字符串"708"
result_str = str(result)[::-1]
# 接下来要将"708" 转化成 7->0->8 的链表，首先第一位是值为 7 的 ListNode
answer = ListNode(int(result_str[0]))
# 这里 body 用来放到之后的 for 循环中不断获取之后的 next 节点
body = answer
# 第一位 "7" 已经拿到了，接下来的范围就是第二位、也就是字符串的索引 1 开始
for i in range(1,len(result_str)):
# 继续下一位 ListNode 的定义
temp = ListNode(int(result_str[i]))
# 如果不是最后一位的话，该 ListNode 的 next 就是下一位的 ListNode
if i<len(result_str)-1:
temp.next = ListNode(int(result_str[i+1]))
# 刚定义完的 ListNode 就是我们结果的 next
body.next = temp
# 为了让结果的每一位相连，将下一位赋值给 body，以在循环中继续获取下下位
body = body.next
# 通过 body 在 for 循环里的更新，后面每一位相连
# 要返回的只是整个链表的第一位 ListNode 即最初定义的 answer
return answer提交答案
刚我们分析过提交区域对 ListNode 的定义，按照这个形式呢估计 LeetCode 后台是对相关输入返回的链表有单独的格式定义来检测，这些我们也不用理会，编辑完函数直接提交，我们可以得到自己代码运行的测评结果：
中文区结果：
执行用时 :128 ms, 在所有 Python3 提交中击败了5.53%的用户 内存消耗 :13.7 MB, 在所有 Python3 提交中击败了5.07%的用户
英文版结果：
Runtime: 80 ms, faster than 17.02% of Python3 online submissions for Add Two Numbers. Memory Usage: 14.1 MB, less than 5.67% of Python3 online submissions for Add Two Numbers.
同样的代码在不同分区提交，数据差异还是有的：执行时间估计和服务器所在地有关吧，目前我在香港，用英文版的执行时反倒更快些；但这个击败用户比例，心痛，看来还要继续优化啊。
优化
结合着推荐答案与评论区，尝试了下在刚刚的思路上优化，我刚代码中两个 while 循环遍历输入的两个链表，最后又一个 for 循环来来生成结果链表，而这三个循环过程实际上可以做到逐位对应，也就是遍历过程可以放到一起。但如果这么来，我之前的代码就要重写，因为我是利用字符串来对链表进行逆转、计算的。
同时，也尝试了下把字符串换成列表、或直接转化为多位数来优化计算过程，反倒出现特殊情况要去处理，于是决定先不考虑了，集中精力尝试下逐位计算这个思路。
这里借用推荐答案中的图来展示下思路：
思路展示 图片、答案思路来源： https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/
我们将跟踪逐位计算过程，逐位相加满 10 取余数作为结果，并进位 1 给下一节点相加，逐位将结果连为链表。
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# 给要返回的链表建个表头，这样通过 answer.next 即可拿到要返回的链表
answer=ListNode(0)
# body 用于代入后续的 while 循环不断连接后续的链表节点
body = answer
# 进位默认为 0
carry = 0
# 将 l1 和 l2 循环二合一
while l1!=None or l2!=None:
# 利用 Python 中的三元表达式简化取值过程
x = l1.val if l1!=None else 0
y = l2.val if l2!=None else 0
# 结果要加上进位
sum_val = x + y + carry
# 更新下一位的进位
carry = sum_val // 10
# 将结果定义为 ListNode 并赋给我们的下一节点
body.next = ListNode(sum_val%10)
# 更新 body 为下一节点以完成连接
body = body.next
# 更新 l1 和 l2 到下一节点
if l1!=None:
l1 = l1.next
if l2!=None:
l2 = l2.next
# 考虑个最后一位的情况
if carry>0:
body.next = ListNode(carry)
# 将表头的下一节点作为结果链表返回
return answer.next表现结果：
Runtime: 76 ms, faster than 32.60% of Python3 online submissions for Add Two Numbers. Memory Usage: 13.8 MB, less than 5.67% of Python3 online submissions for Add Two Numbers.
运行时间从我们之前自己代码的 128ms 降到了 76ms，效果还是很明显的。至于其它思路，之后如果有机会再刷的话再研究，这次先这样吧。
结论
第二题，难度在 LeetCode 中是中等难度，确实一上来这个定义的 ListNode 给了一个下马威，只能尝试着先琢磨明白这个类、搞明白如何返回相应的格式结果，之后便可以回归到我们可以正常设计的算法上来了。
优化的代码是参考着一份推荐的 Java 答案来改写的，自己写可能就会忽略最后那个进位、以及对 l1 和 l2 两个变量同时 while 的情况。写的过程中也是利用到了 Python 中的三元表达式来简化判断赋值过程：
value = true-expr if condition else false-expr也算是一个熟悉这些用法的小实践吧。今天收获挺多，明天继续～