J'essaie de résoudre ce problème - Ajoutez deux nombres qui se trouvent sur Leetcode
J'ai essayé de convertir les deux listes liées en tableaux, puis j'ai effectué l'opération d'ajout. Maintenant, j'ai du mal à les reconvertir dans la liste chaînée qui est la sortie souhaitée pour le problème.
Quelqu'un peut-il vérifier où je me trompe? J'obtiens également une erreur d'attribut:
AttributeError: l'objet 'NoneType' n'a pas d'attribut 'val'
Voici le code que j'ai écrit:
# 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: a = l1 #pointers b = l2 #pointers arr1 = [] arr2 = [] while a.next is not None: arr1.append(a.val) a = a.next arr1.append(a.val) #storing the values of linked lists in arrays/lists while b.next is not None: arr2.append(b.val) b = b.next arr2.append(b.val) #storing the values of linked lists in arrays/lists rev1 = reversed(arr1) #reversed list rev2 = reversed(arr2) #reversed list inta = "".join(str(rev1)) #converting list to strings intb = "".join(str(rev2)) c = str(inta + intb) #performing addition - the answer we wanted revc = reversed(c) #answer in string form - reversed (output in string at present) #trying to convert into linked list and return it q = l1 for i in revc: q.val = i q = q.next return l1
4 Réponses :
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
leetcode.com/problems/add-two-numbers/discuss/771545/… . J'ai trouvé que c'était beaucoup plus facile