Проблема. Реализовать функцию atoi, которая преобразует строку в целое число.

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

Вот случаи, связанные с этой проблемой:

1. Если в строке есть какие-либо пробельные символы, их следует удалить

2. Строка может содержать ровно один непробельный символ в начале, который является знаком «+» или «-».

3. Если перед цифрой стоят другие символы, результат равен 0.

4. Если после цифр есть какие-либо символы, они игнорируются

5. Если число больше 231–1 или меньше -231, вместо этого возвращается максимальное значение 231–1 или минимальное значение -231.

Прежде чем приступить к кодированию, давайте сделаем несколько быстрых примеров, чтобы получить представление о ожидаемом результате.

Ввод:"42"

Вывод:42

Это самый простой случай, с которым мы столкнемся. В этом случае мы можем просто напрямую конвертировать, и все готово.

Ввод:" -42"

Вывод:-42

В этом случае используется отрицательный знак, который мы сохраняем, поскольку это первый символ.

Ввод: «4–2»

Вывод:4

Помните, что все, начиная с первого символа текста и далее, игнорируется, поэтому все после «-» исключается, что дает нам только 4.

Ввод: «текст 4»

Вывод:0

Любой текст перед номером, который не является «+» или «-», приводит к сбою анализа.

Имея в виду эти примеры, давайте теперь запрограммируем решение.

Для начала мы собираемся удалить предоставленную строку, чтобы удалить все существующие пробелы. Отсюда мы можем перебрать строку, чтобы начать проверку допустимых чисел. Сначала проверяем первый символ, чтобы определить, не является ли он цифрой, а не «+» или «-». В этом случае мы устанавливаем для свойства valid значение false, поскольку мы знаем, что первый символ, который мы видим, является текстом, а не числовым знаком, что означает, что ввод недействителен. Если это не так, мы проверяем «-» или цифру. В любом из этих случаев мы просто добавляем результат.

Обратите внимание, что в первом наборе проверок мы игнорируем регистр «+». Это потому, что если мы видим «+», это допустимо, но нам не нужно никуда добавлять его, поэтому мы можем просто игнорировать его. Как только мы разобрались с первым символом, мы можем проанализировать остальные. Если мы встречаем нецифру, мы устанавливаем i равным длине строки. Это остановит итерацию, не устанавливая для параметра valid значение false, так как он может быть допустимым с текстом в середине, но не должен анализироваться дальше. Случай по умолчанию заключается в том, что мы видим целое число, которое мы можем просто добавить.

Отсюда нам просто нужно еще две проверки, и все готово.

Наши последние две проверки должны убедиться, что действительность все еще верна. Если это не так, мы устанавливаем выход в 0 и возвращаемся. Если это допустимо, мы проверяем, является ли результат слишком большим или слишком маленьким, и корректируем его по мере необходимости. После этого мы возвращаем результат, и все готово.

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