4.3 练手
Leetcode 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.
第一次用暴力解，得到Time Limit Exceeded，应该是自己想太多想复杂了，先把链表转成数组然后变成数字加，再把数字转成链表。。我自己手打都好累。。。。
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
curNode1 = l1
curNode2 = l2
list1 = []
list2 = []
Num1 = 0
Num2 = 0
while curNode1 != None:
list1.append(curNode1.val)
list2.append(curNode2.val)
curNode1 = curNode1.next
curNode2 = curNode2.next
for i in range(len(list1)):
Num1 = list1[-i-1]*(10**i) + Num1
Num2 = list2[-i-1]*(10**i) + Num2
result = Num1 + Num2
while result%10 ==0:
result = int(result/10)
if result < 10 :
head = ListNode(result)
return head
else:
headNode = ListNode(result%10)
currentNode = headNode
result = int(result/10)
while result!=0 :
currentNode.next = ListNode(result%10)
currentNode = currentNode.next
result = int(result/10)
return headNode
换了一种方法：我认为时间复杂度为 O(n) ，然而还是Time Limit Exceeded 。。为什么我好难过~
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
curNode1 = l1
curNode2 = l2
resNum = [0]*3
upNum = [0] * 3
i = 0
while curNode1 != None:
resNum[i] = curNode1.val + curNode2.val
if i > 1 and upNum[i-1]==1 :
resNum[i] = resNum[i] + 1
if resNum[i] > 10:
resNum[i] = resNum[i] - 10
upNum[i] = 1
if upNum[2] == 1:
resNum.append(1)
head = ListNode(resNum[0])
current = head
for j in range(1,len(resNum)):
current.next = ListNode(resNum[j])
current = current.next
return head
考虑是不是多开一个链表浪费时间。。但是感觉这种量级的消耗应该没问题才对，换了一种方法来算：
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
curNode1 = l1
curNode2 = l2
up = 0
k = ListNode(0)
k.next = l1
while curNode1 != None:
resup = up
result = curNode1.val + curNode2.val
if result >= 10:
result = result - 10
up = 1
else:
up = 0
l1.val = result + resup
if l1.next != None:
l1 = l1.next
else:
if resup ==1:
l1.next = ListNode(1)
resup = 0
好的，还是超时，比较绝望。决定去看discussion版块
发现其中一个回答是 O（n）的，但是过了...他的回答如下：
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
re = ListNode(0)
r=re
carry=0
while(l1 or l2):
x= l1.val if l1 else 0
y= l2.val if l2 else 0
s=carry+x+y
carry=s//10
r.next=ListNode(s%10)
r=r.next
if(l1!=None):l1=l1.next
if(l2!=None):l2=l2.next
if(carry>0):
r.next=ListNode(1)
return re.next
说明了我忽略了可能l1 和 l2 不等长的情况...em..恍然大悟。
如果用python 自带的divmod函数来做除法和余会更快，而且可以把最后一位进位放进循环中迭代。以下是程序：
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
carry = 0
root = n = ListNode(0)
while l1 or l2 or carry:
v1 = v2 = 0
if l1:
v1 = l1.val
l1 = l1.next
if l2:
v2 = l2.val
l2 = l2.next
carry, val = divmod(v1+v2+carry, 10)
n.next = ListNode(val)
n = n.next
return root.next
看到一个邪道解法
很有用的int 转 list 和 list 转 int 方法，比我的用字符串中转高明得多：
递归方法：
class Solution:
def addTwoNumbers(self, l1, l2):
def toint(node):
return node.val + 10 * toint(node.next) if node else 0
def tolist(n):
node = ListNode(n % 10)
if n > 9:
node.next = tolist(n // 10)
return node
return tolist(toint(l1) + toint(l2))
同时还有一个判断两个链表是否非空的小技巧：
class Solution:
def addTwoNumbers(self, l1, l2):
addends = l1, l2
dummy = end = ListNode(0)
carry = 0
while addends or carry:
carry += sum(a.val for a in addends)
addends = [a.next for a in addends if a.next]
end.next = end = ListNode(carry % 10)
carry /= 10
return dummy.next
感觉这道题让我对python的理解增加了不少，比如C++的指针和变量是有区别的，但是python其实指针就是变量，赋值操作是将指针地址更改了，如果是其他语言应该不会直接更改地址的。如下图
解析：https://www.cnblogs.com/hzwsj/p/5777973.html
让我对python指针认识更加深刻的代码：（天python简直邪道
k = [1,2,3,4] b = k c = k.copy() print(b) k.remove(4) print(b) print(c)
相关知识
宠物教练手游
宠物美容师出来到哪里找狗练手呢
游戏明星大乱斗4.3小游戏,在线玩,4399小游戏
大部分好养价美的宠物蛇！现货秒发！适合新手练手的国产蛇和造景
便宜耐养的观赏鱼，新手养鱼练手之选，你养过哪些？
======中式衣服。仿奚仲男装一套，练手作，慎入，下载使用前请务必阅读，多图展示====
2022年国内宠物鱼油市场规模4.3亿元，胶囊型宠物鱼油需求上涨丨艾媒咨询
【蜥蜴宠物便宜】蜥蜴宠物便宜品牌、价格
宠物训练手游下载安装
Futureway 宠物定位器 4.3*3.6*1.6cm
网址: 4.3 练手 https://m.mcbbbk.com/newsview493022.html
| 上一篇: 《高等代数,张禾瑞》习题2.1. |
下一篇: 干支表 |
