Skip to content

Add Two Numbers

Ссылки:

  1. https://leetcode.com/problems/add-two-numbers/description/

Решение (первое, переполнение)

<?php

class ListNode
{
    public $val = 0;
    public $next = null;

    function __construct($val = 0, $next = null)
    {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution
{

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2)
    {

        $n1 = '';
        $n2 = '';
        $current1 = $l1;
        $current2 = $l2;

        while ($current1 || $current2) {
            if ($current1) {
                $n1 .= $current1->val;
                $current1 = $current1->next;
            }
            if ($current2) {
                $n2 .= $current2->val;
                $current2 = $current2->next;
            }
        }

        $result = (int)strrev($n1) + (int)strrev($n2);
        $result = (int)$result;
        $pointer = $curPointer = new ListNode($result % 10);
        $result = intdiv($result, 10);

        while ($result > 0) {
            $curPointer->next = new ListNode($result % 10);
            $curPointer = $curPointer->next;
            $result = intdiv($result, 10);
        }

        return $pointer;
    }
}

Проблема

У нас есть два числа, представленных в виде связанных списков, где каждая цифра числа хранится в узле списка в обратном порядке (например, число 465 представлено как список [5, 6, 4]). Нужно сложить эти два числа и вернуть результат также в виде связанного списка, где цифры результата снова будут расположены в обратном порядке.

Ошибка в исходном решении:

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

  • Если числа большие, то может возникнуть переполнение при работе с большими числами, что и вызывает неправильные результаты, как, например, -8
  • Преобразование в строки и обратно не подходит для сложения очень длинных чисел (как в случае с l1, где много нулей и единицы в начале и конце).

Решение

Чтобы избежать проблем с переполнением, мы будем складывать числа побитно, то есть цифра к цифре, с учетом переноса (если сумма двух цифр превышает 9).

Как работает решение:

  1. Создаем вспомогательный узел (dummy node): Мы создаем фиктивный узел dummy, который будет указывать на начало нового списка, где будет храниться результат.
  2. Проходим по обоим спискам одновременно: Мы начинаем проходить по обоим связанным спискам, начиная с самой младшей цифры каждого числа (поскольку числа хранятся в обратном порядке).

  3. Если один из списков короче другого, мы просто считаем недостающие цифры как

    javascript 0

    . * Складываем соответствующие цифры и добавляем к ним значение переноса (

    javascript carry

    ), если оно есть. 3. Обрабатываем перенос (carry): Если сумма двух цифр больше 9, то перенос (единица) передается на следующую итерацию. Например, если складываем 6 и 7, получаем 13, записываем в текущий узел 3, а 1 (перенос) передаем на следующий шаг. 4. Продолжаем до конца списков: Мы продолжаем суммировать, пока не обработаем все цифры из обоих списков. Если по завершении работы над обоими списками у нас остался перенос, добавляем новый узел с этим значением. 5. Возвращаем результат: Так как результат хранится в узлах, начиная с фиктивного узла dummy, конечный результат — это список, который начинается с dummy->next.

Пример:

Возьмем два числа:

  • l1 = [1, 0, 0, 0, ..., 0, 1] (очень большое число),
  • l2 = [5, 6, 4] (число 465).

Складываем их:

  • Сначала складываем младшие цифры: 1 + 5 = 6 (записываем 6 в результат).
  • Далее: 0 + 6 = 6 (записываем 6).
  • Далее: 0 + 4 = 4 (записываем 4).
  • Остальные цифры — это нули, и в конце списков добавляется 1 из первого числа.

Итого: результат будет [6, 6, 4, 0, 0, ..., 0, 1].

Код:

<?php 

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $dummy = new ListNode(0);
        $current = $dummy;
        $carry = 0;


        while ($l1 !== null || $l2 !== null || $carry !== 0) {
            $x = ($l1 !== null) ? $l1->val : 0;
            $y = ($l2 !== null) ? $l2->val : 0;
            $sum = $x + $y + $carry;
            $carry = intdiv($sum, 10);
            $current->next = new ListNode($sum % 10);
            $current = $current->next;
            if ($l1 !== null) $l1 = $l1->next;
            if ($l2 !== null) $l2 = $l2->next;
        }
        return $dummy->next;
    }
}

\