Add Two Numbers

Q: Wie hoch ist die Zeitkomplexität beim Addieren zweier Zahlen, die als verkettete Listen gespeichert sind?

Es ist O(max(L1, L2)) : ein Schritt pro Spalte, plus ein weiterer, wenn am Ende ein Übertrag übrig bleibt. Abgesehen von der Antwort benötigt die Ein-Pass-Version O(1) Speicher: zwei Zeiger und den Übertrag.

MittelVerkettete Liste Mathe und Simulation

+10

Du erhältst zwei nicht negative ganze Zahlen, die jeweils als einfach verkettete Liste ihrer Ziffern gespeichert sind, wobei die Ziffer mit dem kleinsten Stellenwert zuerst kommt. In der ersten Liste enthält Knoten i die Ziffer values1[i] und verweist auf Knoten next1[i]. Die zweite Liste funktioniert genauso, mit next2 und values2. In beiden Listen beendet -1 die Liste, und der Kopf ist Knoten 0. Die Knoten sind nicht in Listenreihenfolge gespeichert, folge also den Verweisen.

Gib die Ziffern der Summe der beiden Zahlen zurück, beginnend mit der Ziffer mit dem kleinsten Stellenwert.

Funktion

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

next1integer-array: der Index des Knotens, mit dem jeder Knoten der ersten Zahl verknüpft ist, oder -1 für deren letzten Knoten
values1integer-array: die Ziffer, die in jedem Knoten der ersten Zahl gespeichert ist
next2integer-array: der Index des Knotens, mit dem jeder Knoten der zweiten Zahl verknüpft ist, oder -1 für den letzten Knoten
values2integer-array: die Ziffer, die jeder Knoten der zweiten Zahl enthält
Gibt zurückinteger-array: die Ziffern der Summe, beginnend mit der niedrigstwertigen

Einschränkungen

1 ≤ L1 ≤ 100, wobei L1 die Länge von next1 und values1 ist.
1 ≤ L2 ≤ 100, wobei L2 die Länge von next2 und values2 ist.
0 ≤ values1[i], values2[j] ≤ 9
Jeder Eintrag von next1 ist -1 oder ein Knotenindex der ersten Liste, und jeder Eintrag von next2 ist -1 oder ein Knotenindex der zweiten Liste.
Ausgehend vom Knoten 0 besucht jede Liste jeden ihrer Knoten genau einmal und erreicht dann -1. Es gibt keinen Zyklus.
Keine Zahl hat führende Nullen: Der letzte Knoten einer Liste enthält eine Ziffer ungleich 0, es sei denn, die Liste besteht aus der einzelnen Ziffer 0.

Beispiele

Eingabe: next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
Ausgabe: [5, 4, 1, 1]
Erklärung: Die erste Liste besucht die Knoten 0, 2, 1 und liest 8, 1, 6, die Zahl 618. Die zweite liest 7, 2, 5, die Zahl 527. Ihre Summe ist 1145, also lautet die Antwort 5, 4, 1, 1.

Eingabe: next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
Ausgabe: [0, 0, 0, 0, 1]
Erklärung: Die zweite Liste ergibt 1, 9, 9, 9, die Zahl 9991. Addiert man 9, erhält man 10000: In jeder Spalte entsteht eine 0 und ein Übertrag, und der letzte Übertrag wird zu einer fünften Ziffer.

Eingabe: next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
Ausgabe: [7, 5]
Erklärung: Die erste Zahl ist 0 und die zweite Liste ergibt 7, 5, also die Zahl 57. Das Addieren von 0 ändert nichts, daher lautet die Antwort [7, 5].

Weiterführende Frage

Wie würdest du die Zahlen addieren, wenn die Listen die höchstwertige Ziffer zuerst speichern?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Zahlen sind für jeden Ganzzahltyp zu lang, also addiere sie wie auf Papier: Spalte für Spalte und übertrage eine 1, wenn eine Spalte 10 erreicht. Die Listen speichern die Einerstelle zuerst, daher durchläufst du beim Durchlaufen die Spalten in der Reihenfolge, in der du sie addierst.

Kopiere die Ziffern heraus und addiere dann Spalte für Spalte

Idee

Ein Zeiger ist hier ein Knotenindex, und vorwärtszugehen bedeutet node = next[node]. Kopiere die Ziffern jeder Liste in ein Array, sodass der Index i die Ziffer mit dem Wert 10^i enthält: [8, 1, 6] und [7, 2, 5] im ersten Beispiel.

