Palindrome Number

Q: Ist eine negative Zahl ein Palindrom?

Nein. Rückwärts gelesen wird aus -121 121- , und das Minuszeichen hat am anderen Ende kein passendes Zeichen. Daher gibt jede negative ganze Zahl false zurück.

Q: Wie hoch ist die Zeitkomplexität von Palindrome Number?

Beide Ansätze haben eine Laufzeit von O(log x) , da eine Zahl x etwa log10(x) Ziffern hat und jede davon einmal verarbeitet wird. Der String-Ansatz benötigt für den Text zusätzlichen Speicherplatz von O(log x) ; die Umkehrung der Hälfte benötigt O(1) .

LeichtMathe und Simulation

+10

Eine Zahl ist ein Palindrom, wenn ihre Ziffern von links nach rechts und von rechts nach links gleich gelesen werden, wie bei 1221. Gib für eine ganze Zahl x true zurück, wenn sie ein Palindrom ist, andernfalls false. Eine negative Zahl zählt nie, da ihr Minuszeichen am anderen Ende kein Gegenstück hat.

Funktion

isPalindrome(x: integer) → boolean

xinteger: die zu prüfende Ganzzahl, möglicherweise negativ
Gibt zurückboolean: true, wenn x in beiden Richtungen gleich gelesen wird, andernfalls false

Einschränkungen

-2³¹ ≤ x ≤ 2³¹-1
Jede negative Zahl gibt false zurück.

Beispiele

Eingabe: x = 121
Ausgabe: true
Erklärung: Rückwärts gelesen ist 121 immer noch 121, also lautet die Antwort true.

Eingabe: x = -121
Ausgabe: false
Erklärung: Rückwärts gelesen wird aus -121 121-, was ein anderer Text ist, daher lautet die Antwort false.

Weiterführende Frage

Kannst du es lösen, ohne die Ganzzahl in eine Zeichenfolge umzuwandeln?

Tipps

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

0 von 3 geöffnet

Lösung

Eine Zahl ist ein Palindrom, wenn sie ihrer Umkehrung entspricht. Als Text ist das ein einziger Vergleich. Ohne Text kann das erneute Erstellen der gesamten umgekehrten Zahl zu einem Überlauf führen. Kehre daher nur die zweite Ziffernhälfte um und vergleiche sie mit der ersten Hälfte.

Vergleiche die Zeichenkette mit ihrer Umkehrung

Idee

Schreibe die Zahl als Text und vergleiche sie mit ihrer Umkehrung. Negative Zahlen erfordern keinen Sonderfall: -121 beginnt mit einem Minuszeichen und endet mit einer Ziffer, daher ist sie nie gleich ihrer Umkehrung 121-.

Der Text hat ein Zeichen pro Ziffer, etwa log10(x) Zeichen und hier höchstens 11. Der Nachteil ist die zusätzliche Zeichenkette.

Algorithmus

Wandle x in eine Zeichenkette s um.
Kehre s um.
Gib zurück, ob s seiner Umkehrung entspricht.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

Umgekehrte Hälfte der Zahl

Idee

x % 10 liefert die letzte Ziffer, und eine Ganzzahldivision durch 10 entfernt sie. Wenn du Ziffern vom Ende von x auf eine zweite Zahl half verschiebst, entsteht die Umkehrung der entfernten Ziffern. Beende den Vorgang, sobald half mindestens so groß ist wie der verbleibende Wert von x: Du hast die Hälfte der Ziffern übernommen. Bei 1221 endet der Vorgang mit x = 12 und half = 12 – einer Palindromzahl. Bei einer ungeraden Ziffernanzahl enthält half außerdem die mittlere Ziffer: Bei 12321 endet der Vorgang mit x = 12 und half = 123, also vergleichst du x mit half / 10.

Behandle vor der Schleife zwei Fälle. Eine negative Zahl ist niemals eine Palindromzahl. Eine Zahl, die auf 0 endet, müsste auch mit 0 beginnen, was nur bei 0 der Fall ist; ohne diese Prüfung endet 10 mit x = 0 und half = 1, und x == half / 10 ist fälschlicherweise erfüllt. half wächst nie über 6 Ziffern hinaus und passt daher in jeden ganzzahligen Datentyp.

Algorithmus

Wenn x negativ ist oder auf 0 endet und nicht 0 ist, gib false zurück.
Setze half = 0.
Solange x > half gilt, setze half = half * 10 + x % 10 und teile x durch 10 mit ganzzahliger Division.
Gib true zurück, wenn x == half (gerade Ziffernanzahl) oder x == half / 10 (ungerade Ziffernanzahl) gilt.

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

Stolperfallen und Grenzfälle

Negative Zahlen vergessen. In Sprachen, in denen der Rest das Vorzeichen beibehält, ergibt das Umkehren von -121 -121, und die Prüfung ist erfolgreich. In Python, wo -1 // 10 -1 ist, endet eine while x != 0-Schleife nie.
Zahlen, die mit 0 enden, nicht zurückweisen. Das Umkehren der Hälfte akzeptiert dann 10. 0 selbst ist ein Palindrom.
Die ganze Zahl in einer 32-Bit-Ganzzahl umkehren. Die Umkehrung von 2147483647 passt nicht hinein.
/ verwenden, obwohl die Sprache mit Brüchen dividiert. Verwende Math.floor(x / 10) in JavaScript, // in Python, %/% in R und ~/ in Dart.
Die vollständige Umkehrung mit x vergleichen, nachdem die Schleife x verändert hat. Behalte eine Kopie des ursprünglichen Werts.

Häufige Fragen3

Ist eine negative Zahl ein Palindrom?

Nein. Rückwärts gelesen wird aus -121 121-, und das Minuszeichen hat am anderen Ende kein passendes Zeichen. Daher gibt jede negative ganze Zahl false zurück.

Warum nur die Hälfte der Zahl umkehren?

Das Umkehren jeder Ziffer kann bei einer 32-Bit-Ganzzahl zu einem Überlauf führen: Die Umkehrung von 2147483647 ist größer als die größte int-Zahl. Die Hälfte der Ziffern passt immer, und die Schleife erledigt nur die Hälfte der Arbeit.

Wie hoch ist die Zeitkomplexität von Palindrome Number?

Beide Ansätze haben eine Laufzeit von O(log x), da eine Zahl x etwa log10(x) Ziffern hat und jede davon einmal verarbeitet wird. Der String-Ansatz benötigt für den Text zusätzlichen Speicherplatz von O(log x); die Umkehrung der Hälfte benötigt O(1).

def isPalindrome(x):
    # Schreibe hier den Code

Test #1

Test #2

Argument

x = 121

Erwartete Ausgabe

true