[刷题]LeetCode 2. 两数相加

代码git：History for 2. 两数相加.py - WankkoRee/LeetCodeAnswersWithPython3

这题又是各种卡边缘条件的一题...

先是写个最基本的链表合并，然后简单地考虑一下进位。（assert False只是我当调试断点用的，因为这题结果是对象，不太好直接检查，所以就下断点手动检查了）

 # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = l1
        q = l2
        ex = 0
        while p and q:
            p.val += q.val + ex
            if p.val >= 10:
                ex = 1
                p.val -= 10
            else:
                ex = 0
            p = p.next
            q = q.next
        if ex:
            if p:
                p.val += ex
            else:  # q
                q.val += ex
        return l1
 
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
assert False

结果自然是没过，数据是addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))，因为进位的问题没考虑完全，即使有一条链表已经处理完了，只剩下单条链表，进位也可能不止一次，比如说这个 $9999999+9999$ 的情况，就需要在合并结束后连续进位，于是补一下结束后的连续进位，再看看正确率。

 # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = l1
        q = l2
        ex = 0
        while p and q:
            p.val += q.val + ex
            if p.val >= 10:
                ex = 1
                p.val -= 10
            else:
                ex = 0
            p = p.next
            q = q.next
        if ex:
            if p:
                while p:
                    p.val += ex
                    if p.val >= 10:
                        ex = 1
                        p.val -= 10
                    else:
                        break
            else:  # q
                while q:
                    q.val += ex
                    if q.val >= 10:
                        ex = 1
                        q.val -= 10
                    else:
                        break
        return l1
 
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
assert False

然后因为是没测直接交的，所以又在刚才的数据上翻车了，翻的原因是忘记写链表指针后移了...

 # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = l1
        q = l2
        ex = 0
        while p and q:
            p.val += q.val + ex
            if p.val >= 10:
                ex = 1
                p.val -= 10
            else:
                ex = 0
            p = p.next
            q = q.next
        if ex:
            if p:
                while p:
                    p.val += ex
                    if p.val >= 10:
                        ex = 1
                        p.val -= 10
                    else:
                        break
                    p = p.next
            else:  # q
                while q:
                    q.val += ex
                    if q.val >= 10:
                        ex = 1
                        q.val -= 10
                    else:
                        break
                    q = q.next
        return l1
 
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
assert False

然后又风风火火地交，风风火火地裂开，主要还是太自信了，最后没有处理进位导致溢出了1个长度的问题，所以就补一下进位的溢出修复。

 # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = l1
        q = l2
        ex = 0
        while p and q:
            p.val += q.val + ex
            if p.val >= 10:
                ex = 1
                p.val -= 10
            else:
                ex = 0
            p = p.next
            q = q.next
        if ex:
            if p:
                while p:
                    p.val += ex
                    if p.val >= 10:
                        ex = 1
                        p.val -= 10
                    else:
                        ex = 0
                        break
                    p = p.next
                if ex:
                    p.next = ListNode(ex)
            else:  # q
                while q:
                    q.val += ex
                    if q.val >= 10:
                        ex = 1
                        q.val -= 10
                    else:
                        ex = 0
                        break
                    q = q.next
                if ex:
                    q.next = ListNode(ex)
        return l1
 
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
assert False

结果就报错了，因为在处理最后的溢出进位时，p或者q已经是None了，压根不是ListNode对象...于是就把这处的处理上移一下，确保还没后移指针时先判断一下要不要处理。

 # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = l1
        q = l2
        ex = 0
        while p and q:
            p.val += q.val + ex
            if p.val >= 10:
                ex = 1
                p.val -= 10
            else:
                ex = 0
            p = p.next
            q = q.next
        if ex:
            if p:
                while p:
                    p.val += ex
                    if p.val >= 10:
                        ex = 1
                        p.val -= 10
                        if p.next:
                            p = p.next
                        else:
                            p.next = ListNode(ex)
                            break
                    else:
                        break
            else:  # q
                while q:
                    q.val += ex
                    if q.val >= 10:
                        ex = 1
                        q.val -= 10
                        if q.next:
                            q = q.next
                        else:
                            q.next = ListNode(ex)
                            break
                    else:
                        break
        return l1
 
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
assert False

