Plus One

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

Entrambi gli approcci richiedono un tempo O(n) per n cifre, perché il caso con tutti 9 tocca ogni cifra. La versione con uscita anticipata si ferma dopo i 9 finali e usa uno spazio aggiuntivo O(1) , tranne quando la risposta richiede una nuova cifra iniziale.

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 come [0], e 0 + 1 = 1.

Per approfondire

Come sottrarresti uno invece, per un numero di almeno 1? Quando il risultato perde la cifra iniziale, come in [1, 0, 0]?

Soluzione

Un numero di 100 cifre supera la capacità di qualsiasi intero a 64 bit, che arriva a circa 1.8 × 10^19, quindi non puoi convertirlo e sommarlo. Somma come faresti su carta, partendo dall’ultima cifra e riportando il riporto. Sommando 1 cambiano solo i 9 finali, che diventano 0, e la cifra alla loro sinistra.

Aggiungi con il riporto, cifra per cifra

Intuizione

Inizia con un riporto di 1, quello che stai aggiungendo. Per ogni cifra partendo da destra, il totale della colonna è la cifra più il riporto: total % 10 va nel risultato e total / 10 è il riporto successivo. Il totale è al massimo 9 + 1 = 10, quindi il riporto rimane 0 o 1. Un riporto che rimane dopo la prima cifra diventa una nuova cifra iniziale, come in 999 + 1 = 1000.

Produci il risultato iniziando dall'ultima cifra, quindi raccoglilo in quest'ordine e inverti l'ordine alla fine. Il tempo è O(n) e serve un nuovo array di fino a n + 1 cifre.

Algoritmo

Imposta carry a 1 e avvia 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 a 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

Una cifra minore di 9 assorbe un riporto di 1: aumenta di uno e ogni cifra alla sua sinistra mantiene il proprio valore. Solo un 9 trasmette il riporto, trasformandosi in 0. Quindi puoi fermarti alla prima cifra minore di 9 e restituire l’array di input, modificato sul posto. Per [2, 9, 0, 9] l’ultimo 9 diventa 0, lo 0 diventa 1 e restituisci [2, 9, 1, 0] senza leggere le prime due cifre.

Se nessuna cifra è minore di 9, il numero era 10^n - 1 e la risposta è 1 seguito da n zeri. Questo è l’unico caso che richiede un nuovo array, quindi lo spazio aggiuntivo è altrimenti O(1).

Algoritmo

Esamina gli indici dall’ultimo al primo.
Se la cifra è minore di 9, aumentala 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 dagli 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

Convertire l’array in un intero e poi di nuovo in un array. Un intero a 64 bit contiene al massimo 19 o 20 cifre, quindi 100 cifre causano un overflow, mentre un numero in virgola mobile perde le ultime cifre ancora prima.
Dimenticare la cifra aggiuntiva. [9, 9, 9] deve diventare [1, 0, 0, 0]; il codice che riscrive solo le posizioni esistenti restituisce [0, 0, 0].
Aggiungere 1 alla prima cifra. L’array è ordinato dalla cifra più significativa, quindi la cifra delle unità è l’ultimo elemento.
Non restituire il risultato quando una cifra inferiore a 9 assorbe il riporto. Il ciclo modifica quindi cifre che devono rimanere invariate: [1, 9, 3] deve diventare [1, 9, 4].
In Lua e R, gli array iniziano da 1, quindi l’ultima cifra è all’indice n, non n - 1.

Domande frequenti3

Qual è la complessità temporale di Plus One?

Entrambi gli approcci richiedono un tempo O(n) per n cifre, perché il caso con tutti 9 tocca ogni cifra. La versione con uscita anticipata si ferma dopo i 9 finali e usa uno spazio aggiuntivo O(1), tranne quando la risposta richiede una nuova cifra iniziale.

Perché non convertire le cifre in un intero?

Il numero può avere 100 cifre, mentre un intero a 64 bit si ferma a circa 1.8 × 10^19, ovvero 20 cifre. Python e Ruby hanno interi illimitati, quindi la conversione funziona in quei linguaggi, ma il codice non è trasferibile ad altri linguaggi. Lavorare cifra per cifra evita sempre l'overflow.

Come si sommano due numeri memorizzati come array di cifre?

Usa il metodo per colonne con un indice alla fine di ogni array. Ogni colonna somma le due cifre, considerando una cifra mancante come 0, più il riporto. Fermati quando entrambi gli array sono esauriti e il riporto è 0, quindi inverti le cifre raccolte.

def plusOne(digits):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

digits = [4, 3, 9]

Output atteso

[4, 4, 0]