Addiere dann wie auf Papier und zähle eine fehlende Ziffer als 0. In jeder Spalte wird sum % 10 notiert und der Rest übertragen: 8 + 7 = 15 ergibt 5 und überträgt 1, 1 + 2 + 1 = 4, und 6 + 5 = 11 ergibt 1. Der letzte Übertrag wird zur letzten Ziffer: [5, 4, 1, 1].

Die Kopien benötigen O(L1 + L2) zusätzlichen Speicher, den die Addition gar nicht braucht.

Algorithmus

Durchlaufe jede Liste ab Knoten 0 und kopiere ihre Ziffern in ein Array.
Setze carry = 0. Addiere für jeden Index i bis zur Länge des längeren Arrays die vorhandenen Ziffern an Position i und den Übertrag.
Füge sum % 10 hinzu und setze carry auf sum / 10, abgerundet.
Wenn der Übertrag nach der letzten Stelle 1 beträgt, füge ihn hinzu.

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

Gehe beide Listen gleichzeitig mit einem Übertrag durch

Idee

Spalte i verwendet nur den i-ten Knoten jeder Liste. Behalte daher einen Zeiger pro Liste, a und b, und bewege beide weiter, während die Spalten durchlaufen werden.

Eine Schleife läuft, solange a nicht -1 ist oder b nicht -1 ist oder der Übertrag 1 ist. Ein Zeiger, auf den noch ein Knoten folgt, addiert dessen Ziffer und rückt weiter; ein Zeiger bei -1 addiert nichts. So werden Zahlen unterschiedlicher Länge ohne eine zweite Schleife verarbeitet, und die Übertragsbedingung schreibt die zusätzliche Ziffer am Ende.

Im zweiten Beispiel ergibt 9 plus 9991 in jeder Spalte die Summe 10 und schreibt 0. Nach vier Spalten sind beide Listen abgearbeitet, aber der Übertrag ist 1, also läuft die Schleife noch einmal: [0, 0, 0, 0, 1]. Abgesehen von der Antwort benötigt der Algorithmus drei Ganzzahlen.

Algorithmus

Setze a = 0, b = 0 und carry = 0.
Solange a != -1 oder b != -1 oder carry > 0 gilt, beginne die Spaltensumme mit carry.
Wenn a != -1 gilt, addiere values1[a] und setze a = next1[a]. Mache dasselbe für b mit der zweiten Liste.
Füge sum % 10 hinzu und setze carry auf sum / 10, abgerundet.
Gib die hinzugefügten Ziffern zurück.

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

Stolperfallen und Grenzfälle

Jede Liste in eine Ganzzahl umwandeln und addieren. Eine Zahl mit 100 Stellen läuft bei jedem 64-Bit-Typ über.
Den letzten Übertrag verwerfen. Eine Schleife, die endet, wenn beide Listen zu Ende sind, gibt für das zweite Beispiel [0, 0, 0, 0] zurück.
Anhalten, wenn die kürzere Liste endet. Im zweiten Beispiel gehen dadurch die drei 9en von 9991 und der Übertrag, der durch sie läuft, verloren.
Die Ziffern in Array-Reihenfolge lesen. Im ersten Beispiel ist values1 [8, 6, 1], aber die Zahl ist 618, entlang der Verknüpfungen gelesen.
Den Versatz in Lua und R vergessen, wo Arrays bei 1 beginnen. Knoten-IDs bei 0 beginnen lassen und next1[node + 1] lesen.

Häufige Fragen3

Warum werden die Ziffern bei „Add Two Numbers“ in umgekehrter Reihenfolge gespeichert?

Die Addition beginnt bei der Einerstelle, und eine einfach verkettete Liste kann nur von ihrem Kopf aus durchlaufen werden. Wenn die niedrigstwertige Ziffer zuerst kommt, besucht der Durchlauf die Stellen in der Reihenfolge, in der du sie addierst, sodass der Übertrag mit den Zeigern weiterwandert.

Wie hoch ist die Zeitkomplexität beim Addieren zweier Zahlen, die als verkettete Listen gespeichert sind?

Es ist O(max(L1, L2)): ein Schritt pro Spalte, plus ein weiterer, wenn am Ende ein Übertrag übrig bleibt. Abgesehen von der Antwort benötigt die Ein-Pass-Version O(1) Speicher: zwei Zeiger und den Übertrag.

Kann der Übertrag jemals größer als 1 sein?

Nein. Eine Spalte addiert zwei Ziffern von höchstens 9 und einen Übertrag von höchstens 1, daher ist ihre Summe höchstens 19. Bei der Division durch 10 und Abrunden ergibt sich 0 oder 1.

def addTwoNumbers(next1, values1, next2, values2):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

[5, 4, 1, 1]