Разбор задачи LeetCode №8 String to Integer (atoi) на Java

Рисунок: задача LeetCode №8 String to Integer

Условие задачи

Реализуй функцию, которая преобразует строку в 32-битное знаковое целое число (аналог atoi).Правила:Пропускай пробелы в начале.
Потом может идти знак (+ или -).
Потом идут цифры — из них составляется число.
Как только встретится не-цифра — остановись.
Если результат больше 2³¹ - 1, верни 2147483647.
Если меньше -2³¹, верни -2147483648.
Если нет валидных цифр — верни 0.

Примеры:

• "42" → 42
• " -42" → -42
• "4193 with words" → 4193
• "words and 987" → 0
• "-91283472332" → -2147483648 (переполнение)

Объясняем, как пятилетнему

Представь, что ты — робот-считалка. Ты любишь числа, но не понимаешь слова.

Ты идёшь по дороге из букв и цифр:

1. Сначала ты видишь кучу пробелов — ты их игнорируешь, как будто их нет.
2. Потом видишь плюс или минус — ты запоминаешь знак, как флажок: "Буду складывать или вычитать?"
3. Потом идут цифры — ты берёшь их одну за другой и строишь из них число, как из кубиков.
4. Как только видишь букву, смайлик, звёздочку — ты останавливаешься. Дальше не идёшь.
5. Если число слишком большое, ты говоришь: "Я такое не могу хранить!" и возвращаешь самое большое число, которое помнишь.
6. Если слишком маленькое (очень отрицательное) — возвращаешь самое маленькое.
7. Если ты ничего не нашёл (только слова или пробелы), ты возвращаешь 0.

Ты — очень послушный робот, и делаешь точно по правилам.

Пошаговый алгоритм

1. Пропускаем пробелы в начале строки.
2. Смотрим на знак: если + или -, запоминаем знак, и переходим дальше.
3. Собираем цифры по одной, пока они идут.
4. Проверяем переполнение на каждом шаге.
5. Возвращаем результат с правильным знаком или границу, если переполнилось.

Решение на Java

Рисунок: первая часть листинга решения задачи

Рисунок: вторая часть листинга решения задачи

Рисунок: третья часть листинга решения задачи

Пример 1: " -42"

1. Пропускаем пробелы → доходим до -
2. Знак = -1
3. Читаем 4 → result = 0*10 + 4 = 4
4. Читаем 2 → result = 4*10 + 2 = 42
5. Конец строки → возвращаем 42 * (-1) = -42

Пример 2: "4193 with words"

1. Нет пробелов → сразу читаем + (по умолчанию)
2. Читаем цифры: 4, 1, 9, 3 → result = 4193
3. Видим пробел и слово with → останавливаемся
4. Возвращаем 4193

Ответ: 4193

Пример 4: "-91283472332"

1. Знак -
2. Начинаем собирать число: 9, 1, 2, ...
3. На каком-то шаге result * 10 + digit выходит за пределы int
4. Мы это предсказываем заранее:Если result > (MAX_VALUE - digit) / 10 → переполнение
   
5. Так как знак отрицательный → возвращаем Integer.MIN_VALUE = -2147483648

Ответ: -2147483648

Почему проверка переполнения такая хитрая?

Мы не можем использовать long, потому что задача говорит: "среда не поддерживает 64-битные числа".

Поэтому проверяем до того, как произойдёт переполнение:

if (result > (Integer.MAX_VALUE - digit) / 10) {

return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;

Объяснение:

• Мы хотим сделать: result = result * 10 + digit
• Чтобы это не переполнило MAX_VALUE, должно быть:result * 10 + digit <= MAX_VALUE
  
• Переносим: result * 10 <= MAX_VALUE - digit
• Делим: result <= (MAX_VALUE - digit) / 10

Если это не так, значит — будет переполнение.

Заключение

Задача String to Integer (atoi) — это не просто алгоритм, а симуляция настоящего парсера.
Она учит:

• Работать с граничными случаями
• Предсказывать переполнение
• Писать робастный код, который не сломается на "грязных" данных

Пример, рассмотренный в статье, можно найти по адресу:

https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task8_stringToIntegerAtoi/Solution.java