Add Two Numbers

Q: Какова временная сложность сложения двух чисел, хранящихся в связанных списках?

Это O(max(L1, L2)) : один шаг на столбец, плюс ещё один, если в конце остаётся перенос. Помимо ответа, версия с одним проходом использует память O(1) : два указателя и перенос.

СреднеСвязный список Математика и моделирование

+10

Даны два неотрицательных целых числа, каждое из которых хранится в виде односвязного списка цифр, начиная с цифры младшего разряда. В первом списке узел i содержит цифру values1[i] и связан с узлом next1[i]. Второй список устроен так же, с next2 и values2. В обоих списках -1 обозначает конец списка, а голова — это узел 0. Узлы хранятся не в порядке следования в списке, поэтому переходите по связям.

Верните цифры суммы этих двух чисел, начиная с цифры младшего разряда.

Функция

addTwoNumbers(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: индекс узла, на который ссылается каждый узел первого числа, или -1 для его последнего узла
values1integer-array: цифра, хранящаяся в каждом узле первого числа
next2integer-array: индекс узла, на который ссылается каждый узел второго числа, или -1 для его последнего узла
values2integer-array: цифра, хранящаяся в каждом узле второго числа
Возвращаетinteger-array: цифры суммы, начиная с младшей

Ограничения

1 ≤ L1 ≤ 100, где L1 — длина next1 и values1.
1 ≤ L2 ≤ 100, где L2 — длина next2 и values2.
0 ≤ values1[i], values2[j] ≤ 9
Каждый элемент next1 — это -1 или индекс узла первого списка, а каждый элемент next2 — это -1 или индекс узла второго списка.
Начиная с узла 0, каждый список посещает каждый из своих узлов ровно один раз, а затем достигает -1. Цикла нет.
Ни одно число не начинается с нулей: последний узел списка содержит цифру, отличную от 0, если только список не состоит из одной цифры 0.

Примеры

Ввод: next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
Вывод: [5, 4, 1, 1]
Пояснение: Первый список посещает узлы 0, 2, 1 и считывает 8, 1, 6, число 618. Второй считывает 7, 2, 5, число 527. Их сумма равна 1145, поэтому ответ — 5, 4, 1, 1.

Ввод: next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
Вывод: [0, 0, 0, 0, 1]
Пояснение: Второй список читается как 1, 9, 9, 9 — число 9991. Прибавление 9 даёт 10000: в каждом разряде получается 0 и перенос, а последний перенос становится пятой цифрой.

Ввод: next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
Вывод: [7, 5]
Пояснение: Первое число равно 0, а во втором списке указано 7, 5 — число 57. Добавление 0 ничего не меняет, поэтому ответ — [7, 5].

Дополнительный вопрос

Как бы вы сложили числа, если бы в списках первой хранилась самая значащая цифра?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Числа слишком длинные для любого целочисленного типа, поэтому складывай их, как на бумаге: по столбцам, перенося 1, когда сумма в столбце достигает 10. В списках сначала хранится цифра единиц, поэтому при проходе по ним столбцы встречаются в том же порядке, в котором ты их складываешь.

Перепишите цифры, затем складывайте по столбцам

Идея

Здесь указатель — это индекс узла, а переход к следующему узлу выполняется так: node = next[node]. Скопируй цифры каждого списка в массив, чтобы по индексу i хранилась цифра, соответствующая 10^i: [8, 1, 6] и [7, 2, 5] в первом примере.

Затем сложи числа столбиком, считая отсутствующую цифру равной 0. В каждом разряде запиши sum % 10, а остаток перенеси в следующий разряд: 8 + 7 = 15 — запиши 5 и перенеси 1, 1 + 2 + 1 = 4, а 6 + 5 = 11 — запиши 1. Последний перенос становится итоговой цифрой: [5, 4, 1, 1].

Для копий требуется дополнительная память объёмом O(L1 + L2), которая при сложении не нужна.

Алгоритм

Пройди по каждому списку, начиная с узла 0, и скопируй его цифры в массив.
Установи carry = 0. Для каждого индекса i до длины более длинного массива включительно сложи существующие цифры с индексом i и перенос.
Добавь sum % 10 и установи carry равным sum / 10, округлённому вниз.
Если после последнего разряда перенос равен 1, добавь его.

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 result

Одновременно пройдите по обоим спискам, перенося остаток

Идея

Столбец i использует только i-й узел каждого списка, поэтому сохраняй по одному указателю на список — a и b — и передвигай оба по мере прохода по столбцам.

Один цикл выполняется, пока a не равен -1, или b не равен -1, или перенос равен 1. Указатель, за которым ещё есть узел, добавляет его цифру и переходит дальше; указатель со значением -1 ничего не добавляет. Так обрабатываются числа разной длины без второго цикла, а условие с переносом записывает дополнительную цифру в конце.

Во втором примере, 9 плюс 9991, сумма в каждом столбце равна 10, и записывается 0. После четырёх столбцов оба списка заканчиваются, но перенос равен 1, поэтому цикл выполняется ещё раз: [0, 0, 0, 0, 1]. Помимо ответа, алгоритм хранит три целых числа.

Алгоритм

Установи a = 0, b = 0 и carry = 0.
Пока a != -1 или b != -1 или carry > 0, начинай сумму в столбик со значения carry.
Если a != -1, прибавь values1[a] и установи a = next1[a]. Сделай то же самое для b со вторым списком.
Добавь sum % 10 и установи carry равным sum / 10, округлённому вниз.
Верни добавленные цифры.

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

Ловушки и крайние случаи

Преобразование каждого списка в целое число и сложение. Число из 100 цифр переполняет любой 64-разрядный тип.
Пропуск последнего переноса. Цикл, который останавливается, когда заканчиваются оба списка, возвращает [0, 0, 0, 0] для второго примера.
Остановка, когда заканчивается более короткий список. Во втором примере тогда теряются три девятки числа 9991 и перенос, проходящий через них.
Чтение цифр в порядке массива. В первом примере values1 — это [8, 6, 1], но число равно 618, если читать его по связям.
Забывание о смещении в Lua и R, где массивы начинаются с 1. Оставляй идентификаторы узлов с отсчётом от 0 и читай next1[node + 1].

Частые вопросы3

Почему цифры хранятся в обратном порядке в задаче «Сложение двух чисел»?

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

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

Это O(max(L1, L2)): один шаг на столбец, плюс ещё один, если в конце остаётся перенос. Помимо ответа, версия с одним проходом использует память O(1): два указателя и перенос.

Может ли перенос когда-либо быть больше 1?

Нет. В столбце складываются две цифры, каждая не больше 9, и перенос не больше 1, поэтому сумма не превышает 19. Деление на 10 с округлением вниз даёт 0 или 1.

def addTwoNumbers(next1, values1, next2, values2):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

next1 = [2, -1, 1]
values1 = [8, 6, 1]
next2 = [2, -1, 1]
values2 = [7, 5, 2]

Ожидаемый вывод

[5, 4, 1, 1]