Agregue una solución Leetcode de dos números en Python PyPixel

Analizaremos la solución Leetcode Agregar dos números en Python, que es un problema de Leetcode medio (n.º 2).
El problema «Sumar dos números» en LeetCode presenta un desafío interesante al sumar dos enteros no negativos representados por listas vinculadas. Los dígitos de estos números se almacenan en orden inverso y cada nodo de la lista vinculada contiene un dígito. La tarea consiste en realizar la suma y devolver el resultado como una lista vinculada.

Planteamiento del problema

te dan dos no vacío Listas enlazadas que representan dos números enteros no negativos. Los dígitos se almacenan en orden inverso, y cada uno de sus nodos contiene un dígito. Suma los dos números y devuelve la suma como una lista vinculada.

Puedes suponer que ambos números no contienen ceros a la izquierda, excepto el propio número 0.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Enlace al problema de Leetcode: https://leetcode.com/problems/add-two-numbers/

Solución

Enfoque de fuerza bruta

Detalles:

1. Convertir a número: Las listas enlazadas se recorren para convertir cada dígito en un número entero y se suman los dos números enteros resultantes.
2. Realizar suma: Luego, la suma se vuelve a convertir en una lista vinculada, con cada dígito representado por un nodo.

Resumen:

• La solución de fuerza bruta implica convertir listas vinculadas a números enteros, realizar una suma y luego convertir el resultado nuevamente a una lista vinculada.
• La complejidad del tiempo está dominada por los pasos de conversión, lo que la hace menos eficiente para números grandes.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbersBruteForce(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        num1 = self.convert_to_number(l1)
        num2 = self.convert_to_number(l2)
        result = num1 + num2

        return self.convert_to_linked_list(result)

    def convert_to_number(self, node):
        result = 0
        multiplier = 1

        while node:
            result += node.val * multiplier
            multiplier *= 10
            node = node.next

        return result

    def convert_to_linked_list(self, number):
        dummy = ListNode()
        current = dummy

        for digit in str(number)[::-1]:
            current.next = ListNode(int(digit))
            current = current.next

        return dummy.next

Complejidad del tiempo:

• Conversión a número: O(n) donde n es la longitud de la lista vinculada más larga.
• Conversión a lista enlazada: O(m) donde m es el número de dígitos de la suma.

Enfoque óptimo

Detalles:

1. Iteración con dos punteros: De manera similar a la mejor solución, dos punteros atraviesan ambas listas vinculadas simultáneamente.
2. Realizar suma: La suma se realiza dígito a dígito, teniendo en cuenta cualquier remanente del paso anterior.
3. Cree una lista de resultados: El resultado se genera en el lugar y se devuelve una nueva lista vinculada.

Resumen:

• La solución óptima comparte similitudes con la mejor solución pero minimiza el uso de variables y combina la lógica de la suma con la iteración.
• Mantiene la eficiencia y maneja casos extremos de manera efectiva.

class Solution:
    def addTwoNumbersOptimal(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        current = dummy
        carry = 0

        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0

            total_sum = x + y + carry
            carry, digit = divmod(total_sum, 10)

            current.next = ListNode(digit)
            current = current.next

            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        return dummy.next

Complejidad del tiempo:

• Iterando a través de listas: O(max(n, m)) donde num son las longitudes de las listas enlazadas de entrada.

Entonces, estas dos fueron las soluciones brutas y óptimas para el problema de sumar dos números leetcode en Python. Espero que haya entendido bien la solución y pueda resolver este problema mediante iteraciones.

Algo que te pueda gustar: