В этой статье блога мы рассмотрим различные подходы к решению проблемы LeetCode 66, известной как «Плюс один». Эта проблема заключается в увеличении числа, представленного в виде массива цифр, на единицу. Мы предоставим примеры кода для каждого метода и обсудим их плюсы и минусы. Давайте погрузимся!

Метод 1: простая манипуляция с массивом
Пример кода:

def plusOne(digits):
    n = len(digits)
    for i in range(n - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

Описание:
Этот метод начинается с самой правой цифры и проверяет, меньше ли она 9. Если да, он увеличивает цифру и возвращает обновленный массив. Если цифра равна 9, он устанавливает ее в 0 и переходит к следующей цифре. Если все цифры равны 9, в начале добавляется 1 и возвращается обновленный массив.

Метод 2: преобразование в целое число и обратно в массив
Пример кода:

def plusOne(digits):
    num = int(''.join(map(str, digits)))
    num += 1
    return list(map(int, str(num)))

Описание:
В этом методе мы преобразуем массив цифр в целое число, объединяя их в строку и преобразуя его с помощью функции int(). Затем мы увеличиваем целое число на единицу и преобразуем его обратно в массив, сопоставляя каждую цифру с целым числом с помощью функции map().

Метод 3. Математика – без преобразования
Пример кода:

def plusOne(digits):
    carry = 1
    for i in range(len(digits) - 1, -1, -1):
        digits[i] += carry
        if digits[i] < 10:
            carry = 0
            break
        digits[i] = 0
    if carry:
        digits.insert(0, carry)
    return digits

Описание:
Этот метод выполняет операцию сложения непосредственно в массиве без какого-либо преобразования. Он начинается с самой правой цифры, добавляет перенос (инициализируется как 1) и проверяет, меньше ли цифра 10. Если да, цикл разрывается. В противном случае он устанавливает цифру в 0 и переходит к следующей цифре. Наконец, если перенос еще есть, он вставляет его в начало массива.

Метод 4: рекурсивный подход
Пример кода:

def plusOne(digits):
    if not digits:
        return [1]
    if digits[-1] < 9:
        digits[-1] += 1
        return digits
    return plusOne(digits[:-1]) + [0]

Описание:
Этот метод использует рекурсию для решения проблемы. Он проверяет, пуст ли массив, и если да, возвращает [1]. Если последняя цифра меньше 9, она увеличивается и возвращает обновленный массив. В противном случае он рекурсивно вызывает функцию plusOne для массива, за исключением последней цифры, и добавляет к результату 0.

В этой статье мы рассмотрели четыре различных метода решения проблемы LeetCode 66 «Плюс один». Каждый метод обеспечивает уникальный подход к увеличению числа, представленного в виде массива цифр. В зависимости от конкретных требований и ограничений вы можете выбрать наиболее подходящий для вашей реализации метод. Не забудьте проанализировать временную и пространственную сложность каждого подхода, чтобы принять обоснованное решение. Приятного кодирования!