Plus One

Q: Wie hoch ist die Zeitkomplexität von Plus One?

Beide Ansätze benötigen für n Ziffern eine Laufzeit von O(n) , da der Fall mit lauter 9ern jede Ziffer betrifft. Die Version mit vorzeitigem Abbruch endet nach den nachgestellten 9ern und benötigt O(1) zusätzlichen Speicherplatz, außer wenn das Ergebnis eine neue führende Ziffer erfordert.

LeichtMathe und Simulation

+10

Eine nichtnegative ganze Zahl wird als Array ihrer Dezimalziffern gespeichert, digits, mit der höchstwertigen Ziffer zuerst: 472 ist [4, 7, 2]. Addiere eins zur Zahl und gib die Ziffern des Ergebnisses in derselben Form zurück. Die Zahl kann bis zu 100 Ziffern haben, weit mehr, als eine 64-Bit-Ganzzahl speichern kann.

Funktion

plusOne(digits: integer-array) → integer-array

digitsinteger-array: die Ziffern der Zahl, beginnend mit der höchstwertigen
Gibt zurückinteger-array: die Ziffern der Zahl plus eins, beginnend mit der höchstwertigen Ziffer

Einschränkungen

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits hat keine führende Null, außer bei der Zahl 0 selbst, die [0] ist.

Beispiele

Eingabe: digits = [4, 3, 9]
Ausgabe: [4, 4, 0]
Erklärung: Die Zahl ist 439, und 439 + 1 = 440. Die letzte Ziffer 9 wird zu 0 und gibt einen Übertrag an die 3 weiter, die zu 4 wird.

Eingabe: digits = [0]
Ausgabe: [1]
Erklärung: Die Zahl 0 wird als [0] geschrieben, und 0 + 1 = 1.

Weiterführende Frage

Wie würdest du stattdessen 1 abziehen, wenn die Zahl mindestens 1 beträgt? Wann verliert das Ergebnis seine führende Ziffer, wie bei [1, 0, 0]?

Lösung

Eine 100-stellige Zahl läuft bei jedem 64-Bit-Integer über, dessen Grenze bei etwa 1.8 × 10^19 liegt, daher kannst du sie nicht konvertieren und addieren. Addiere so, wie du es auf Papier machst: von der letzten Ziffer aus mit einem Übertrag. Beim Addieren von 1 ändern sich nur die nachfolgenden 9en, die zu 0en werden, und die Ziffer links davon.

Addieren mit Übertrag, Ziffer für Ziffer

Idee

Beginne mit einem Übertrag von 1, der Zahl, die du addierst. Bei jeder Ziffer von rechts ist die Spaltensumme die Ziffer plus der Übertrag: total % 10 kommt in die Antwort und total / 10 ist der nächste Übertrag. Eine Summe beträgt höchstens 9 + 1 = 10, daher bleibt der Übertrag 0 oder 1. Ein nach der ersten Ziffer übrig gebliebener Übertrag wird zu einer neuen führenden Ziffer, wie bei 999 + 1 = 1000.

Du erzeugst die Antwort mit der letzten Ziffer zuerst. Sammle die Ziffern also in dieser Reihenfolge und kehre sie am Ende um. Das dauert O(n) und benötigt ein neues Array mit bis zu n + 1 Ziffern.

Algorithmus

Setze carry auf 1 und beginne mit einer leeren Liste für die Antwort.
Berechne für jede Ziffer von der letzten bis zur ersten total = digit + carry.
Füge total % 10 zur Antwort hinzu und setze carry auf total / 10, abgerundet.
Füge nach der Schleife carry hinzu, wenn es 1 ist.
Kehre die Antwort um und gib sie zurück.

def plusOne(digits):
    result = []  # the answer, last digit first
    carry = 1  # the one you are adding
    for i in range(len(digits) - 1, -1, -1):
        total = digits[i] + carry
        result.append(total % 10)
        carry = total // 10
    if carry > 0:
        result.append(carry)
    result.reverse()
    return result

Bei der ersten Ziffer unter 9 anhalten

Idee

