LeetCode 2. 两数相加

作者: freesan44 | 来源:发表于2020-02-20 19:19 被阅读0次

    题目

    给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

    如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

    您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

    示例:
    
    输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出:7 -> 0 -> 8
    原因:342 + 465 = 807
    

    解题思路

    创建初始链表,用carry来记录进位

    # Definition for singly-linked list.
    class ListNode():
        def __init__(self, val):
            if isinstance(val, int):
                self.val = val
                self.next = None
    
            elif isinstance(val, list):
                self.val = val[0]
                self.next = None
                cur = self
                for i in val[1:]:
                    cur.next = ListNode(i)
                    cur = cur.next
    
        def gatherAttrs(self):
            return ", ".join("{}: {}".format(k, getattr(self, k)) for k in self.__dict__.keys())
    
        def __str__(self):
            return self.__class__.__name__ + " {" + "{}".format(self.gatherAttrs()) + "}"
    
    
    class Solution:
        def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            if isinstance(l1, list):
                l1 = ListNode(l1)
                l2 = ListNode(l2)
            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
                z = x + y + carry
                carry = z//10
                r.next = ListNode(z % 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
    
    if __name__ == '__main__':
        test = Solution()
        print(test.addTwoNumbers([1, 3], [2, 1, 3]))
    

    相关文章

      网友评论

        本文标题:LeetCode 2. 两数相加

        本文链接:https://www.haomeiwen.com/subject/ynhfqhtx.html