亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

鏈表加法產生不正確的結果

鏈表加法產生不正確的結果

慕容森 2023-03-22 17:02:06
這是我試圖從這個 leetcode問題中解決的一個簡單問題的一些 python 代碼。給定兩個非空鏈表,代表兩個非負整數。這些數字以相反的順序存儲,并且它們的每個節點都包含一個數字。將這兩個數字相加并將其作為鏈表返回。您可以假設這兩個數字不包含任何前導零,除了數字 0 本身。例子:  Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)   Output: 7 -> 0 -> 8   Explanation: 342 + 465 = 807.我無法弄清楚我的代碼中的錯誤在哪里。運行時代碼的輸出在底部。import unittestdef addTwoNumbers(l1, l2):    Rhead1 = reverseLL(l1) # 3 -> 4 -> 2    Rhead2 = reverseLL(l2) # 4 -> 6 -> 5    node1 = Rhead1    node2 = Rhead2    carry = 0    newLL = None    while node1 and node2:        arith = node1.data + node2.data + carry        # print('node1: {0} + node2: {1} + carry: {2} = arith: {3}'.format(node1.data, node2.data, carry, arith))        carry = 0        if arith >= 10: carry, arith = divmod(arith, 10)                if newLL: newLL.next = Node(arith)        else: newLL = Node(arith)        node1, node2 = node1.next, node2.next        return newLLdef reverseLL(head):    prev = None    node = head    while node:        next = node.next        node.next = prev        prev = node        node = next        return prevclass Node:    def __init__(self, data, next=None):        self.data, self.next = data, next        def __str__(self):        string = str(self.data)        if self.next:            string += ' -> ' + str(self.next)        return stringclass Test(unittest.TestCase):    def test_addTwoNumbers(self):        head1 = Node(2, Node(4, Node(3, None)))    # (2 -> 4 -> 3)        head2 = Node(5, Node(6, Node(4, None)))    # (5 -> 6 -> 4)        expected = Node(7, Node(0, Node(8, None))) # (7 -> 0 -> 8)        print('actual:',str(addTwoNumbers(head1, head2)))        print('expected:',str(expected))        # self.assertAlmostEqual(str(addTwoNumbers(head1, head2)), str(expected))if __name__ == '__main__':    unittest.main() 輸出:actual: 7 -> 8expected: 7 -> 0 -> 8我在哪里沒有得到預期的結果?我傻眼了,我不知道為什么我的代碼不起作用。請幫忙
查看完整描述

2 回答

?
慕勒3428872

TA貢獻1848條經驗 獲得超6個贊

問題在于您的 newLL 變量以及您如何將數字附加到鏈表中。您已經創建了該列表的頭部,并且最多使用 newLL.next 上升到第二個值,但是您沒有遍歷列表以添加更多值。這是一個可能的解決方案:


def addTwoNumbers(l1, l2):

    Rhead1 = reverseLL(l1) # 3 -> 4 -> 2

    Rhead2 = reverseLL(l2) # 4 -> 6 -> 5


    node1 = Rhead1

    node2 = Rhead2

    carry = 0

    newLL = None

    temp = None


    while node1 and node2:

        arith = node1.data + node2.data + carry

        # print('node1: {0} + node2: {1} + carry: {2} = arith: {3}'.format(node1.data, 

        #node2.data, carry, arith))

        carry = 0

        if arith >= 10: carry, arith = divmod(arith, 10)

    

        if newLL: 

            temp.next = Node(arith)

            temp = temp.next

        else: 

            newLL = Node(arith)

            temp = newLL


        node1, node2 = node1.next, node2.next


    return newLL


查看完整回答
反對 回復 2023-03-22
?
慕婉清6462132

TA貢獻1804條經驗 獲得超2個贊

干得好使用unittest和carry, arith = divmod(arith, 10)!


不確定你的錯誤,但我們可以使用哨兵節點并更容易地解決問題。


這會過去:


class Solution:

    def addTwoNumbers(self, a, b):

        carry = 0

        sentinel = p = ListNode(0)

        while a or b or carry:

            if a:

                carry, a = carry + a.val, a.next

            if b:

                carry, b = carry + b.val, b.next

            carry, val = carry // 10, carry % 10

            p.next = p = ListNode(val)

        return sentinel.next

參考

  • 有關其他詳細信息,您可以查看討論區。有很多公認的解決方案,其中包含各種語言和解釋、高效的算法以及漸近時間/空間復雜性分析1、2。


查看完整回答
反對 回復 2023-03-22
  • 2 回答
  • 0 關注
  • 128 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號