Add Two Numbers
Você recebe dois números inteiros não negativos, cada um armazenado como uma lista simplesmente encadeada de seus dígitos, com o dígito menos significativo primeiro. Na primeira lista, o nó i contém o dígito values1[i] e aponta para o nó next1[i]. A segunda lista funciona da mesma forma, com next2 e values2. Em ambas as listas, -1 marca o fim da lista, e o nó 0 é a cabeça. Os nós não estão armazenados na ordem da lista, então siga os links.
Retorne os dígitos da soma dos dois números, com o dígito menos significativo primeiro.
Função
- next1integer-array
- o índice do nó para o qual cada nó do primeiro número aponta, ou -1 para seu último nó
- values1integer-array
- o dígito armazenado por cada nó do primeiro número
- next2integer-array
- o índice do nó ao qual cada nó do segundo número se liga, ou -1 para seu último nó
- values2integer-array
- o dígito armazenado em cada nó do segundo número
- Retornainteger-array
- os dígitos da soma, começando pelo menos significativo
Restrições
1 ≤ L1 ≤ 100, ondeL1é o comprimento denext1e devalues1.1 ≤ L2 ≤ 100, em queL2é o comprimento denext2e devalues2.0 ≤ values1[i], values2[j] ≤ 9- Cada entrada de
next1é-1ou um índice de nó da primeira lista, e cada entrada denext2é-1ou um índice de nó da segunda lista. - A partir do nó
0, cada lista visita cada um de seus nós exatamente uma vez e, em seguida, chega a-1. Não há ciclo. - Nenhum número tem zeros à esquerda: o último nó de uma lista contém um dígito diferente de
0, a menos que a lista seja o dígito único0.
Exemplos
- Entrada
- next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
- Saída
- [5, 4, 1, 1]
- Explicação
- A primeira lista visita os nós
0, 2, 1e lê8, 1, 6, o número 618. A segunda lê7, 2, 5, o número 527. A soma deles é 1145, então a resposta é5, 4, 1, 1.
- Entrada
- next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
- Saída
- [0, 0, 0, 0, 1]
- Explicação
- A segunda lista representa
1, 9, 9, 9, o número 9991. Somar 9 resulta em 10000: cada coluna produz um0e um transporte, e o último transporte se torna um quinto dígito.
- Entrada
- next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
- Saída
- [7, 5]
- Explicação
- O primeiro número é 0 e a segunda lista corresponde a
7, 5, o número 57. Somar 0 não muda nada, então a resposta é[7, 5].
Para ir além
Como você somaria os números se as listas armazenassem o dígito mais significativo primeiro?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Transformar cada lista em um número não dá certo: 100 dígitos não cabem em nenhum tipo inteiro. Como você soma dois números grandes no papel?
As listas começam pelo algarismo das unidades, exatamente onde começa a adição em colunas. Cada coluna soma um algarismo de cada número mais o vai-um da coluna anterior. A coluna escreve
sum % 10e levasum / 10, arredondado para baixo.Percorra as duas listas ao mesmo tempo, com um ponteiro para cada uma. Uma lista que acabou soma
0. Continue enquanto qualquer um dos ponteiros for diferente de-1ou o transporte for1, para que um transporte final se torne mais um dígito.
Solução
Os números são longos demais para qualquer tipo inteiro, então some-os como no papel: coluna por coluna, levando um 1 quando uma coluna chega a 10. As listas armazenam primeiro o dígito das unidades, então percorrê-las visita as colunas na ordem em que você as soma.
Copie os algarismos e depois some coluna por coluna
Intuição
Um ponteiro aqui é um índice de nó, e avançar é node = next[node]. Copie os dígitos de cada lista para um array, de modo que o índice i contenha o dígito que vale 10^i: [8, 1, 6] e [7, 2, 5] no primeiro exemplo.
Em seguida, some como no papel, considerando um dígito ausente como 0. Em cada coluna, escreva sum % 10 e transporte o restante: 8 + 7 = 15 escreve 5 e transporta 1, 1 + 2 + 1 = 4, e 6 + 5 = 11 escreve 1. O último valor transportado torna-se um dígito final: [5, 4, 1, 1].
As cópias custam O(L1 + L2) de memória extra, da qual a soma nunca precisa.
Algoritmo
- Percorra cada lista a partir do nó
0e copie seus dígitos para um array. - Defina
carry = 0. Para cada índiceiaté o comprimento do array mais longo, some os dígitos existentes no índiceie o carry. - Adicione
sum % 10e definacarrycomosum / 10, arredondado para baixo. - Se o carry for
1após a última coluna, adicione-o.
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 resultPercorra as duas listas ao mesmo tempo, mantendo um vai-um
Intuição
A coluna i usa apenas o nó de índice i de cada lista, então mantenha um ponteiro por lista, a e b, e avance ambos conforme as colunas passam.
Um loop é executado enquanto a não for -1, ou b não for -1, ou o vai-um for 1. Um ponteiro que ainda tem um nó soma seu dígito e avança; um ponteiro em -1 não soma nada. Isso lida com números de comprimentos diferentes sem um segundo loop, e a condição do vai-um grava o dígito extra no final.
No segundo exemplo, 9 mais 9991, cada coluna soma 10 e grava 0. Depois de quatro colunas, as duas listas terminam, mas o vai-um é 1, então o loop é executado mais uma vez: [0, 0, 0, 0, 1]. Além da resposta, ele mantém três inteiros.
Algoritmo
- Defina
a = 0,b = 0ecarry = 0. - Enquanto
a != -1oub != -1oucarry > 0, comece a soma da coluna comcarry. - Se
a != -1, somevalues1[a]e definaa = next1[a]. Faça o mesmo parabcom a segunda lista. - Adicione
sum % 10e definacarrycomosum / 10, arredondado para baixo. - Retorne os dígitos que você adicionou.
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
Armadilhas e casos extremos
- Converter cada lista em um inteiro e somar. Um número de 100 dígitos excede qualquer tipo de 64 bits.
- Descartar o carry final. Um loop que para quando ambas as listas terminam retorna
[0, 0, 0, 0]para o segundo exemplo. - Parar quando a lista mais curta termina. O segundo exemplo então perde os três 9s de 9991 e o carry que passa por eles.
- Ler os dígitos na ordem do array. No primeiro exemplo,
values1é[8, 6, 1], mas o número é 618, lido ao longo dos links. - Esquecer o deslocamento em Lua e R, onde os arrays começam em 1. Mantenha os ids dos nós baseados em 0 e leia
next1[node + 1].
Perguntas frequentes3
Por que os dígitos são armazenados na ordem inversa em Add Two Numbers?
A adição começa pelo algarismo das unidades, e só é possível percorrer uma lista simplesmente encadeada a partir de sua cabeça. Com o algarismo menos significativo primeiro, o percurso visita as colunas na ordem em que você as soma, então o vai-um avança junto com os ponteiros.
Qual é a complexidade de tempo de somar dois números armazenados como listas encadeadas?
É O(max(L1, L2)): um passo por coluna, mais um quando sobra um vai-um no final. Além da resposta, a versão de passagem única usa memória O(1): dois ponteiros e o vai-um.
O vai-um pode ser maior que 1?
Não. Uma coluna soma dois dígitos de no máximo 9 e um vai-um de no máximo 1, então sua soma é no máximo 19. Dividir por 10 e arredondar para baixo resulta em 0 ou 1.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def addTwoNumbers(next1, values1, next2, values2):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
next1 = [2, -1, 1] values1 = [8, 6, 1] next2 = [2, -1, 1] values2 = [7, 5, 2]
Saída Esperada
[5, 4, 1, 1]