Reverse the Digits

Q: Wie kehrt man die Ziffern einer Zahl um, ohne sie in eine Zeichenkette umzuwandeln?

Wiederhole zwei Schritte, bis die Zahl 0 ist: Nimm die letzte Ziffer mit n % 10 und hänge sie mit result = result * 10 + digit an das Ergebnis an. Entferne sie dann mit n = n / 10 mithilfe der ganzzahligen Division. Bei 1234 wächst das Ergebnis zu 4, 43, 432 und 4321.

EinsteigerMathe und Simulation

+10

Du erhältst eine nicht negative ganze Zahl n. Gib die Zahl zurück, die entsteht, wenn du ihre Dezimalziffern in umgekehrter Reihenfolge schreibst. Nullen, die dadurch vorne stehen, werden weggelassen, sodass aus 120 21 wird.

Funktion

reverseDigits(n: integer) → integer

ninteger: die nichtnegative ganze Zahl, die umgekehrt werden soll
Gibt zurückinteger: die Ziffern von n in umgekehrter Reihenfolge, als Zahl

Einschränkungen

0 ≤ n < 10⁹
Die umgekehrte Zahl passt ebenfalls in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: n = 1234
Ausgabe: 4321
Erklärung: Die Ziffern von 1234 sind 1, 2, 3 und 4. Vom Ende aus gelesen sind sie 4, 3, 2 und 1, also 4321.

Eingabe: n = 120
Ausgabe: 21
Erklärung: Rückwärts gelesen ergeben sich bei 120 die Ziffern 0, 2 und 1. Eine führende Null zählt in einer Zahl nicht, daher lautet die Antwort 21.

Eingabe: n = 0
Ausgabe: 0
Erklärung: 0 hat eine einzelne Ziffer, und wenn man sie umdreht, erhält man wieder 0.

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Wenn n eine beliebige 32-Bit-Ganzzahl sein könnte, passt ihre umgekehrte Darstellung möglicherweise nicht. Wie würdest du das erkennen, bevor die Multiplikation einen Überlauf verursacht?

Tipps

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

0 von 3 geöffnet

Lösung

Das Umkehren der Dezimalzahl als Text ist in den meisten Sprachen eine Zeile lang und eine gute erste Antwort. Interviewer fragen meist nach einer Lösung, die dasselbe Ergebnis ohne Zeichenketten liefert. Die arithmetische Variante basiert auf zwei Operationen: n % 10 liest die letzte Ziffer aus und n / 10 (Ganzzahldivision) entfernt sie.

Den Dezimaltext umkehren

Idee

Die Ziffern einer Zahl sind genau die Zeichen ihres Dezimaltexts. Wandle n in Text um, kehre die Zeichen um und lies den Text wieder als Zahl ein. Aus 1234 wird "1234", dann "4321", dann 4321.

Die führenden Nullen erledigen sich von selbst. Wenn du 120 umkehrst, erhältst du den Text "021", und beim Einlesen als Zahl wird die Null vorne ignoriert und 21 zurückgegeben.

Eine Zahl unter 10^9 hat höchstens 9 Ziffern, und sowohl der Aufwand als auch der zusätzliche Text wachsen mit der Anzahl der Ziffern, also mit O(log n).

Algorithmus

Wandle n in seinen Dezimaltext um.
Kehre die Zeichenfolge um.
Wandle den umgekehrten Text in eine Ganzzahl um und gib sie zurück.

def reverseDigits(n):
    # int() ignores the leading zeros that trailing zeros turn into.
    return int(str(n)[::-1])

Ziffern mit arithmetischen Operationen auslesen und hinzufügen

Idee

Nimm die Ziffern von n einzeln von hinten ab und hänge jede an das Ende einer neuen Zahl an. n % 10 ist die letzte Ziffer von n, und n / 10 mit Ganzzahldivision entfernt sie. Um die Ziffer d an das Ende von result anzuhängen, verschiebe den bisherigen Wert um eine Stelle nach links und setze d an die Einerstelle: result * 10 + d.

