Add Two Numbers
Se te dan dos números enteros no negativos, cada uno almacenado como una lista enlazada simple de sus dígitos, con el dígito menos significativo primero. En la primera lista, el nodo i contiene el dígito values1[i] y apunta al nodo next1[i]. La segunda lista funciona de la misma manera con next2 y values2. En ambas listas, -1 marca el final de la lista y la cabeza es el nodo 0. Los nodos no están almacenados en el orden de la lista, así que sigue los enlaces.
Devuelve los dígitos de la suma de los dos números, con el dígito menos significativo primero.
Función
- next1integer-array
- el índice del nodo al que apunta cada nodo del primer número, o -1 para su último nodo
- values1integer-array
- el dígito que contiene cada nodo del primer número
- next2integer-array
- el índice del nodo al que se conecta cada nodo del segundo número, o -1 para su último nodo
- values2integer-array
- el dígito que contiene cada nodo del segundo número
- Devuelveinteger-array
- los dígitos de la suma, empezando por el menos significativo
Restricciones
1 ≤ L1 ≤ 100, dondeL1es la longitud denext1y devalues1.1 ≤ L2 ≤ 100, dondeL2es la longitud denext2y devalues2.0 ≤ values1[i], values2[j] ≤ 9- Cada elemento de
next1es-1o un índice de nodo de la primera lista, y cada elemento denext2es-1o un índice de nodo de la segunda lista. - Empezando en el nodo
0, cada lista visita cada uno de sus nodos exactamente una vez y después llega a-1. No hay ningún ciclo. - No hay ningún número con ceros iniciales: el último nodo de una lista contiene un dígito distinto de
0, a menos que la lista sea el dígito0.
Ejemplos
- Entrada
- next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
- Salida
- [5, 4, 1, 1]
- Explicación
- La primera lista visita los nodos
0, 2, 1y lee8, 1, 6, el número 618. La segunda lee7, 2, 5, el número 527. Su suma es 1145, así que la respuesta es5, 4, 1, 1.
- Entrada
- next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
- Salida
- [0, 0, 0, 0, 1]
- Explicación
- La segunda lista se lee como
1, 9, 9, 9, el número 9991. Al sumar 9 se obtiene 10000: cada columna produce un0y un acarreo, y el último acarreo se convierte en un quinto dígito.
- Entrada
- next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
- Salida
- [7, 5]
- Explicación
- El primer número es 0 y la segunda lista se lee como
7, 5, el número 57. Sumar 0 no cambia nada, así que la respuesta es[7, 5].
Para ir más allá
¿Cómo sumarías los números si las listas almacenaran primero el dígito más significativo?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Convertir cada lista en un número falla: 100 dígitos no caben en ningún tipo entero. ¿Cómo sumas dos números largos en papel?
Las listas empiezan por la cifra de las unidades, que es exactamente donde empieza la suma en columnas. Cada columna suma una cifra de cada número más el acarreo de la columna anterior. La columna escribe
sum % 10y acarreasum / 10, redondeado hacia abajo.Recorre ambas listas a la vez con un puntero para cada una. A la lista que se haya agotado se le agrega
0. Continúa mientras alguno de los punteros no sea-1o el acarreo sea1, para que un acarreo final se convierta en un dígito más.
Solución
Los números son demasiado largos para cualquier tipo entero, así que súmalos como en el papel: columna por columna, llevando un 1 cuando una columna llega a 10. Las listas almacenan primero el dígito de las unidades, así que recorrerlas visita las columnas en el orden en que las sumas.
Copia los dígitos y después súmalos columna por columna
Intuición
Un puntero aquí es un índice de nodo, y avanzar es node = next[node]. Copia los dígitos de cada lista en un arreglo, de modo que el índice i contenga el dígito que vale 10^i: [8, 1, 6] y [7, 2, 5] en el primer ejemplo.
Después suma como en papel, contando un dígito faltante como 0. En cada columna se escribe sum % 10 y se lleva el resto: 8 + 7 = 15 escribe 5 y lleva 1, 1 + 2 + 1 = 4, y 6 + 5 = 11 escribe 1. El último acarreo se convierte en un dígito final: [5, 4, 1, 1].
Las copias cuestan O(L1 + L2) de memoria adicional que la suma nunca necesita.
Algoritmo
- Recorre cada lista desde el nodo
0y copia sus dígitos en un arreglo. - Establece
carry = 0. Para cada índiceihasta la longitud del arreglo más largo, suma los dígitos que existan eniy el acarreo. - Añade
sum % 10y establececarryensum / 10, redondeado hacia abajo. - Si el acarreo es
1después de la última columna, añádelo.
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 resultRecorre ambas listas a la vez con un acarreo
Intuición
La columna i usa solo el nodo i-ésimo de cada lista, así que mantén un puntero por lista, a y b, y avanza ambos a medida que pasan las columnas.
Un bucle se ejecuta mientras a no sea -1, o b no sea -1, o el acarreo sea 1. Un puntero que todavía tiene un nodo suma su dígito y avanza; un puntero en -1 no suma nada. Esto maneja números de distintas longitudes sin un segundo bucle, y la condición del acarreo escribe el dígito adicional al final.
En el segundo ejemplo, 9 más 9991, cada columna suma 10 y escribe 0. Después de cuatro columnas, ambas listas terminan, pero el acarreo es 1, así que el bucle se ejecuta una vez más: [0, 0, 0, 0, 1]. Aparte de la respuesta, mantiene tres enteros.
Algoritmo
- Establece
a = 0,b = 0ycarry = 0. - Mientras
a != -1ob != -1ocarry > 0, inicia la suma de la columna encarry. - Si
a != -1, sumavalues1[a]y establecea = next1[a]. Haz lo mismo parabcon la segunda lista. - Agrega
sum % 10y establececarryensum / 10, redondeado hacia abajo. - Devuelve los dígitos que agregaste.
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
Errores comunes y casos límite
- Convertir cada lista en un entero y sumarlas. Un número de 100 dígitos desborda cualquier tipo de 64 bits.
- Descartar el acarreo final. Un bucle que se detiene cuando ambas listas terminan devuelve
[0, 0, 0, 0]para el segundo ejemplo. - Detenerse cuando termina la lista más corta. Después, en el segundo ejemplo se pierden los tres 9 de 9991 y el acarreo que pasa por ellos.
- Leer los dígitos en el orden del arreglo. En el primer ejemplo,
values1es[8, 6, 1], pero el número es 618, leído siguiendo los enlaces. - Olvidar el desplazamiento en Lua y R, donde los arreglos empiezan en 1. Mantén los identificadores de nodo basados en 0 y lee
next1[node + 1].
Preguntas frecuentes3
¿Por qué se almacenan los dígitos en orden inverso en Add Two Numbers?
La suma empieza por la cifra de las unidades, y una lista simplemente enlazada solo se puede recorrer desde su cabeza. Si el dígito menos significativo va primero, el recorrido visita las columnas en el orden en que las sumas, así que el acarreo avanza junto con los punteros.
¿Cuál es la complejidad temporal de sumar dos números almacenados como listas enlazadas?
Es O(max(L1, L2)): un paso por columna, más uno cuando queda un acarreo al final. Aparte de la respuesta, la versión de una sola pasada usa memoria O(1): dos punteros y el acarreo.
¿Puede el acarreo ser alguna vez mayor que 1?
No. Una columna suma dos dígitos de como máximo 9 y un acarreo de como máximo 1, así que su suma es como máximo 19. Al dividir entre 10 y redondear hacia abajo, se obtiene 0 o 1.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def addTwoNumbers(next1, values1, next2, values2):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
next1 = [2, -1, 1] values1 = [8, 6, 1] next2 = [2, -1, 1] values2 = [7, 5, 2]
Salida Esperada
[5, 4, 1, 1]