Plus One

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

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

Q: Когда результат содержит больше цифр, чем входные данные?

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

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

+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.

+13 скрытых тестов при отправке

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

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

Решение

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

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

Идея

Запишите число и прибавьте 1 под его последней цифрой, как в школе. Начните с переноса 1 — единицы, которую вы прибавляете. Для каждой цифры справа налево сумма в столбце равна этой цифре плюс перенос. Последняя цифра суммы, total % 10, идёт в ответ, а цифра десятков, total / 10, становится переносом для следующего столбца.

При переносе 1 сумма в столбце не превышает 9 + 1 = 10, поэтому перенос всегда равен 0 или 1. Если после первой цифры перенос ещё остался, в ответе появляется новая ведущая цифра: для 999 + 1 требуется четвёртая позиция для 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

Идея

Посмотри, что происходит с переносом, когда ты прибавляешь ровно 1. Цифра меньше 9 поглощает его: 3 становится 4, перенос становится равен 0, а все цифры левее сохраняют свои значения. Только 9 передаёт перенос дальше, превращаясь в 0. Значит, прибавить 1 — это заменить конечные девятки на 0, а затем прибавить 1 к цифре непосредственно перед ними.

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

Если цикл так и не найдёт цифру меньше 9, значит, каждая цифра была равна 9 и теперь стала 0. Число было равно 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

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

Ловушки — это переполнение целого числа и случай, когда все цифры равны 9.

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

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

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

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

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

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

Когда результат содержит больше цифр, чем входные данные?

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

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

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

digits = [4, 3, 9]

Ожидается

[4, 4, 0]