Преобразование строки в целое число (atoi)

Средняя

medium , string

01 August 2024

Описание задачи #

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

Функция должна следовать следующим правилам при чтении строки:

Пропустить любые ведущие пробелы.
Проверить наличие знака (+ или -).
Читать следующие символы до тех пор, пока они составляют последовательность цифр.
Преобразовать эти цифры в целое число.
Если первая непустая последовательность символов не является допустимым целым числом, вернуть 0.
Если полученное значение превышает диапазон 32-битного знакового целого числа, вернуть INT_MAX (2³¹ - 1) или INT_MIN (-2³¹).

Ограничения #

Длина строки находится в диапазоне от 0 до 200
Строка s состоит из английских букв (как заглавных, так и строчных), цифр, знаков ' ' ( пробел), '+', '-' и '.'.

Примеры #

Входные данные: "42"

Ответ: 42

Преобразуем строку "42" в целое число 42.
Входные данные: " -42"

Ответ: -42

Пропускаем начальные пробелы и преобразуем строку "-42" в целое число -42.
Входные данные: "4193 with words"

Ответ: 4193

Прекращаем чтение после числовой последовательности, так как первый нечисловой символ - пробел.
Входные данные: "words and 987"

Ответ: 0

Первый непустой символ - буква, которая не является допустимым числом.
Входные данные: "-91283472332"

Ответ: -2147483648

Значение меньше нижнего предела 32-битного знакового целого числа, поэтому возвращаем INT_MIN (-2³¹).

Решение #

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

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

После этого нам нужно проверить присутствует ли в строке определение знака числа. Для этого заведем переменную sign.

Если встречаем в строке символ +, то устанавливаем значение sign равным 1.
Если встречаем в строке символ -, то устанавливаем значение sign равным -1.

Если в строке присутствовал знак числа, то еще необходимо увеличить index на единицу.

Теперь осталось преобразовать оставшиеся символы в число. Чтобы проверить, является ли символ в строке числом без приведения типов можно воспользоваться маленьким хаком и сравнивать его со строками.

Если char < "0" или char > "9", то символ не является числом. Как только мы встретили не числовой символ в строке, то дальнейший разбор необходимо прекратить.
Если смвол является числом, то его необходимо добавить к результирующему числу. Для этого надо воспользоваться следующей формулой res = res * 10 + char - '0'. Это позволяет прибавить цифру справа к существующему числу.

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

Если превышено максимальное значение, то в качестве ответа надо вернуть максимальное.
Если превышено минимальное значение, то в качестве ответа надо вернуть минимальное.

В заключение в ответе нужно вернуть ответ res умноженный на знак sign.

Реализация #

package atoi

const (
	maxInt32 = 1<<31 - 1
	minInt32 = -1 << 31
)

func myAtoi(s string) int {
	var (
		res   = 0
		sign  = 1
		index = 0
	)

	runes := []rune(s)

	for index < len(s) && runes[index] == ' ' {
		index++
	}

	if index < len(runes) && runes[index] == '-' {
		sign = -1
		index++
	} else if index < len(runes) && runes[index] == '+' {
		index++
	}

	for i := index; i < len(runes); i++ {
		char := runes[i]

		if char < '0' || char > '9' {
			break
		}

		res = res*10 + int(char-'0')
		if sign*res > maxInt32 {
			return maxInt32
		}
		if sign*res < minInt32 {
			return minInt32
		}
	}

	return sign * res
}

export function myAtoi(s: string): number {
    const maxInt32 = 2**31 - 1;
    const minInt32 = 2**31 * -1;

    let res = 0;
    let sign = 1;
    let index = 0;

    while (index < s.length && s[index] === ' ') {
        index++;
    }

    if (index < s.length && s[index] === '-') {
        sign = -1;
        index++;
    } else if (index < s.length && s[index] === '+') {
        index++;
    }

    for (let i = index; i < s.length; i++) {
        const char = s[i];

        if (char < '0' || char > '9') {
            break;
        }

        res = res * 10 + (char.charCodeAt(0) - '0'.charCodeAt(0));
        if (sign * res > maxInt32) {
            return maxInt32;
        }
        if (sign * res < minInt32) {
            return minInt32;
        }
    }

    if (res === 0) {
        // Обрабатываем случай, когда res = 0 и sign = -1. В таком случае JS вернет в качестве ответа «-0»
        return res
    }

    return sign * res;
}

Оценка сложности #

n - длина строки

По времени

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

По памяти

Сложность по памяти константная — O(1), так как мы не создаем дополнительных переменных.

Оригинал задачи на Leetcode

Algorithmics