Программирование

Задачи с собеседований: Leetcode — Сложите два числа (Add Two Numbers)

Вам даны два непустых связанных списка, представляющих два неотрицательных целых числа. Цифры хранятся в обратном порядке, и каждый из их узлов содержит одну цифру. Сложите эти два числа и верните сумму в виде связанного списка.

Опубликовано

2 месяца назад

24.10.2024

Автор:

AppTractor

Задача

Можно предположить, что эти два числа не содержат никаких ведущих нулей, кроме самого числа 0.

Пример:

Ввод: l1 = [2,4,3], l2 = [5,6,4]
Вывод: [7,0,8]
Объяснение: 342 + 465 = 807.

Пример:

Ввод: l1 = [0], l2 = [0]
Вывод: [0]

Пример:

Ввод: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Вывод: [8,9,9,9,0,0,0,1]

Ограничения

Количество узлов в каждом связанном списке находится в диапазоне [1, 100].
0 <= Значение каждого узла <= 9
Гарантируется, что список представляет собой число, не содержащее ведущих нулей.

Ссылка

Сложите два числа на Leetcode: https://leetcode.com/problems/add-two-numbers/

Решение

Так как связанные списки и так представляют собой числа от меньшего разряда к большему, нам просто надо идти по списку и последовательно складывать их элементы (ноды). Здесь возникает две задачи.

Во-первых, надо учитывать «переполнение» разряда — если сумма превышает 9, то нужно в текущую узел ответа записать 0 и к следующему добавить 1. Если элемент последний, то надо добавить новый узел с 1.

Во-вторых, разницу в длине двух чисел — если мы в одном числе дошли до конца, а второе еще не кончилось, то для первого надо просто брать 0.

В результате получается такой код:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {

        var l1 = l1
        var l2 = l2
        let dummyNode = ListNode(0)
        var current: ListNode? = dummyNode
        var carry = 0
        
        while l1 != nil || l2 != nil || carry != 0 {
            let x = l1?.val ?? 0
            let y = l2?.val ?? 0
            let sum = carry + x + y
            carry = sum / 10
            current?.next = ListNode(sum % 10)
            current = current?.next
            
            if l1 != nil { l1 = l1?.next }
            if l2 != nil { l2 = l2?.next }
        }
        
        return dummyNode.next
    }
}

Пояснение:

ListNode — это определение класса узла списка, где каждый узел хранит целочисленное значение и ссылку на следующий узел.
Мы используем два указателя (l1 и l2), чтобы пройтись по двум входным спискам.
Для суммирования значений с учётом переноса (carry), мы проходим по каждому узлу обоих списков.
Если одно из чисел короче, недостающие значения считаем как 0.
После суммирования на каждом шаге создается новый узел списка с результатом суммы.
Перенос (carry) учитывается для следующего узла.
Если после завершения списков остается перенос, создается дополнительный узел.

Этот код эффективно решает задачу, поддерживая сложность O(n), где n — длина более длинного списка.

Такое решение эффективнее всего по скорости работы и вряд ли его можно оптимизировать еще больше:

Однако оно же является худшим по потреблению памяти:

Оптимизация памяти

Чтобы минимизировать потребление памяти при решении задачи Сложения двух чисел, мы можем адаптировать алгоритм так, чтобы использовать существующие узлы входных списков вместо создания новых. Это уменьшит количество дополнительной памяти, необходимой для хранения результатов.

Ключевые моменты для оптимизации:

Избегаем создания новых узлов, где это возможно, изменяя значения существующих узлов входных списков.
Работаем напрямую с входными данными, модифицируя их на месте.

Оптимизированный алгоритм на Swift:

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var l1 = l1
        var l2 = l2
        var carry = 0
        let head = l1 // Используем первый список для результата

        var prev: ListNode? = nil
        
        while l1 != nil || l2 != nil || carry != 0 {
            let x = l1?.val ?? 0
            let y = l2?.val ?? 0
            let sum = carry + x + y
            carry = sum / 10

            if l1 != nil {
                l1!.val = sum % 10
                prev = l1
                l1 = l1?.next
            } else {
                // Если l1 закончился, присоединяем l2, и модифицируем его
                prev?.next = l2
                prev = l2
                l2!.val = sum % 10
                l2 = l2?.next
            }

            if l2 != nil {
                l2 = l2?.next
            }
        }
        
        if carry > 0 {
            prev?.next = ListNode(carry)
        }

        return head
    }
}

Пояснение:

Использование существующих узлов: Вместо создания нового списка, мы изменяем первый входной список l1 на месте, чтобы сохранить результат. Это позволяет минимизировать использование памяти.
Модификация на месте: Цифры из второго списка l2 прибавляются к первому, и результат записывается в узлы l1. Когда первый список заканчивается, оставшиеся узлы из второго списка используются для хранения результата.
Перенос: Если после завершения прохода по спискам остается ненулевой перенос, мы создаем только один новый узел для этого.

Преимущества:

Этот подход избегает лишнего выделения памяти для новых узлов и использует уже существующие структуры данных.
Потребление памяти сведено к минимуму, поскольку новый узел создается только в случае необходимости для хранения конечного переноса.

Таким образом, этот алгоритм эффективно использует память, работая в основном с уже существующими узлами. Правда, проверить это в текущих условиях невозможно, потому что Leetcode падает с ошибкой переполнения.

Другая оптимизация

Как пишут, этот подход оптимизирует использование пространства за счет предварительного распределения узлов для результирующего связанного списка и повторного использования узлов из входных списков, где это возможно.

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let dummy = ListNode(0)
        var current = dummy
        var p = l1
        var q = l2
        var carry = 0

        while p != nil || q != nil {
            let x = p?.val ?? 0
            let y = q?.val ?? 0
            let sum = carry + x + y
            carry = sum / 10

            current.next = p ?? q
            current.next?.val = sum % 10

            current = current.next!
            if p != nil { p = p?.next }
            if q != nil { q = q?.next }
        }

        if carry > 0 {
            current.next = ListNode(carry)
        }

        return dummy.next
    }
}

Его временная сложность O(n). Оптимизированный итерационный подход также обрабатывает каждый узел l1 и l2 ровно один раз. Каждая итерация включает в себя операции с постоянным временем, такие как извлечение значения, вычисление суммы, обработка переноса и переназначение узлов. В результате временная сложность является линейной (O(n)) по отношению к длине длинного списка.

Пространственная сложность O(1). Этот подход оптимизирует использование пространства за счет повторного использования существующих узлов из входных списков вместо создания новых узлов. Единственное дополнительное пространство, которое требуется, — это несколько вспомогательных переменных (dummy, current, p, q и carry), которые не зависят от размера входных данных. Следовательно, пространственная сложность постоянна (O(1)), что делает этот подход более компактным по сравнению с другими решениями.