8. 字符串转换整数 (atoi)

🟠   🔖  字符串  🔗 力扣 LeetCode

题目

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1.
6. Return the integer as the final result.

Note:

• Only the space character ' ' is considered a whitespace character.
• Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

Input: s = "42"

Output: 42

Explanation: The underlined characters are what is read in, the caret is the current reader position.

Step 1: "42" (no characters read because there is no leading whitespace)

Step 2: "42" (no characters read because there is neither a '-' nor '+')

Step 3: " 42 " ("42" is read in)

The parsed integer is 42.

Since 42 is in the range [-2^31, 2^31 - 1], the final result is 42.

Example 2:

Input: s = " -42"

Output: -42

Explanation:

Step 1: " -42" (leading whitespace is read and ignored)

Step 2: " - 42" ('-' is read, so the result should be negative)

Step 3: " - 42 " ("42" is read in)

The parsed integer is -42.

Since -42 is in the range [-2^31, 2^31 - 1], the final result is -42.

Example 3:

Input: s = "4193 with words"

Output: 4193

Explanation:

Step 1: "4193 with words" (no characters read because there is no leading whitespace)

Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')

Step 3: " 4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)

The parsed integer is 4193.

Since 4193 is in the range [-2^31, 2^31 - 1], the final result is 4193.

Constraints:

• 0 <= s.length <= 200
• s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

题目大意

请你来实现一个  myAtoi(string s)  函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数  myAtoi(string s) 的算法如下：

• 读入字符串并丢弃无用的前导空格
• 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
• 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
• 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
• 如果整数数超过 32 位有符号整数范围 [−2^31,  2^31 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被固定为 −2^31 ，大于 2^31 − 1 的整数应该被固定为 2^31 − 1 。
• 返回整数作为最终结果。

注意：

• 本题中的空白字符只包括空格字符 ' ' 。
• 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

解题思路

题目要求实现类似 C++ 中 atoi 函数的功能，这个函数功能是将字符串类型的数字转成 int 类型数字。

1. 先去除字符串中的前导空格，并判断记录数字的符号 sign；
2. 遍历字符串，如果 s[i] 是整型，则将其转换成数字类型存入 res；
3. 如果遇到非整型，则立刻结束遍历；
4. 将数字乘以 sign；
5. 判断是否超过 int 类型的上限 [-2^31, 2^31 - 1]，如果超过上限，需要输出边界，即 -2^31，或者 2^31 - 1。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度；
  • 对输入字符串进行 trim() 操作，去除字符串开头和结尾的空格，此操作的时间复杂度为 O(n)；
  • 遍历字符串，在最坏的情况下，可能需要遍历整个字符串，时间复杂度为 O(n)；
• 空间复杂度：O(1)，只使用了几个变量（如 i, res, 和 sign），没有使用额外的数据结构。

代码

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function (s) {
	s = s.trim();
	if (s.length == 0) return 0;

	let i = 0;
	let res = 0;
	let sign = 1;

	if (s[i] === '-') {
		i++;
		sign = -1;
	} else if (s[i] === '+') {
		i++;
	}

	while (i < s.length && !isNaN(parseInt(s[i]))) {
		res = 10 * res + parseInt(s[i]);
		i++;
	}

	res *= sign;
	res = Math.max(Math.min(2 ** 31 - 1, res), -(2 ** 31));
	return res;
};

相关题目

题号	标题	题解	标签	难度
7	整数反转	[✓]	数学
65	有效数字		字符串
2042	检查句子中的数字是否递增		字符串