站点图标 Wankko Ree's Blog

[刷题]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 exbreak给共享一下就完事。

# 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
退出移动版