Найдите допустимое целое число из заданной строки

Опубликовано: 20 Сентября, 2022

Дана строка str размера N , содержащая ' ' , '.' , '-' , '+' и ['0'-'9'] задача состоит в том, чтобы найти допустимое целое число из этой строки.
Целое число считается действительным, если оно соответствует следующим правилам:

  • Если str содержит начальные пробелы, игнорируйте их.
  • Первый допустимый символ должен быть "-", "+" или ['0'-'9'].
  • Если знак не указан, рассматривайте целое число как положительное
  • Если перед целым числом есть другие недопустимые символы, выведите 0.
  • Если после целого числа есть недопустимые символы, выведите целое число
  • Если число является десятичным числом, преобразовать его в целое число
  • Игнорировать любые начальные 0
  • Сделайте так, чтобы целое число находилось в диапазоне [-2^31, 2^31-1], а если нет, выведите соответствующий предел.
  • Считайте следующие символы, пока не будет достигнут следующий нецифровой символ или конец ввода. Остальная часть строки игнорируется.

Примеры:

Input: s = “28”
Output: 28
Explanation: As per the given rules 42 is a valid integer.

Input: s = ”   -2″
Output: -2
Explanation: Leading white spaces are ignored

Input: s = ”   -one6″
Output: 0
Explanation: Invalid character before the integer

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

Перемещайте строку символ за символом и сохраняйте флаги для первой найденной и отрицательной цифры:

  • Если цифра еще не найдена, и:
    • символ пробел, игнорировать
    • символ '-' и отрицательный флаг не установлен, установите отрицательное значение на -1
    • символ «+», а отрицательный флаг не установлен, установите отрицательный на 1
    • символ «-» или «+» и установлен отрицательный флаг, разрыв
    • символ - это символ или '.', вырваться
    • символ - это цифра, установите флаг в значение true и сохраните цифру в ответе
  • Если цифра найдена и флаг истинен:
    • символ - это цифра, сохраните цифру в ответе
    • Если предел достигнут, установите соответствующий боковой предел в качестве окончательного ответа
    • Если символ не является цифрой, вырваться.
  • Выведите окончательное значение ответа.

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