Ajouter un problème de deux nombres (liste chaînée) - Python - Leetcode - AttributeError

NoneType signifie que vous travaillez avec None où vous supposez travailler l'instance de Class ou Object. Cela se produit lorsqu'une affectation ou un appel de fonction ci-dessus a échoué ou a renvoyé un résultat inattendu.

NoneType est le type de la valeur None . Dans ce cas, la durée de vie de la variable a la valeur None Habituellement, il arrive d'appeler une fonction sans retour.

J'ai fait cela en Python3 et je vous recommande de travailler en Python3.

Pour les opérations d'inversion, vous pouvez également utiliser .reverse() qui est en place afin que vous n'ayez pas à créer de nouvelles variables.

De plus, votre opération .join() était incorrecte. Vous devez parcourir chaque caractère de chaque liste au lieu de ce que vous faisiez qui est de créer une représentation sous forme de chaîne de la liste.

La construction de la liste chaînée renvoyée implique l'attribution d'une valeur à la tête de cette liste, puis, si nécessaire, l'ajout de chiffres dans les nouveaux ListNodes lorsque vous parcourez votre chaîne de résultat.

Je dois dire que même si je pense que la vôtre est une nouvelle solution, je pense que l’esprit du problème est de vous mettre plus à l’aise avec les listes chaînées. Donc, travailler autour d'eux est, je crois, légèrement contre cet objectif.

Cela dit, il s'agit d'une solution très efficace en mémoire car les listes sont des structures de données très optimisées en Python.

Bon codage à vous!

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = l1 #pointers
        b = l2 #pointers
        arr1 = []
        arr2 = []

        while a:
          arr1.append(a.val)
          a = a.next

        while b:
          arr2.append(b.val)
          b = b.next

        arr1.reverse()
        arr2.reverse()

        inta = int("".join(str(x) for x in arr1)) #converting list to strings
        intb = int("".join(str(x) for x in arr2))

        c = list(str(inta + intb)) #performing addition - the answer we wanted

        # assign last digit to new ListNode which represents the head of returned LL
        head = l3 = ListNode(c.pop())

        c.reverse()

        # traverse remaining digits, assigning each to new ListNode
        for i in c:
            l3.next = ListNode(i)
            l3 = l3.next

        return head 

Votre erreur est due au fait qu'à un moment donné, a , b ou q vaut None lorsque vous essayez d'accéder à .val .

Je ne vais pas comprendre pourquoi, je vais plutôt vous expliquer comment vous devriez essayer de résoudre ce problème.

La raison pour laquelle le problème est spécifié comme ça est que vous pouvez écrire une solution efficace. La question vous invite à coder une addition longue à partir d'unités de base - c'est-à-dire des unités, des dizaines, des centaines, des milliers, etc.

Les nombres sont dans l'ordre inverse afin que vous puissiez commencer par les unités et transporter tout ce qui dépasse 10.

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def recursive_wrapper(l1, l2, carry):
            if l1 is None and l2 is None:
                return None
            elif l1 is None:
                res = ListNode(l2.val + carry)
                res.next = add_two_recursive(None, l2.next, 0)
            elif l2 is None:
                res = ListNode(l1.val + carry)
                res.next = add_two_recursive(l1.next, None, 0)
            else:
                car, val = divmod(l1.val + l2.val, 10)
                res = ListNode(val + carry)
                res.next = add_two_recursive(l1.next, l2.next, car)
            return res
        return recursive_wrapper(l1, l2, 0)

Penser ainsi cela signifie que vous pouvez coder une réponse beaucoup plus efficace. La complexité pour cela est O(max(len(a), len(b))) , alors que pour votre méthode, elle se situe autour de O(8*max(len(a), len(b))) . Pas une énorme différence, mais il y a beaucoup de calculs inutiles, et ce n'est pas simple à comprendre.

Je suis sûr qu'il y a des améliorations logiques qui peuvent être apportées ici, mais c'est le genre de solution que je pense que vous devriez viser:

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry = 0
        original = value = ListNode(None)
        while True:
            if l1 is None and l2 is None:
                value.val = carry
                break
            elif l1 is None:
                value.val = l2.val + carry
                carry = 0
                l2 = l2.next
            elif l2 is None:
                value.val = l1.val + carry
                carry = 0
                l1 = l1.next
            else:
                car, val = divmod(l1.val + l2.val, 10)
                value.val = val + carry
                carry = car
                l1, l2 = l1.next, l2.next
            value.next = ListNode(None)
            value = value.next
        return original

Edit: Avec un peu plus de réflexion, j'ai réalisé que vous pouvez aussi le faire très bien avec la récursivité.

243
564
^
start here

2 + 5 = 7, carry 0

243
564
 ^

4 + 6 = 0, carry 1

243
564
  ^

3 + 4 (+ 1) = 8, carry 0

therefore the answer is 

7 -> 0 -> 8

Vous créez le ListNode au ListNode mesure. À chaque point, c'est la tête du l1 plus la tête de l2 plus le numéro de portage comme valeur. Ensuite, prenez le suivant pour l1 et l2 et répétez. Si, à tout moment, l1 ou l2 est manquant, comptez la valeur comme 0 . Une fois qu'il n'y a plus de nombres, renvoyez None signifiant la fin du résultat.

class Solution:

    
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    carry = 0
    head = curr = ListNode()
        
    while l1 and l2:
        total = l1.val + l2.val + carry
        curr.next = ListNode(total% 10)
        carry = total // 10
        l1,l2,curr = l1.next, l2.next,curr.next
            
    while l1:
        total = l1.val + carry
        curr.next = ListNode(total%10)
        carry = total // 10
        l1, curr = l1.next, curr.next
            
    while l2:
        total = l2.val + carry
        curr.next = ListNode(total%10)
        carry = total//10
        l2, curr = l2.next, curr.next
    if carry > 0:
        curr.next  = ListNode(carry)
                
    return head.next