Add Two Numbers
Ti vengono forniti due numeri interi non negativi, ciascuno memorizzato come lista concatenata semplice delle sue cifre, con la cifra meno significativa per prima. Nella prima lista, il nodo i contiene la cifra values1[i] e punta al nodo next1[i]. La seconda lista funziona allo stesso modo con next2 e values2. In entrambe le liste, -1 indica la fine della lista e la testa è il nodo 0. I nodi non sono memorizzati nell'ordine della lista, quindi segui i collegamenti.
Restituisci le cifre della somma dei due numeri, dalla meno significativa alla più significativa.
Funzione
- next1integer-array
- l'indice del nodo a cui è collegato ciascun nodo del primo numero, oppure -1 per il suo ultimo nodo
- values1integer-array
- la cifra rappresentata da ciascun nodo del primo numero
- next2integer-array
- l'indice del nodo a cui è collegato ciascun nodo del secondo numero, oppure -1 per il suo ultimo nodo
- values2integer-array
- la cifra contenuta in ciascun nodo del secondo numero
- Restituisceinteger-array
- le cifre della somma, dalla meno significativa alla più significativa
Vincoli
1 ≤ L1 ≤ 100, doveL1è la lunghezza dinext1e divalues1.1 ≤ L2 ≤ 100, doveL2è la lunghezza dinext2e divalues2.0 ≤ values1[i], values2[j] ≤ 9- Ogni elemento di
next1è-1o un indice di nodo della prima lista, e ogni elemento dinext2è-1o un indice di nodo della seconda lista. - A partire dal nodo
0, ciascuna lista visita ognuno dei suoi nodi esattamente una volta e poi raggiunge-1. Non c'è alcun ciclo. - Nessun numero ha zeri iniziali: l'ultimo nodo di una lista contiene una cifra diversa da
0, a meno che la lista non sia la singola cifra0.
Esempi
- Input
- next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
- Output
- [5, 4, 1, 1]
- Spiegazione
- La prima lista visita i nodi
0, 2, 1e legge8, 1, 6, il numero 618. La seconda legge7, 2, 5, il numero 527. La loro somma è 1145, quindi la risposta è5, 4, 1, 1.
- Input
- next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
- Output
- [0, 0, 0, 0, 1]
- Spiegazione
- La seconda lista si legge
1, 9, 9, 9, il numero 9991. Aggiungendo 9 si ottiene 10000: ogni colonna produce uno0e un riporto, e l'ultimo riporto diventa una quinta cifra.
- Input
- next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
- Output
- [7, 5]
- Spiegazione
- Il primo numero è 0 e la seconda lista legge
7, 5, il numero 57. Aggiungere 0 non cambia nulla, quindi la risposta è[7, 5].
Per approfondire
Come sommeresti i numeri se le liste memorizzassero per primo la cifra più significativa?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Convertire ogni lista in un numero non funziona: 100 cifre non entrano in nessun tipo intero. Come si sommano due numeri lunghi su carta?
Le liste iniziano dalla cifra delle unità, che è esattamente il punto da cui inizia l'addizione in colonna. Ogni colonna somma una cifra di ciascun numero più il riporto della colonna precedente. La colonna scrive
sum % 10e riportasum / 10, arrotondato per difetto.Scorri entrambe le liste contemporaneamente, con un puntatore per ciascuna. Aggiungi
0alla lista che è terminata. Continua finché almeno uno dei due puntatori non è-1oppure il riporto è1, così un riporto finale diventa un'altra cifra.
Soluzione
I numeri sono troppo lunghi per qualsiasi tipo intero, quindi sommali come faresti sulla carta: colonna per colonna, riportando un 1 quando una colonna arriva a 10. Le liste memorizzano prima la cifra delle unità, quindi percorrerle visita le colonne nell’ordine in cui le sommi.
Copia le cifre, poi somma colonna per colonna
Intuizione
Un puntatore qui è un indice di nodo e spostarsi in avanti significa node = next[node]. Copia le cifre di ogni lista in un array, così che l’indice i contenga la cifra del valore 10^i: [8, 1, 6] e [7, 2, 5] nel primo esempio.
Poi somma come sulla carta, contando una cifra mancante come 0. In ogni colonna si scrive sum % 10 e si riporta il resto: 8 + 7 = 15 scrive 5 e riporta 1, 1 + 2 + 1 = 4 e 6 + 5 = 11 scrive 1. L’ultimo riporto diventa una cifra finale: [5, 4, 1, 1].
Le copie richiedono memoria aggiuntiva O(L1 + L2) che l’addizione non necessita mai.
Algoritmo
- Percorri ogni lista dal nodo
0e copia le sue cifre in un array. - Imposta
carry = 0. Per ogni indiceifino alla lunghezza dell'array più lungo, somma le cifre presenti all'indiceie il riporto. - Aggiungi
sum % 10e impostacarryasum / 10, arrotondato per difetto. - Se il riporto è
1dopo l'ultima colonna, aggiungilo.
def readDigits(next, values):
# The digits in list order: least significant first.
digits = []
node = 0
while node != -1:
digits.append(values[node])
node = next[node]
return digits
def addTwoNumbers(next1, values1, next2, values2):
first = readDigits(next1, values1)
second = readDigits(next2, values2)
result = []
carry = 0
for i in range(max(len(first), len(second))):
column = carry
if i < len(first):
column += first[i]
if i < len(second):
column += second[i]
result.append(column % 10)
carry = column // 10
if carry > 0:
result.append(carry)
return resultScorri entrambe le liste contemporaneamente con un riporto
Intuizione
La colonna i usa solo il nodo i-esimo di ogni lista, quindi mantieni un puntatore per lista, a e b, e spostali man mano che procedono le colonne.
Un ciclo continua finché a non è -1, oppure b non è -1, oppure il riporto è 1. Un puntatore che ha ancora un nodo aggiunge la sua cifra e avanza; un puntatore a -1 non aggiunge nulla. Questo gestisce numeri di lunghezze diverse senza un secondo ciclo, e la condizione sul riporto scrive la cifra aggiuntiva alla fine.
Nel secondo esempio, 9 più 9991, ogni colonna dà come somma 10 e scrive 0. Dopo quattro colonne entrambe le liste sono esaurite, ma il riporto è 1, quindi il ciclo viene eseguito ancora una volta: [0, 0, 0, 0, 1]. Oltre alla risposta, mantiene tre interi.
Algoritmo
- Imposta
a = 0,b = 0ecarry = 0. - Mentre
a != -1ob != -1ocarry > 0, inizia la somma della colonna dacarry. - Se
a != -1, aggiungivalues1[a]e impostaa = next1[a]. Fai lo stesso perbcon la seconda lista. - Aggiungi
sum % 10e impostacarryasum / 10, arrotondato per difetto. - Restituisci le cifre che hai aggiunto.
def addTwoNumbers(next1, values1, next2, values2):
a = 0 # current node of the first number
b = 0 # current node of the second number
carry = 0
result = []
# Keep going while either number has digits left or a carry is waiting.
while a != -1 or b != -1 or carry > 0:
column = carry
if a != -1:
column += values1[a]
a = next1[a]
if b != -1:
column += values2[b]
b = next2[b]
result.append(column % 10) # the digit this column writes
carry = column // 10 # 1 when the column reached 10, else 0
return result
Trappole e casi limite
- Convertire ogni lista in un intero ed eseguire la somma. Un numero di 100 cifre supera la capacità di qualsiasi tipo a 64 bit.
- Scartare il riporto finale. Un ciclo che si ferma quando entrambe le liste finiscono restituisce
[0, 0, 0, 0]per il secondo esempio. - Fermarsi quando termina la lista più corta. Nel secondo esempio, così si perdono i tre 9 di 9991 e il riporto che li attraversa.
- Leggere le cifre nell’ordine dell’array. Nel primo esempio
values1è[8, 6, 1], ma il numero è 618, letto seguendo i collegamenti. - Dimenticare l’offset in Lua e R, dove gli array iniziano da 1. Mantenere gli ID dei nodi con indice da 0 e leggere
next1[node + 1].
Domande frequenti3
Perché le cifre sono memorizzate in ordine inverso in Add Two Numbers?
L’addizione inizia dalla cifra delle unità e una lista collegata singolarmente può essere percorsa solo dalla testa. Con la cifra meno significativa per prima, il percorso visita le colonne nell’ordine in cui le sommi, quindi il riporto avanza insieme ai puntatori.
Qual è la complessità temporale dell’addizione di due numeri memorizzati come liste concatenate?
È O(max(L1, L2)): un passaggio per colonna, più uno quando rimane un riporto alla fine. A parte la risposta, la versione a passaggio singolo usa memoria O(1): due puntatori e il riporto.
Il riporto può mai essere maggiore di 1?
No. Una colonna somma due cifre al massimo pari a 9 e un riporto al massimo pari a 1, quindi la somma è al massimo 19. Dividendo per 10 e arrotondando per difetto si ottiene 0 oppure 1.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def addTwoNumbers(next1, values1, next2, values2):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
next1 = [2, -1, 1] values1 = [8, 6, 1] next2 = [2, -1, 1] values2 = [7, 5, 2]
Output atteso
[5, 4, 1, 1]