Eine Ziffer kleiner als 9 übernimmt einen Übertrag von 1: Sie erhöht sich um eins, und jede Ziffer links von ihr behält ihren Wert. Nur eine 9 gibt den Übertrag weiter, indem sie zu 0 wird. Du kannst also bei der ersten Ziffer kleiner als 9 aufhören und das Eingabearray zurückgeben, das direkt geändert wurde. Bei [2, 9, 0, 9] wird die letzte 9 zu 0, die 0 wird zu 1, und du gibst [2, 9, 1, 0] zurück, ohne die ersten beiden Ziffern zu lesen.

Wenn keine Ziffer kleiner als 9 ist, war die Zahl 10^n - 1, und das Ergebnis besteht aus einer 1 gefolgt von n Nullen. Nur in diesem Fall wird ein neues Array benötigt, sodass der zusätzliche Speicherbedarf andernfalls O(1) beträgt.

Algorithmus

Gehe die Indizes vom letzten bis zum ersten durch.
Wenn die Ziffer kleiner als 9 ist, erhöhe sie um eins und gib das Array zurück.
Andernfalls ist die Ziffer 9: Setze sie auf 0 und gehe eine Stelle nach links.
Wenn die Schleife endet, war jede Ziffer 9: Gib eine 1 gefolgt von den n Nullen zurück.

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1  # no carry leaves this digit, so the rest stays as it is
            return digits
        digits[i] = 0  # 9 + 1 = 10: write 0 and carry one to the left
    # Every digit was 9: the answer is 1 followed by zeros.
    return [1] + digits

Stolperfallen und Grenzfälle

Das Array in eine Ganzzahl und zurück umzuwandeln. Eine 64-Bit-Ganzzahl fasst höchstens 19 oder 20 Ziffern, daher kommt es bei 100 Ziffern zu einem Überlauf, und eine Gleitkommazahl verliert schon früher die letzten Ziffern.
Die zusätzliche Ziffer zu vergessen. [9, 9, 9] muss zu [1, 0, 0, 0] werden; Code, der nur die vorhandenen Stellen überschreibt, gibt [0, 0, 0] zurück.
Zur ersten Ziffer 1 zu addieren. Das Array ist mit der höchstwertigen Ziffer zuerst angeordnet, die Einerstelle ist also das letzte Element.
Nach dem Übertrag nicht zurückzukehren, sobald eine Ziffer kleiner als 9 den Übertrag aufnimmt. Die Schleife verändert dann Ziffern, die unverändert bleiben müssen: [1, 9, 3] muss zu [1, 9, 4] werden.
In Lua und R beginnen Arrays bei 1, daher steht die letzte Ziffer am Index n, nicht n - 1.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Plus One?

Beide Ansätze benötigen für n Ziffern eine Laufzeit von O(n), da der Fall mit lauter 9ern jede Ziffer betrifft. Die Version mit vorzeitigem Abbruch endet nach den nachgestellten 9ern und benötigt O(1) zusätzlichen Speicherplatz, außer wenn das Ergebnis eine neue führende Ziffer erfordert.

Warum wandeln wir die Ziffern nicht in eine Ganzzahl um?

Die Zahl kann 100 Stellen haben, und eine 64-Bit-Ganzzahl endet bei etwa 1.8 × 10^19, also bei 20 Stellen. Python und Ruby haben Ganzzahlen ohne Begrenzung, daher funktioniert die Umwandlung dort, aber der Code lässt sich nicht auf andere Sprachen übertragen. Die Verarbeitung Ziffer für Ziffer führt niemals zu einem Überlauf.

Wie addiert man zwei Zahlen, die als Ziffern-Arrays gespeichert sind?

Verwende die Spaltenmethode mit einem Index am Ende jedes Arrays. Addiere in jeder Spalte die beiden Ziffern, wobei eine fehlende Ziffer als 0 behandelt wird, sowie den Übertrag. Beende den Vorgang, wenn beide Arrays aufgebraucht sind und der Übertrag 0 ist, und kehre dann die gesammelten Ziffern um.

def plusOne(digits):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

digits = [4, 3, 9]

Erwartete Ausgabe

[4, 4, 0]