Plus One

Q: Qual è la complessità temporale di Plus One?

Entrambi gli approcci vengono eseguiti in tempo O(n) per n cifre, perché nel caso peggiore, con tutte cifre 9, viene esaminata ogni cifra. La versione con uscita anticipata si ferma dopo gli eventuali 9 finali, quindi per un numero che termina con una cifra minore di 9 esegue un solo passaggio. Usa spazio aggiuntivo O(1) , tranne quando il risultato richiede una nuova cifra iniziale.

Q: Quando il risultato ha più cifre dell’input?

Solo quando ogni cifra è 9. In quel caso il numero è 10^n - 1 e aggiungendo uno si ottiene 10^n : un 1 seguito da n zeri. Se una qualsiasi cifra è inferiore a 9, assorbe il riporto, quindi la lunghezza rimane invariata.

FacileMatematica e simulazione

+10

Un numero intero non negativo è memorizzato come un array delle sue cifre decimali, digits, con la cifra più significativa per prima: 472 è [4, 7, 2]. Aggiungi uno al numero e restituisci le cifre del risultato nello stesso formato. Il numero può avere fino a 100 cifre, molte più di quante ne possa contenere un intero a 64 bit.

Funzione

plusOne(digits: integer-array) → integer-array

digitsinteger-array: le cifre del numero, dalla più significativa alla meno significativa
Restituisceinteger-array: le cifre del numero più uno, dalla più significativa alla meno significativa

Vincoli

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits non ha zeri iniziali, tranne il numero 0 stesso, che è [0].

Esempi

Input: digits = [4, 3, 9]
Output: [4, 4, 0]
Spiegazione: Il numero è 439 e 439 + 1 = 440. L'ultima cifra 9 diventa 0 e riporta un riporto al 3, che diventa 4.

Input: digits = [0]
Output: [1]
Spiegazione: Il numero 0 si scrive [0] e 0 + 1 = 1.

+13 test nascosti all’invio

Per approfondire

Come sottrarresti uno, invece, a un numero di almeno 1? Quali cifre cambiano e quando il risultato perde la cifra iniziale, come in [1, 0, 0]?

Soluzione

Convertire le cifre in un numero, aggiungere uno e riconvertire non funziona in questo caso: 100 cifre superano il limite di qualsiasi intero a 64 bit, che si ferma intorno a 1.8 × 10^19. Quindi si esegue l’addizione come si fa sulla carta, partendo dall’ultima cifra e riportando il resto. Un’osservazione riduce il lavoro: aggiungere 1 modifica solo i 9 finali, che diventano 0, e la prima cifra alla loro sinistra. Tutte le altre cifre restano come sono.

Aggiungere con il riporto, cifra per cifra

Intuizione

Scrivi il numero e aggiungi 1 sotto la sua ultima cifra, come a scuola. Inizia con un riporto di 1, quello che stai aggiungendo. Per ogni cifra, da destra, il totale della colonna è la cifra più il riporto. La sua ultima cifra, total % 10, va nella risposta, mentre la cifra delle decine, total / 10, è il riporto per la colonna successiva.

Con un riporto di 1, il totale di una colonna è al massimo 9 + 1 = 10, quindi il riporto è sempre 0 o 1. Se resta un riporto dopo la prima cifra, la risposta guadagna una nuova cifra iniziale: 999 + 1 richiede una quarta posizione per l'1 di 1000.

La risposta viene fuori partendo dall'ultima cifra, perché è questo l'ordine in cui la calcoli. Raccoglila in quest'ordine e inverti l'ordine alla fine. Questo richiede un tempo O(n) e un nuovo array con fino a n + 1 cifre.

Algoritmo

Imposta carry su 1 e crea una lista vuota per la risposta.
Per ogni cifra, dall'ultima alla prima, calcola total = digit + carry.
Aggiungi total % 10 alla risposta e imposta carry su total / 10, arrotondato per difetto.
Dopo il ciclo, se carry è 1, aggiungilo.
Inverti la risposta e restituiscila.

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

Fermati alla prima cifra inferiore a 9

Intuizione

Osserva cosa succede al riporto quando aggiungi esattamente 1. Una cifra minore di 9 lo assorbe: 3 diventa 4, il riporto diventa 0 e ogni cifra più a sinistra mantiene il proprio valore. Solo un 9 trasmette il riporto, trasformandosi in 0. Quindi aggiungere 1 significa: trasformare gli 9 finali in 0, poi aggiungere 1 alla cifra che li precede.