Bei 1234 nimmt result die Werte 4, 43, 432, 4321 an, während n die Werte 123, 12, 1, 0 annimmt. Die Schleife endet, wenn n 0 erreicht, läuft also einmal pro Ziffer.

Führende Nullen treten nie auf. Bei 120 ist die erste entnommene Ziffer 0, und 0 * 10 + 0 ist weiterhin 0, sodass sie keine Spur hinterlässt. Für n = 0 wird die Schleife nie ausgeführt und das Ergebnis ist 0. Es werden nur zwei Ganzzahlen gespeichert, daher beträgt der zusätzliche Speicherbedarf O(1).

Algorithmus

Setze result = 0.
Solange n größer als 0 ist, berechne die letzte Ziffer n % 10.
Setze result = result * 10 + digit.
Entferne die Ziffer mit n = n / 10 unter Verwendung der Ganzzahldivision.
Gib result zurück.

def reverseDigits(n):
    result = 0
    while n > 0:
        result = result * 10 + n % 10  # push the last digit of n
        n //= 10                        # drop it from n
    return result

Stolperfallen und Grenzfälle

Die meisten Fehler entstehen durch Division und durch das Ende der Schleife.

Gewöhnliche Division verwenden, obwohl du ganzzahlige Division brauchst. In JavaScript, Python 3 und Lua ergibt n / 10 den Wert 123.4, sodass n nie wieder eine ganze Zahl wird und result sich mit Nachkommastellen füllt. Verwende Math.floor, // oder die ganzzahlige Division deiner Sprache.
Die Schleife als while n >= 10 schreiben. Sie stoppt vor der letzten Ziffer, sodass 1234 als 432 zurückkommt.
Den umgekehrten Text zurückgeben, ohne ihn zu parsen. "021" ist nicht die Zahl 21, und der Vergleich mit der erwarteten Antwort schlägt fehl.
Eine Zahl mit doppelter Genauigkeit in R mit as.character formatieren. Wenn n als Zahl mit doppelter Genauigkeit gespeichert ist, wird 100000000 als 1e+08 ausgegeben, und der umgekehrte Text lautet 80+e1. Verwende format(n, scientific = FALSE).

Häufige Fragen4

Wie kehrt man die Ziffern einer Zahl um, ohne sie in eine Zeichenkette umzuwandeln?

Wiederhole zwei Schritte, bis die Zahl 0 ist: Nimm die letzte Ziffer mit n % 10 und hänge sie mit result = result * 10 + digit an das Ergebnis an. Entferne sie dann mit n = n / 10 mithilfe der ganzzahligen Division. Bei 1234 wächst das Ergebnis zu 4, 43, 432 und 4321.

Was passiert beim Umkehren einer Zahl mit nachgestellten Nullen?

Sie würden zu führenden Nullen werden, die eine Zahl nicht hat, und verschwinden daher. Das Umkehren von 120 ergibt 21, und das Umkehren von 100000000 ergibt 1. Die Rechenschleife lässt sie von selbst weg, denn wenn man 0 zu einem leeren Ergebnis addiert, bleibt es bei 0.

Wie hoch ist die Zeitkomplexität beim Umkehren einer Ganzzahl?

Die Schleife wird einmal pro Dezimalziffer ausgeführt, und eine Zahl n hat ungefähr log10(n) + 1 Ziffern, daher beträgt die Laufzeit O(log n). Die arithmetische Variante benötigt O(1) zusätzlichen Speicherplatz; die String-Variante speichert die Ziffern als Text, was O(log n) entspricht.

Kann das Umkehren einer Ganzzahl einen Überlauf verursachen?

Ja, wenn die Eingabe eine beliebige 32-Bit-Ganzzahl sein kann. 1000000009 passt, aber ihre Umkehrung 9000000001 nicht. Hier ist n kleiner als 10^9, daher hat die Umkehrung höchstens 9 Ziffern und passt immer. Prüfe bei größeren Eingaben vor jeder Multiplikation result > (INT_MAX - digit) / 10.

Python

def reverseDigits(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

n = 1234

Erwartet