美文网首页
leetcode每日一题 python解法 4月14日

leetcode每日一题 python解法 4月14日

作者: Never肥宅 | 来源:发表于2020-04-14 02:38 被阅读0次

    难度:中等

    题目内容:

    给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

    进阶:

    如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。

    示例:

    输入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出:7 -> 8 -> 0 -> 7

    题解:

    emmm
    首先最简单的情况就是有数为0 ,直接返回另一个就好了
    其他的情况可以先把列表翻转过来,然后相加的出一个新列表,把新列表再翻转一下就得到结果了。
    不过题目要求不能进行翻转
    emmm那也好说,我们加一个位数计数就好了
    不过要注意的是(反正我出错了)相加是可能进多位的(199+1这样)
    我下面这个就算初步修改了一下,但是只能解决进两位。。。所以打算换种方法,先算出来,然后把中间变成两位的数拆开就好了嘛,比如10拆成1 0

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            ###如果有0的话
            if l1.val == 0:
                return l2
            elif l2.val == 0:
                return l1
            l1len = 0
            l1c = l1
            while l1c:
                l1c = l1c.next
                l1len += 1
            l2len = 0
            l2c = l2
            while l2c :
                l2c = l2c.next
                l2len += 1
            if l2len >= l1len:
                return self.sum(l2,l2len,l1,l1len)
            elif l2len < l1len:
                return self.sum(l1,l1len,l2,l2len)
    
        def sum(self,lbig,lbiglen,lsmall,lsmalllen):
            # if lbiglen == lsmalllen and (lbig.val +lsmall.val) >= 10:
            #     r = ListNode(1)
            r0 = ListNode(0)
            r = r0
            while lbig:
                if lbiglen == lsmalllen:
                    if  (lbig.val +lsmall.val) >= 10:
                        r.val += 1
    
                    r.next = ListNode(mod( (lbig.val +lsmall.val) ,10))
                    if r.next.val == 9:#预警一下会不会连进两位
                        temp = r
                    r = r.next
                    lbig = lbig.next
                    lbiglen -= 1
                    lsmall = lsmall.next
                    lsmalllen -= 1
                else:
                    r.next = ListNode(lbig.val)
                    if r.next.val == 9:#预警一下会不会连进两位
                        temp = r
                    r = r.next
                    lbig = lbig.next
                    lbiglen -= 1
            if r0.val == 0 and r0.next:
                r0 = r0.next
            return r0
    

    稍加改动,就可以通过啦!

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            ###如果有0的话
            if l1.val == 0:
                return l2
            elif l2.val == 0:
                return l1
            l1len = 0
            l1c = l1
            while l1c:
                l1c = l1c.next
                l1len += 1
            l2len = 0
            l2c = l2
            while l2c :
                l2c = l2c.next
                l2len += 1
            if l2len >= l1len:
                return self.sum(l2,l2len,l1,l1len)
            elif l2len < l1len:
                return self.sum(l1,l1len,l2,l2len)
    
        def sum(self,lbig,lbiglen,lsmall,lsmalllen):
            # if lbiglen == lsmalllen and (lbig.val +lsmall.val) >= 10:
            #     r = ListNode(1)
            r0 = ListNode(0)
            r = r0
            while lbig:
                if lbiglen == lsmalllen:
                    if  (lbig.val +lsmall.val) >= 10:
                        r.val += 1
                    r.next = ListNode(mod( (lbig.val +lsmall.val) ,10))
                    r = r.next
                    lbig = lbig.next
                    lbiglen -= 1
                    lsmall = lsmall.next
                    lsmalllen -= 1
                else:
                    r.next = ListNode(lbig.val)
                    r = r.next
                    lbig = lbig.next
                    lbiglen -= 1
            if r0.val == 0 and r0.next:
                r0 = r0.next
            # 拆数
            
            l = lbiglen
    
            r = r0
            carry = True
            while carry:
                carry = False
                r = r0
                while r.next:
                    if r.next.val >= 10:
                        r.val += 1
                        r.next.val -= 10
                        carry = True
                    r = r.next
            # 第一位大于等于10要变成两个数
            if r0.val >= 10:
                newNode = ListNode(mod(r0.val,10))
                newNode.next = r0.next
                r0.val = r0.val // 10
                r0.next = newNode
                l += 1
            return r0
    

    相关文章

      网友评论

          本文标题:leetcode每日一题 python解法 4月14日

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