Palindrome Number
Un numero è palindromo quando le sue cifre si leggono allo stesso modo da sinistra a destra e da destra a sinistra, come 1221. Dato un intero x, restituisci true se è palindromo e false altrimenti. Un numero negativo non conta mai, perché il suo segno meno non ha un corrispondente all'altra estremità.
Funzione
- xinteger
- l'intero da controllare, eventualmente negativo
- Restituisceboolean
- true se x si legge allo stesso modo in entrambe le direzioni, false altrimenti
Vincoli
-231 ≤ x ≤ 231-1- Ogni numero negativo restituisce
false.
Esempi
- Input
- x = 121
- Output
- true
- Spiegazione
- Letto al contrario, 121 è ancora 121, quindi la risposta è
true.
- Input
- x = -121
- Output
- false
- Spiegazione
- Letto al contrario,
-121diventa121-, che è un testo diverso, quindi la risposta èfalse.
Per approfondire
Riesci a risolverlo senza convertire l’intero in una stringa?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
I numeri negativi non possono mai essere palindromi, quindi gestiscili per primi.
Prendi l’ultima cifra con
x % 10e rimuovila usando la divisione intera per10.Costruisci il numero invertito con
reversed = reversed * 10 + digit, poi confrontalo con l’originale.
Soluzione
Un numero è palindromo quando è uguale al suo inverso. Come testo, basta un confronto. Senza convertirlo in testo, ricostruire l'intero numero al contrario può causare un overflow, quindi inverti solo la seconda metà delle cifre e confrontala con la prima metà.
Confronta la stringa con la sua inversa
Intuizione
Scrivi il numero come testo e confrontalo con il suo inverso. I numeri negativi non richiedono casi speciali: -121 inizia con un segno meno e termina con una cifra, quindi non è mai uguale al suo inverso 121-.
Il testo ha un carattere per cifra, circa log10(x) caratteri e al massimo 11 qui. Il costo è la stringa aggiuntiva.
Algoritmo
- Converti
xin una stringas. - Inverti
s. - Restituisci se
sè uguale al suo inverso.
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]Inverti metà del numero
Intuizione
x % 10 dà l'ultima cifra, mentre la divisione intera per 10 la rimuove. Spostando le cifre dalla fine di x a un secondo numero half, si costruisce l'inverso delle cifre rimosse. Fermati quando half è almeno pari a ciò che resta di x: avrai preso metà delle cifre. 1221 termina con x = 12 e half = 12, un palindromo. Con un numero dispari di cifre, half contiene anche la cifra centrale: 12321 termina con x = 12 e half = 123, quindi confronti x con half / 10.
Gestisci due casi prima del ciclo. Un numero negativo non è mai un palindromo. Un numero che termina con 0 dovrebbe iniziare con 0, cosa che vale solo per 0; senza questo controllo, 10 termina con x = 0 e half = 1, e x == half / 10 risulta vero per errore. half non supera mai 6 cifre, quindi è compatibile con qualsiasi tipo intero.
Algoritmo
- Se
xè negativo, oppure termina con 0 e non è 0, restituiscifalse. - Imposta
half = 0. - Mentre
x > half, impostahalf = half * 10 + x % 10e dividixper 10 con divisione intera. - Restituisci
truesex == half(numero pari di cifre) oppurex == half / 10(numero dispari di cifre).
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
Trappole e casi limite
- Dimenticare i numeri negativi. Nei linguaggi in cui il resto mantiene il segno, invertire
-121dà-121e il controllo ha esito positivo. In Python, dove-1 // 10è-1, un ciclowhile x != 0non termina mai. - Non rifiutare i numeri che terminano con 0. L’inversione della metà accetta quindi
10.0è un palindromo. - Invertire l’intero numero in un intero a 32 bit. L’inverso di
2147483647non rientra nell’intervallo. - Usare
/quando il linguaggio esegue la divisione con una frazione. UsaMath.floor(x / 10)in JavaScript,//in Python,%/%in R e~/in Dart. - Confrontare l’inverso completo con
xdopo che il ciclo ha modificatox. Conserva una copia del valore originale.
Domande frequenti3
Un numero negativo è palindromo?
No. Letto al contrario, -121 diventa 121- e il segno meno non ha un carattere corrispondente all’altra estremità. Quindi ogni intero negativo restituisce false.
Perché invertire solo metà del numero?
Invertire ogni cifra può causare un overflow di un intero a 32 bit: il numero invertito di 2147483647 è più grande del più grande int. Metà delle cifre entra sempre, e il ciclo fa metà del lavoro.
Qual è la complessità temporale di Palindrome Number?
Entrambi gli approcci hanno una complessità temporale di O(log x), perché un numero x ha circa log10(x) cifre e ognuna viene gestita una volta. L’approccio con stringa usa O(log x) spazio aggiuntivo per il testo; l’inversione di metà numero usa O(1).
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def isPalindrome(x):
# Scrivi il codice quiTest #1
Test #2
Argomento
x = 121
Output atteso
true