[LeetCode] Add Two Numbers

题意

给出俩十进制数字 A 和 B,求 A+B 的和。

注意: A 和 B 都是拿链表方式存储的,链表每一个节点存一位。链表是倒序的。也就是说,如果一个十进制数字是 123 的话,你得到的输入数据会是 3->2->1

题解

题目没看懂…… 但是看懂题目之后程序还是很简单的。

按照标准的高精度写,改成链表就是了。不过要自己根据提示写桩程序。

第一次提交就是因为不知道上面的提示是什么意思而 RE 了。

顺便的,理解了为什么学数据结构的时候 “链表” 要有一个不存任何东西的头指针了:为了简化操作啊!

代码

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        p1 = l1
        p2 = l2
        t = 0

        t1 = 0
        t2 = 0
        head = ListNode(0)
        last = head
        while p1 or p2:
            if p1:
                t1 = p1.val
                p1 = p1.next
            else:
                t1 = 0

            if p2:
                t2 = p2.val
                p2 = p2.next
            else:
                t2 = 0

            t = t + t1 + t2
            last.next = ListNode(t % 10)
            t //= 10
            last = last.next
        if t:
            last.next = ListNode(t)
        return head.next

结果

1556 / 1556 test cases passed.
Status: Accepted
Runtime: 136 ms

Excuse me? 1556 个测试点?!

桩程序

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


def make_list(x):
    if not x:
        return None

    head = ListNode(0)
    last = head
    for ith in range(len(x)):
        last.next = ListNode(x[ith])
        last = last.next

    return head.next


def print_list(x):
    while x:
        print(x.val, end="")
        x = x.next
    print()


def judge(p1, p2):
    while p1 or p2:
        if p1.val != p2.val:
            return False
        p1 = p1.next
        p2 = p2.next
        if bool(p1) ^ bool(p2):
            return False
    return True


if __name__ == '__main__':
    cases = [
        {'l1': [2, 4, 5], 'l2': [5, 6, 4], 'ans': [7, 0, 0, 1]},
        {'l1': [2, 4, 3], 'l2': [5, 6, 4], 'ans': [7, 0, 8]},
    ]

    for item in cases:
        l1 = make_list(item['l1'])
        l2 = make_list(item['l2'])

        ans = (Solution()).addTwoNumbers(l1=l1, l2=l2)

        print(judge(ans, make_list(item['ans'])))
        print_list(ans)
        print()

留下评论