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 im schlimmsten Fall, bei lauter 9ern, jede Ziffer berücksichtigt wird. Die Version mit vorzeitigem Abbruch stoppt nach den abschließenden 9ern und benötigt daher bei einer Zahl, die mit einer Ziffer kleiner als 9 endet, einen Schritt. Sie benötigt zusätzlichen Speicherplatz von O(1) , außer wenn das Ergebnis eine neue führende Ziffer benötigt.

Q: Wann hat das Ergebnis mehr Stellen als die Eingabe?

Nur wenn jede Ziffer 9 ist. Dann ist die Zahl 10^n - 1 , und wenn man eins addiert, erhält man 10^n : eine 1, gefolgt von n Nullen. Wenn eine Ziffer kleiner als 9 ist, nimmt sie den Übertrag auf, sodass die Länge gleich bleibt.

LeichtMathe und Simulation

+10

Eine nichtnegative ganze Zahl wird als Array ihrer Dezimalziffern gespeichert, digits, wobei die höchstwertige Ziffer zuerst kommt: 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

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 überträgt einen Übertrag auf die 3, die zu 4 wird.

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

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du stattdessen eins subtrahieren, wenn die Zahl mindestens 1 beträgt? Welche Ziffern ändern sich, und wann verliert das Ergebnis seine führende Ziffer, wie bei [1, 0, 0]?

Lösung

Die Ziffern in eine Zahl umzuwandeln, eins zu addieren und wieder zurückzuwandeln, funktioniert hier nicht: 100 Ziffern laufen bei jeder 64-Bit-Ganzzahl über, deren Grenze bei etwa 1.8 × 10^19 liegt. Deshalb addierst du wie auf Papier, von der letzten Ziffer aus mit einem Übertrag. Die eine Beobachtung, die den Aufwand verringert: Beim Addieren von 1 ändern sich nur die abschließenden 9en, die zu 0en werden, und die erste Ziffer links davon. Alle anderen Ziffern bleiben unverändert.

Mit Übertrag addieren, Ziffer für Ziffer

Idee

Schreibe die Zahl auf und addiere 1 unter ihrer letzten Ziffer, wie in der Schule. Beginne mit einem Übertrag von 1, der 1, die du addierst. Bei jeder Ziffer von rechts ist die Spaltensumme die Ziffer plus der Übertrag. Ihre letzte Ziffer, total % 10, kommt in die Antwort, und ihre Zehnerziffer, total / 10, ist der Übertrag für die nächste Spalte.

Bei einem Übertrag von 1 ist eine Spaltensumme höchstens 9 + 1 = 10, daher ist der Übertrag immer 0 oder 1. Wenn nach der ersten Ziffer noch ein Übertrag übrig ist, erhält die Antwort eine neue führende Ziffer: Für 999 + 1 wird eine vierte Stelle für die 1 von 1000 benötigt.

Die Antwort entsteht zuletzt mit der letzten Ziffer zuerst, denn in dieser Reihenfolge berechnest du sie. Sammle sie in dieser Reihenfolge und kehre sie am Ende um. Das kostet O(n) Zeit und ein neues Array mit bis zu n + 1 Ziffern.

Algorithmus

Setze carry auf 1 und beginne mit einer leeren Liste für das Ergebnis.
Berechne für jede Ziffer von der letzten bis zur ersten total = digit + carry.
Füge total % 10 zum Ergebnis hinzu und setze carry auf total / 10, abgerundet.
Füge nach der Schleife carry hinzu, wenn es 1 ist.
Kehre das Ergebnis um und gib es 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

Beim ersten Wert unter 9 anhalten

Idee

Beobachte, was mit dem Übertrag passiert, wenn du genau 1 addierst. Eine Ziffer kleiner als 9 übernimmt ihn: Aus 3 wird 4, der Übertrag wird 0, und jede Ziffer weiter links behält ihren Wert. Nur eine 9 gibt den Übertrag weiter, indem sie zu 0 wird. 1 zu addieren bedeutet also: Wandle die abschließenden 9en in 0en um und addiere dann 1 zur Ziffer direkt davor.

Gehe von der letzten Ziffer nach links. Bei einer 9 schreibst du 0 und machst weiter. Bei jeder anderen Ziffer erhöhst du sie um eins und gibst das Array sofort zurück, da sich links davon nichts ändern kann. Bei [2, 9, 0, 9] wird die letzte 9 zu 0, die 0 wird zu 1, und du hörst mit [2, 9, 1, 0] auf, ohne die ersten beiden Ziffern anzusehen.

