Пример решения задачи #8. Python LeetCode, String to Integer (atoi)

Вариант решения задачи на Python с LeetCode

Категория: Алгоритмы.
Название задачи: String to Integer (atoi).
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Реализуйте функцию myAtoi(string s), которая преобразует строку в 32-битное целое число со знаком.

Алгоритм для myAtoi(string s) выглядит следующим образом:

1. Пробелы: Игнорируйте любые начальные пробелы (" ").
2. Знак числа: Определите знак числа, проверив, является ли следующий символ '-' или '+'. Если ни один из символов не присутствует, предполагается положительное число.
3. Преобразование: Считайте число, пропуская ведущие нули, пока не встретится нецифровой символ или не будет достигнут конец строки. Если цифры не были прочитаны, результат равен 0.
4. Округление: Если число выходит за пределы диапазона 32-битного целого числа со знаком [-2^31, 2^31 - 1], округлите его до ближайшей границы диапазона:
- Числа меньше -2^31 округляются до -2^31.
- Числа больше 2^31 - 1 округляются до 2^31 - 1.
5. Возвращайте полученное целое число как окончательный результат.

Решение:

Python

class Solution(object):
    def myAtoi(self, s):
        """
        :type s: str
        :rtype: int
        """
        # Удаляем начальные пробелы
        i = 0
        while i < len(s) and s[i] == ' ':
            i += 1
        
        # Определяем знак числа
        sign = 1  # По умолчанию положительное число
        if i < len(s) and (s[i] == '+' or s[i] == '-'):
            sign = -1 if s[i] == '-' else 1
            i += 1
        
        # Читаем цифры и формируем число
        result = 0
        while i < len(s) and s[i].isdigit():
            result = result * 10 + int(s[i])  # Добавляем очередную цифру к результату
            i += 1
        
        # Применяем знак к результату
        result *= sign
        
        # Проверяем выход за границы 32-битного целого числа
        INT_MIN, INT_MAX = -2**31, 2**31 - 1
        if result < INT_MIN:
            return INT_MIN
        if result > INT_MAX:
            return INT_MAX
        
        # Возвращаем результат
        return result

Объяснение кода

Удаление начальных пробелов:
Мы используем цикл while, чтобы пропустить все пробельные символы в начале строки. Это соответствует первому шагу алгоритма.

Определение знака числа:
Если после пробелов встречается символ '+' или '-', мы определяем знак числа. Если символ '-', то знак становится отрицательным (sign = -1), иначе остаётся положительным (sign = 1).

Чтение цифр:
Мы читаем последовательность цифр, начиная с текущей позиции. Для каждой цифры обновляем значение переменной result, добавляя её к текущему числу. Это делается путём умножения текущего значения result на 10 и прибавления новой цифры.

Применение знака:
После завершения чтения цифр мы умножаем результат на sign, чтобы применить знак к числу.

Проверка на переполнение:
Мы проверяем, попадает ли результат в диапазон 32-битных целых чисел ([-2^31, 2^31 - 1]). Если число выходит за пределы этого диапазона, мы возвращаем ближайшее допустимое значение (INT_MIN или INT_MAX).

Возврат результата:
Если число находится в допустимом диапазоне, мы возвращаем его как результат.

Пример работы:
Input: s = "42"
Output: 42

Источник решения: hdhai.com