这个边缘数据总算过了，但是又来了个addTwoNumbers(ListNode(2, ListNode(4, ListNode(9))), ListNode(5, ListNode(6, ListNode(4, ListNode(9)))))的边缘数据，这个纯属是刚才考虑q比p长的时候想岔了，忘记把q尾部数据接到p上面去了，不过既然拼接了链表的话，那就下面进位不用管q的事了，所有数据全在p上了。

 # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = l1
        q = l2
        ex = 0
        while True:
            p.val += q.val + ex
            if p.val >= 10:
                ex = 1
                p.val -= 10
            else:
                ex = 0
            if p.next:
                p = p.next
            else:
                p.next = q.next
                p = p.next
                break
            if q.next:
                q = q.next
            else:
                break
        if ex:
            while p:
                p.val += ex
                if p.val >= 10:
                    ex = 1
                    p.val -= 10
                    if p.next:
                        p = p.next
                    else:
                        p.next = ListNode(ex)
                        break
                else:
                    break
        return l1
 
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
c = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(9))), ListNode(5, ListNode(6, ListNode(4, ListNode(9)))))
assert False

然后又来个addTwoNumbers(ListNode(5), ListNode(5))的边缘数据，这个的话是因为刚才改动的时候，数据判定的位置不太合理造成的，导致把p给整成None了，所以把上面指针后移的判断给改改就行。

 # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = l1
        q = l2
        ex = 0
        while True:
            p.val += q.val + ex
            if p.val >= 10:
                ex = 1
                p.val -= 10
            else:
                ex = 0
 
            if p.next:
                p = p.next
                if q.next:
                    q = q.next
                else:
                    break
            else:
                if q.next:
                    p.next = q.next
                    p = p.next
                    break
                else:
                    if ex:  # 特殊情况
                        p.next = ListNode(ex)
                        ex = 0
                        break
        if ex:
            while p:
                p.val += ex
                if p.val >= 10:
                    ex = 1
                    p.val -= 10
                    if p.next:
                        p = p.next
                    else:
                        p.next = ListNode(ex)
                        break
                else:
                    break
        return l1
 
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
c = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(9))), ListNode(5, ListNode(6, ListNode(4, ListNode(9)))))
d = solution.addTwoNumbers(ListNode(5), ListNode(5))
assert False

结果这回一改连第一个数据都没过了，仔细看了下跳出情况发现not p.next and not q.next and not ex的时候本来也得跳，结果整忘了，所以直接把not p.next and not q.next and ex的break给共享一下就完事。

 # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = l1
        q = l2
        ex = 0
        while True:
            p.val += q.val + ex
            if p.val >= 10:
                ex = 1
                p.val -= 10
            else:
                ex = 0
 
            if p.next:
                p = p.next
                if q.next:
                    q = q.next
                else:
                    break
            else:
                if q.next:
                    p.next = q.next
                    p = p.next
                    break
                else:
                    if ex:  # 特殊情况
                        p.next = ListNode(ex)
                        ex = 0
                    break
        if ex:
            while p:
                p.val += ex
                if p.val >= 10:
                    ex = 1
                    p.val -= 10
                    if p.next:
                        p = p.next
                    else:
                        p.next = ListNode(ex)
                        break
                else:
                    break
        return l1
 
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
c = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(9))), ListNode(5, ListNode(6, ListNode(4, ListNode(9)))))
d = solution.addTwoNumbers(ListNode(5), ListNode(5))
assert False

终于过了，这测试数据仔细得有点离谱。

执行用时： 40 ms , 在所有 Python3 提交中击败了 99.45% 的用户
内存消耗： 15.1 MB , 在所有 Python3 提交中击败了 22.40% 的用户
通过测试用例： 1568 / 1568

The End

[刷题]LeetCode 2. 两数相加

绿城杯 S1 2021 WriteUp

鹤城杯 S1 2021 WriteUp

Comments NOTHING

取消回复

	# Definition for singly-linked list.
	class ListNode:
	def __init__(self, val=0, next=None):
	self.val = val
	self.next = next

	class Solution:
	def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
	p = l1
	q = l2
	ex = 0
	while p and q:
	p.val += q.val + ex
	if p.val >= 10:
	ex = 1
	p.val -= 10
	else:
	ex = 0
	p = p.next
	q = q.next
	if ex:
	if p:
	p.val += ex
	else: # q
	q.val += ex
	return l1

	solution = Solution()
	a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
	assert False