Wenn die Schleife keine Ziffer kleiner als 9 findet, war jede Ziffer eine 9 und ist nun 0. Die Zahl war 10^n - 1, daher besteht die Antwort aus einer 1 gefolgt von n Nullen. Nur in diesem Fall ist ein neues Array erforderlich. In allen anderen Fällen änderst du die Eingabe direkt, sodass der zusätzliche Speicherbedarf O(1) beträgt, und die Schleife läuft einmal pro abschließender 9 plus einen weiteren Schritt.

Algorithmus

Gehe die Indizes vom letzten 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 eine 9: Gib 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

Die Stolperfallen sind ein Ganzzahlüberlauf und der Fall mit lauter 9en.

Das Array in eine Ganzzahl und wieder zurück umwandeln. Bei kleinen Tests funktioniert es, doch bei den 100-stelligen Zahlen schlägt es fehl: Eine 64-Bit-Ganzzahl kann höchstens 19 oder 20 Ziffern speichern, und eine Gleitkommazahl verliert die letzten Ziffern sogar noch früher.
Die zusätzliche Ziffer vergessen. [9, 9, 9] muss zu [1, 0, 0, 0] werden, also zu vier Ziffern. Code, der nur die vorhandenen Stellen überschreibt, gibt [0, 0, 0] zurück.
Die erste statt der letzten Ziffer um 1 erhöhen. Das Array ist mit der höchstwertigen Ziffer zuerst angeordnet, daher steht die Einerziffer am Ende.
Vergessen, nach einer Ziffer kleiner als 9 zurückzukehren, die den Übertrag aufnimmt. Bei der Version mit vorzeitigem Abbruch läuft die Schleife weiter und ändert Ziffern, die unverändert bleiben müssen. Bei [1, 9, 3] darf sich nur die 3 ändern; das Ergebnis ist [1, 9, 4].
Die Reihenfolge der Indizes in Lua und R verwechseln, wo Arrays bei 1 beginnen: Die letzte Ziffer hat den Index n, und eine neue führende 1 kommt vor Index 1.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Plus One?

Beide Ansätze benötigen für n Ziffern eine Laufzeit von O(n), da im schlimmsten Fall, bei lauter 9ern, jede Ziffer berücksichtigt wird. Die Version mit vorzeitigem Abbruch stoppt nach den abschließenden 9ern und benötigt daher bei einer Zahl, die mit einer Ziffer kleiner als 9 endet, einen Schritt. Sie benötigt zusätzlichen Speicherplatz von O(1), außer wenn das Ergebnis eine neue führende Ziffer benötigt.

Warum wandeln wir die Ziffern nicht in eine Ganzzahl um?

Da die Zahl 100 Ziffern haben kann und eine 64-Bit-Ganzzahl bei etwa 1.8 × 10^19 endet, also bei 20 Ziffern, funktioniert die Umwandlung in Python und Ruby, da diese Sprachen Ganzzahlen ohne Größenbeschränkung haben. Das verschleiert jedoch den Sinn der Übung und lässt sich nicht auf andere Sprachen übertragen. Die Verarbeitung Ziffer für Ziffer führt nie zu einem Überlauf.

Wann hat das Ergebnis mehr Stellen als die Eingabe?

Nur wenn jede Ziffer 9 ist. Dann ist die Zahl 10^n - 1, und wenn man eins addiert, erhält man 10^n: eine 1, gefolgt von n Nullen. Wenn eine Ziffer kleiner als 9 ist, nimmt sie den Übertrag auf, sodass die Länge gleich bleibt.

Wie addiert man zwei Zahlen, die als Ziffernfelder gespeichert sind?

Verwende die Spaltenmethode aus dem ersten Ansatz mit zwei Indizes, je einem am Ende jedes Arrays. Addiere in jeder Spalte die beiden Ziffern, wobei eine fehlende Ziffer als 0 behandelt wird, sowie den Übertrag. Fahre fort, bis beide Arrays vollständig durchlaufen sind und der Übertrag 0 beträgt, und kehre dann die gesammelten Ziffern um.

Python

def plusOne(digits):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

digits = [4, 3, 9]

Erwartet

[4, 4, 0]