Add Two Numbers

Q: Quelle est la complexité temporelle de l’addition de deux nombres stockés dans des listes chaînées ?

C’est O(max(L1, L2)) : une étape par colonne, plus une de plus lorsqu’il reste une retenue à la fin. À part la réponse, la version en un seul passage utilise une mémoire O(1) : deux pointeurs et la retenue.

MoyenListe chaînée Maths et simulation

+10

Tu reçois deux nombres entiers non négatifs, chacun stocké sous forme de liste chaînée simple de ses chiffres, avec le chiffre de poids faible en premier. Dans la première liste, le nœud i contient le chiffre values1[i] et pointe vers le nœud next1[i]. La deuxième liste fonctionne de la même manière avec next2 et values2. Dans les deux listes, -1 marque la fin de la liste et la tête est le nœud 0. Les nœuds ne sont pas stockés dans l’ordre de la liste, alors suis les liens.

Renvoie les chiffres de la somme des deux nombres, en commençant par le chiffre de poids faible.

Fonction

addTwoNumbers(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: l’index du nœud auquel chaque nœud du premier nombre est relié, ou -1 pour son dernier nœud
values1integer-array: le chiffre stocké dans chaque nœud du premier nombre
next2integer-array: l’index du nœud vers lequel pointe chaque nœud du deuxième nombre, ou -1 pour son dernier nœud
values2integer-array: le chiffre stocké dans chaque nœud du deuxième nombre
Renvoieinteger-array: les chiffres de la somme, du moins significatif au plus significatif

Contraintes

1 ≤ L1 ≤ 100, où L1 est la longueur de next1 et de values1.
1 ≤ L2 ≤ 100, où L2 est la longueur de next2 et de values2.
0 ≤ values1[i], values2[j] ≤ 9
Chaque entrée de next1 est -1 ou un indice de nœud de la première liste, et chaque entrée de next2 est -1 ou un indice de nœud de la deuxième liste.
En partant du nœud 0, chaque liste parcourt chacun de ses nœuds exactement une fois, puis atteint -1. Il n’y a pas de cycle.
Aucun nombre ne comporte de zéros non significatifs : le dernier nœud d’une liste contient un chiffre différent de 0, sauf si la liste correspond au chiffre unique 0.

Exemples

Entrée: next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
Sortie: [5, 4, 1, 1]
Explication: La première liste visite les nœuds 0, 2, 1 et lit 8, 1, 6, soit le nombre 618. La deuxième lit 7, 2, 5, soit le nombre 527. Leur somme est 1145, donc la réponse est 5, 4, 1, 1.

Entrée: next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
Sortie: [0, 0, 0, 0, 1]
Explication: La deuxième liste se lit 1, 9, 9, 9, le nombre 9991. En ajoutant 9, on obtient 10000 : chaque colonne produit un 0 et une retenue, et la dernière retenue devient un cinquième chiffre.

Entrée: next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
Sortie: [7, 5]
Explication: Le premier nombre est 0 et la deuxième liste représente 7, 5, le nombre 57. Ajouter 0 ne change rien, donc la réponse est [7, 5].

Pour aller plus loin

Comment additionnerais-tu les nombres si les listes stockaient le chiffre le plus significatif en premier ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Les nombres sont trop longs pour tenir dans un type entier, alors additionne-les comme sur papier : colonne par colonne, en reportant un 1 lorsqu’une colonne atteint 10. Les listes stockent d’abord le chiffre des unités, donc les parcourir permet de visiter les colonnes dans l’ordre où tu les additionnes.

Recopiez les chiffres, puis additionnez colonne par colonne

Intuition

Un pointeur désigne ici un indice de nœud, et avancer revient à faire node = next[node]. Copie les chiffres de chaque liste dans un tableau, de sorte que l’indice i contienne le chiffre correspondant à 10^i : [8, 1, 6] et [7, 2, 5] dans le premier exemple.

Ensuite, additionne comme sur papier, en considérant qu’un chiffre manquant vaut 0. Pour chaque colonne, écris sum % 10 et reporte le reste : 8 + 7 = 15 donne 5 et reporte 1, 1 + 2 + 1 = 4, et 6 + 5 = 11 donne 1. La dernière retenue devient un chiffre final : [5, 4, 1, 1].

Les copies coûtent O(L1 + L2) de mémoire supplémentaire, dont l’addition n’a jamais besoin.

Algorithme

Parcourez chaque liste depuis le nœud 0 et copiez ses chiffres dans un tableau.
Définissez carry = 0. Pour chaque indice i, jusqu’à la longueur du tableau le plus long, additionnez les chiffres présents à i et la retenue.
Ajoutez sum % 10 et définissez carry sur sum / 10, arrondi à l’entier inférieur.
Si la retenue vaut 1 après la dernière colonne, ajoutez-la.

def readDigits(next, values):
    # The digits in list order: least significant first.
    digits = []
    node = 0
    while node != -1:
        digits.append(values[node])
        node = next[node]
    return digits


def addTwoNumbers(next1, values1, next2, values2):
    first = readDigits(next1, values1)
    second = readDigits(next2, values2)
    result = []
    carry = 0
    for i in range(max(len(first), len(second))):
        column = carry
        if i < len(first):
            column += first[i]
        if i < len(second):
            column += second[i]
        result.append(column % 10)
        carry = column // 10
    if carry > 0:
        result.append(carry)
    return result

Parcourir les deux listes en même temps avec une retenue

Intuition

La colonne i utilise uniquement le nœud i-ième de chaque liste ; garde donc un pointeur par liste, a et b, et avance les deux au fil des colonnes.

Une boucle s’exécute tant que a n’est pas -1, ou que b n’est pas -1, ou que la retenue vaut 1. Un pointeur qui a encore un nœud ajoute son chiffre et avance ; un pointeur à -1 n’ajoute rien. Cela permet de gérer les nombres de longueurs différentes sans seconde boucle, et la condition sur la retenue écrit le chiffre supplémentaire à la fin.

Dans le deuxième exemple, 9 plus 9991, chaque colonne donne une somme de 10 et écrit 0. Après quatre colonnes, les deux listes sont terminées, mais la retenue vaut 1, donc la boucle s’exécute une fois de plus : [0, 0, 0, 0, 1]. En plus de la réponse, cela nécessite trois entiers.

Algorithme

Définis a = 0, b = 0 et carry = 0.
Tant que a != -1 ou b != -1 ou carry > 0, commence la somme de la colonne à carry.
Si a != -1, ajoute values1[a] et définis a = next1[a]. Fais de même pour b avec la deuxième liste.
Ajoute sum % 10 et définis carry sur sum / 10, arrondi à l’entier inférieur.
Renvoie les chiffres que tu as ajoutés.

def addTwoNumbers(next1, values1, next2, values2):
    a = 0  # current node of the first number
    b = 0  # current node of the second number
    carry = 0
    result = []
    # Keep going while either number has digits left or a carry is waiting.
    while a != -1 or b != -1 or carry > 0:
        column = carry
        if a != -1:
            column += values1[a]
            a = next1[a]
        if b != -1:
            column += values2[b]
            b = next2[b]
        result.append(column % 10)  # the digit this column writes
        carry = column // 10  # 1 when the column reached 10, else 0
    return result

Pièges et cas limites

Convertir chaque liste en entier et les additionner. Un nombre de 100 chiffres dépasse la capacité de tout type sur 64 bits.
Oublier la retenue finale. Une boucle qui s’arrête lorsque les deux listes sont terminées renvoie [0, 0, 0, 0] pour le deuxième exemple.
S’arrêter lorsque la liste la plus courte se termine. Le deuxième exemple perd alors les trois 9 de 9991 et la retenue qui se propage à travers eux.
Lire les chiffres dans l’ordre du tableau. Dans le premier exemple, values1 est [8, 6, 1], mais le nombre est 618, lu en suivant les liens.
Oublier le décalage en Lua et en R, où les tableaux commencent à 1. Garder les identifiants des nœuds à partir de 0 et lire next1[node + 1].

Questions fréquentes3

Pourquoi les chiffres sont-ils stockés dans l’ordre inverse dans Add Two Numbers ?

L’addition commence par le chiffre des unités, et une liste simplement chaînée ne peut être parcourue qu’à partir de sa tête. En plaçant le chiffre de poids faible en premier, le parcours visite les colonnes dans l’ordre où vous les additionnez, de sorte que la retenue avance avec les pointeurs.

Quelle est la complexité temporelle de l’addition de deux nombres stockés dans des listes chaînées ?

C’est O(max(L1, L2)) : une étape par colonne, plus une de plus lorsqu’il reste une retenue à la fin. À part la réponse, la version en un seul passage utilise une mémoire O(1) : deux pointeurs et la retenue.

La retenue peut-elle être supérieure à 1 ?

Non. Une colonne additionne deux chiffres de 9 au maximum et une retenue de 1 au maximum, donc sa somme est au plus égale à 19. La division par 10, suivie d’un arrondi à l’entier inférieur, donne 0 ou 1.

def addTwoNumbers(next1, values1, next2, values2):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

next1 = [2, -1, 1]
values1 = [8, 6, 1]
next2 = [2, -1, 1]
values2 = [7, 5, 2]

Résultat attendu

[5, 4, 1, 1]