Plus One

Q: Какова временная сложность задачи Plus One?

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

ЛегкоМатематика и моделирование

+10

Неотрицательное целое число хранится в виде массива его десятичных цифр digits, начиная со старшей цифры: 472 — это [4, 7, 2]. Прибавьте к числу единицу и верните цифры результата в том же формате. Число может содержать до 100 цифр — намного больше, чем помещается в 64-битном целом числе.

Функция

plusOne(digits: integer-array) → integer-array

digitsinteger-array: цифры числа, начиная со старшей
Возвращаетinteger-array: цифры числа плюс один, начиная со старшей

Ограничения

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits не содержит ведущего нуля, за исключением самого числа 0, которое равно [0].

Примеры

Ввод: digits = [4, 3, 9]
Вывод: [4, 4, 0]
Пояснение: Число равно 439, а 439 + 1 = 440. Последняя цифра 9 превращается в 0 и передаёт перенос цифре 3, которая становится 4.

Ввод: digits = [0]
Вывод: [1]
Пояснение: Число 0 записывается как [0], а 0 + 1 = 1.

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

Как вместо этого вычесть единицу из числа, которое не меньше 1? Когда результат теряет первую цифру, как в [1, 0, 0]?

Решение

100-значное число переполняет любой 64-битный целочисленный тип, максимальное значение которого близко к 1.8 × 10^19, поэтому преобразовать число и сложить не получится. Складывай так же, как на бумаге: начиная с последней цифры и перенося разряд. Прибавление 1 меняет только конечные девятки: они становятся нулями, а также меняется цифра слева от них.

Сложение с переносом, цифра за цифрой

Идея

Начните с переноса 1 — единицы, которую вы прибавляете. Для каждой цифры справа сумма в столбце равна цифре плюс перенос: total % 10 добавляется в ответ, а total / 10 становится следующим переносом. Сумма не превышает 9 + 1 = 10, поэтому перенос равен 0 или 1. Перенос, оставшийся после первой цифры, становится новой ведущей цифрой, как в примере 999 + 1 = 1000.

Вы получаете ответ, начиная с последней цифры, поэтому собирайте его в таком порядке и разверните в конце. Это занимает время O(n) и требует нового массива размером до n + 1 цифр.

Алгоритм

Установи carry равным 1 и создай пустой список для ответа.
Для каждой цифры, начиная с последней и заканчивая первой, вычисли total = digit + carry.
Добавь total % 10 в ответ и установи carry равным total / 10, округлённому вниз.
После цикла, если carry равен 1, добавь его.
Разверни ответ и верни его.

def plusOne(digits):
    result = []  # the answer, last digit first
    carry = 1  # the one you are adding
    for i in range(len(digits) - 1, -1, -1):
        total = digits[i] + carry
        result.append(total % 10)
        carry = total // 10
    if carry > 0:
        result.append(carry)
    result.reverse()
    return result

Остановитесь на первой цифре меньше 9

Идея

Цифра меньше 9 поглощает перенос 1: она увеличивается на единицу, а все цифры слева от неё сохраняют свои значения. Перенос дальше передаёт только 9, превращаясь в 0. Поэтому можно остановиться на первой цифре меньше 9 и вернуть входной массив, изменённый на месте. Для [2, 9, 0, 9] последняя 9 становится 0, 0 становится 1, и ты возвращаешь [2, 9, 1, 0], не считывая первые две цифры.

Если ни одна цифра не меньше 9, число равно 10^n - 1, а ответ — это 1, за которой следуют n нулей. Только в этом случае нужен новый массив, поэтому в остальных случаях дополнительное пространство составляет O(1).

Алгоритм

Пройдите по индексам от последнего к первому.
Если цифра меньше 9, увеличьте её на единицу и верните массив.
В противном случае цифра равна 9: установите её равной 0 и переместитесь на одну позицию влево.
Если цикл завершится, значит, каждая цифра была равна 9: верните 1, за которой следуют n нулей.

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1  # no carry leaves this digit, so the rest stays as it is
            return digits
        digits[i] = 0  # 9 + 1 = 10: write 0 and carry one to the left
    # Every digit was 9: the answer is 1 followed by zeros.
    return [1] + digits

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

Преобразование массива в целое число и обратно. В 64-битном целом числе помещается не более 19 или 20 цифр, поэтому 100 цифр приводят к переполнению, а число с плавающей точкой теряет последние цифры ещё раньше.
Забыть про дополнительную цифру. [9, 9, 9] должно превратиться в [1, 0, 0, 0]; код, который переписывает только существующие разряды, возвращает [0, 0, 0].
Прибавление 1 к первой цифре. В массиве сначала идёт старший разряд, поэтому цифра единиц находится в последнем элементе.
Не возвращаться после того, как цифра меньше 9 поглотила перенос. Тогда цикл изменит цифры, которые должны остаться прежними: [1, 9, 3] должно превратиться в [1, 9, 4].
В Lua и R массивы начинаются с 1, поэтому последняя цифра находится по индексу n, а не n - 1.

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

Какова временная сложность задачи Plus One?

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

Почему бы не преобразовать цифры в целое число?

Число может состоять из 100 цифр, а 64-битное целое число ограничено примерно значением 1.8 × 10^19, то есть 20 цифрами. В Python и Ruby целые числа не ограничены по размеру, поэтому преобразование там работает, но этот код нельзя перенести на другие языки. Обработка цифр по одной никогда не приводит к переполнению.

Как сложить два числа, хранящиеся в виде массивов цифр?

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

def plusOne(digits):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

digits = [4, 3, 9]

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

[4, 4, 0]