Reverse the Digits

Q: Come inverti le cifre di un numero senza convertirlo in una stringa?

Ripeti due passaggi finché il numero non è 0 : prendi l’ultima cifra con n % 10 e aggiungila al risultato con result = result * 10 + digit , poi rimuovila con n = n / 10 usando la divisione intera. Per 1234 il risultato cresce così: 4, 43, 432 e 4321.

PrincipianteMatematica e simulazione

+10

Ti viene dato un numero intero non negativo n. Restituisci il numero che ottieni scrivendo le sue cifre decimali in ordine inverso. Gli zeri che finiscono all’inizio vengono eliminati, quindi 120 diventa 21.

Funzione

reverseDigits(n: integer) → integer

ninteger: l'intero non negativo da invertire
Restituisceinteger: le cifre di n in ordine inverso, come numero

Vincoli

0 ≤ n < 10⁹
Anche il numero invertito rientra in un intero con segno a 32 bit.

Esempi

Input: n = 1234
Output: 4321
Spiegazione: Le cifre di 1234 sono 1, 2, 3 e 4. Letti dalla fine, sono 4, 3, 2 e 1, ovvero 4321.

Input: n = 120
Output: 21
Spiegazione: Letto al contrario, 120 dà le cifre 0, 2 e 1. Uno zero iniziale non conta in un numero, quindi la risposta è 21.

Input: n = 0
Output: 0
Spiegazione: 0 ha una sola cifra e invertirlo dà di nuovo 0.

+13 test nascosti all’invio

Per approfondire

Se n potesse essere un qualsiasi intero a 32 bit, il suo valore invertito potrebbe non rientrare. Come lo rileveresti prima che la moltiplicazione vada in overflow?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Invertire il testo decimale richiede una sola riga nella maggior parte dei linguaggi, ed è una prima risposta valida. Gli intervistatori di solito chiedono poi di ottenere lo stesso risultato senza stringhe. La versione aritmetica si basa su due operazioni: n % 10 legge l’ultima cifra e n / 10 (divisione intera) la rimuove.

Inverti il testo decimale

Intuizione

Le cifre di un numero sono esattamente i caratteri della sua rappresentazione decimale testuale. Converti n in testo, inverti i caratteri e riconverti il testo in un numero. 1234 diventa "1234", poi "4321", poi 4321.

Gli zeri iniziali si gestiscono da soli. Invertendo 120 si ottiene il testo "021" e, analizzandolo come numero, lo zero iniziale viene ignorato e si ottiene 21.

Un numero minore di 10^9 ha al massimo 9 cifre, e sia il lavoro sia il testo aggiuntivo crescono con il numero di cifre, che è O(log n).

Algoritmo

Converti n nel suo testo decimale.
Inverti i caratteri.
Analizza il testo invertito come numero intero e restituiscilo.

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

Inserire e rimuovere cifre con l’aritmetica

Intuizione

Rimuovi una alla volta le cifre dalla fine di n e aggiungi ciascuna alla fine di un nuovo numero. n % 10 è l’ultima cifra di n, mentre n / 10 con divisione intera la elimina. Per aggiungere una cifra d alla fine di result, sposta di una posizione a sinistra ciò che c’è già e metti d nella posizione delle unità: result * 10 + d.

Per 1234, result diventa 4, 43, 432, 4321, mentre n diventa 123, 12, 1, 0. Il ciclo si ferma quando n raggiunge 0, quindi viene eseguito una volta per ogni cifra.

Gli zeri iniziali non compaiono mai. Per 120, la prima cifra prelevata è 0, e 0 * 10 + 0 è ancora 0, quindi non lascia traccia. Per n = 0, il ciclo non viene mai eseguito e la risposta è 0. Si conservano solo due interi, quindi lo spazio aggiuntivo è O(1).

Algoritmo

Imposta result = 0.
Finché n è maggiore di 0, calcola l'ultima cifra n % 10.
Imposta result = result * 10 + digit.
Elimina la cifra con n = n / 10, usando la divisione intera.
Restituisci result.

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

Trappole e casi limite

La maggior parte degli errori deriva dalla divisione e dalla fine del ciclo.

Usare la divisione ordinaria quando serve la divisione intera. In JavaScript, Python 3 e Lua, n / 10 dà 123.4, quindi n non torna mai a essere un numero intero e result si riempie di frazioni. Usa Math.floor, // o la divisione intera del tuo linguaggio.
Scrivere il ciclo come while n >= 10. Si ferma prima dell'ultima cifra, quindi 1234 diventa 432.
Restituire il testo invertito senza convertirlo in numero. "021" non è il numero 21 e il confronto con la risposta attesa non riesce.
Formattare un double in R con as.character. Quando n è memorizzato come double, stampa 100000000 come 1e+08 e il testo invertito è 80+e1. Usa format(n, scientific = FALSE).

Domande frequenti4

Come inverti le cifre di un numero senza convertirlo in una stringa?

Ripeti due passaggi finché il numero non è 0: prendi l’ultima cifra con n % 10 e aggiungila al risultato con result = result * 10 + digit, poi rimuovila con n = n / 10 usando la divisione intera. Per 1234 il risultato cresce così: 4, 43, 432 e 4321.

Che cosa succede agli zeri finali quando inverti un numero?

Diventerebbero zeri iniziali, che un numero non ha, quindi scompaiono. Invertendo 120 si ottiene 21, e invertendo 100000000 si ottiene 1. Il ciclo aritmetico li elimina da solo, perché aggiungere 0 a un risultato vuoto lo lascia a 0.

Qual è la complessità temporale dell’inversione di un intero?

Il ciclo viene eseguito una volta per ogni cifra decimale e un numero n ha circa log10(n) + 1 cifre, quindi il tempo è O(log n). La versione aritmetica usa uno spazio aggiuntivo di O(1); la versione con stringhe memorizza le cifre come testo, con una complessità di O(log n).

Un'inversione può causare un overflow di un intero?

Sì, quando l'input può essere un qualsiasi intero a 32 bit. 1000000009 ci sta, ma il suo inverso 9000000001 no. Qui n è minore di 10^9, quindi l'inverso ha al massimo 9 cifre e ci sta sempre. Con input più grandi, controlla result > (INT_MAX - digit) / 10 prima di ogni moltiplicazione.

Python

def reverseDigits(n):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

n = 1234

Atteso