Procedi dall’ultima cifra verso sinistra. Se trovi un 9, scrivi 0 e continua. Con qualsiasi altra cifra, aumentala di uno e restituisci subito l’array, perché nulla alla sua sinistra può cambiare. Per [2, 9, 0, 9] l’ultimo 9 diventa 0, lo 0 diventa 1 e ti fermi con [2, 9, 1, 0] senza esaminare le prime due cifre.

Se il ciclo non trova mai una cifra minore di 9, tutte le cifre erano 9 e ora sono 0. Il numero era 10^n - 1, quindi il risultato è un 1 seguito da n zeri. Questo è l’unico caso che richiede un nuovo array. In tutti gli altri casi modifichi l’input direttamente, quindi lo spazio aggiuntivo è O(1) e il ciclo viene eseguito una volta per ogni 9 finale, più un altro passaggio.

Algoritmo

Scorri gli indici dall’ultimo al primo.
Se la cifra è minore di 9, incrementala di uno e restituisci l’array.
Altrimenti la cifra è 9: impostala a 0 e spostati di una posizione a sinistra.
Se il ciclo termina, tutte le cifre erano 9: restituisci 1 seguito da n zeri.

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

Trappole e casi limite

Le insidie sono l'overflow degli interi e il caso di tutti 9.

Trasformare l'array in un intero e poi di nuovo in un array. Supera i test piccoli, poi fallisce con quelli da 100 cifre: un intero a 64 bit contiene al massimo 19 o 20 cifre, mentre un numero in virgola mobile perde le ultime cifre ancora prima.
Dimenticare la cifra extra. [9, 9, 9] deve diventare [1, 0, 0, 0], quattro cifre. Il codice che riscrive solo le posizioni esistenti restituisce [0, 0, 0].
Aggiungere 1 alla prima cifra anziché all'ultima. L'array è ordinato dalla cifra più significativa alla meno significativa, quindi la cifra delle unità si trova alla fine.
Dimenticare di restituire il risultato dopo che una cifra minore di 9 ha assorbito il riporto. Nella versione con uscita anticipata, il ciclo continua e modifica cifre che dovrebbero restare invariate. In [1, 9, 3] può cambiare solo il 3; la risposta è [1, 9, 4].
Confondere l'ordine degli indici in Lua e R, dove gli array iniziano da 1: l'ultima cifra si trova all'indice n, e un nuovo 1 iniziale va inserito prima dell'indice 1.

Domande frequenti4

Qual è la complessità temporale di Plus One?

Entrambi gli approcci vengono eseguiti in tempo O(n) per n cifre, perché nel caso peggiore, con tutte cifre 9, viene esaminata ogni cifra. La versione con uscita anticipata si ferma dopo gli eventuali 9 finali, quindi per un numero che termina con una cifra minore di 9 esegue un solo passaggio. Usa spazio aggiuntivo O(1), tranne quando il risultato richiede una nuova cifra iniziale.

Perché non convertire le cifre in un intero?

Poiché il numero può avere 100 cifre e un intero a 64 bit arriva solo a circa 1.8 × 10^19, ovvero 20 cifre. Python e Ruby hanno interi illimitati, quindi la conversione funziona in quei linguaggi, ma nasconde lo scopo dell’esercizio e non è applicabile ad altri linguaggi. Lavorare cifra per cifra evita sempre l’overflow.

Quando il risultato ha più cifre dell’input?

Solo quando ogni cifra è 9. In quel caso il numero è 10^n - 1 e aggiungendo uno si ottiene 10^n: un 1 seguito da n zeri. Se una qualsiasi cifra è inferiore a 9, assorbe il riporto, quindi la lunghezza rimane invariata.

Come si sommano due numeri memorizzati come array di cifre?

Usa il metodo delle colonne del primo approccio con due indici, uno alla fine di ciascun array. Ogni colonna somma le due cifre, considerando una cifra mancante come 0, più il riporto. Continua finché entrambi gli array non sono esauriti e il riporto è 0, poi inverti le cifre raccolte.

Python

def plusOne(digits):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

digits = [4, 3, 9]

Atteso

[4, 4, 0]