本文我们来看看LeetCode 第8题. 字符串转换整数 (atoi) 的解析过程。
文章目录
一、引言
今天我们要聊的是LeetCode的第8题——字符串转换整数，也就是俗称的“atoi”。听到这个名字，你是不是想起了大学C语言课上那个让人头疼的atoi函数？对，你没听错，这个题目就是让你自己实现那个C标准库的atoi函数。
题目描述
请你来实现一个
myAtoi(string s)函数，使其能将字符串转换成一个32位有符号整数（类似C/C++中的atoi函数）。函数
myAtoi(string s)的算法如下：
- 读入字符串并丢弃无用的前导空格。
- 检查下一个字符（假设还未到字符串的末尾）。如果是正负号，则读入该符号；否则，假定结果为正。
- 读入下一个字符，直到到达下一个非数字字符或到达输入的末尾。字符串的其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数。如果没有读入数字，则整数为
0。必要时更改符号（从步骤2开始）。- 如果整数超出32位有符号整数的范围，需要截断这个整数，使其保持在这个范围内。
- 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围是 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。
示例
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面的所有数字组合在一起，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−2^31) 。
好了，以上就是题目描述。接下来，让我们一起探讨如何优雅地解决这个问题。
二、解题思路
1. 丢弃无用的前导空格
就像清晨起床前要先挠挠头，伸个懒腰一样，我们需要先过滤掉字符串前面的空格，让后面的字符显露出来。
2. 处理正负号
接下来，我们要看看第一个显露出来的字符是啥。如果是正号 + 或负号 -，我们就记住它，这关系到后面结果的符号。如果都不是，那就默认是正数。
3. 读入数字
然后，就进入疯狂扫数字的阶段了。只要是数字，我们就一口气读下去，直到遇到非数字字符或者字符串结束。
4. 处理整数溢出
我们知道，32位有符号整数的范围是[-2147483648, 2147483647]，所以我们还需要处理溢出的问题。如果转换后的数字超出了这个范围，就得按照题目要求，返回最大或最小值。
5. 组合起来
最后，把上述步骤组合起来，就得到了完整的atoi函数实现。
思路流程图
三、Java代码实现
下面是完整的Java代码实现：
public class Solution {
public int myAtoi(String s) {
int index = 0, sign = 1, total = 0;
// 1. 移除字符串前导空格
while(index < s.length() && s.charAt(index) == ' ')
index++;
// 2. 处理符号
if(index < s.length() && (s.charAt(index) == '+' || s.charAt(index) == '-')){
sign = s.charAt(index) == '+' ? 1 : -1;
index++;
}
// 3. 转换数字并避免溢出
while(index < s.length()){
int digit = s.charAt(index) - '0';
if(digit < 0 || digit > 9) break;
// 检查溢出
if(Integer.MAX_VALUE / 10 < total || Integer.MAX_VALUE / 10 == total && Integer.MAX_VALUE % 10 < digit)
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
total = 10 * total + digit;
index++;
}
return total * sign;
}
}
代码解析
让我们一步步地解析上述代码，以便更好地理解实现细节。
1. 移除前导空格
// 1. 移除字符串前导空格
while(index < s.length() && s.charAt(index) == ' ')
index++;
这一段代码的目的是跳过字符串开头的空格。while 循环会一直运行，直到 index 到达字符串末尾或者遇到一个非空格字符。
2. 处理正负号
// 2. 处理符号
if(index < s.length() && (s.charAt(index) == '+' || s.charAt(index) == '-')){
sign = s.charAt(index) == '+' ? 1 : -1;
index++;
}
接下来，我们检查当前字符是否是 + 或 - 号。如果是，我们将 sign 变量设置为 1 或 -1 以表示正负号，同时将 index 前移一位，准备处理后续的数字部分。
3. 转换数字并避免溢出
// 3. 转换数字并避免溢出
while(index < s.length()){
int digit = s.charAt(index) - '0';
if(digit < 0 || digit > 9) break;
// 检查溢出
if(Integer.MAX_VALUE / 10 < total || Integer.MAX_VALUE / 10 == total && Integer.MAX_VALUE % 10 < digit)
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
total = 10 * total + digit;
index++;
}
return total * sign;
这个 while 循环的任务是将字符串中的数字字符逐个转换为整数。以下是该段代码的详细解析：
-
int digit = s.charAt(index) - '0';：将字符转换为对应的数字。这里通过减去字符'0'的ASCII值来实现。 -
if(digit < 0 || digit > 9) break;：如果当前字符不是数字（即不在0-9范围内），跳出循环。 -
溢出检查：
if(Integer.MAX_VALUE / 10 < total || Integer.MAX_VALUE / 10 == total && Integer.MAX_VALUE % 10 < digit) return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;这里我们需要确保在乘以
10并加上当前数字digit时不会导致溢出。如果total超过了Integer.MAX_VALUE / 10，那么再加上一个数字肯定会溢出。同理，如果total恰好等于Integer.MAX_VALUE / 10，那么只要digit超过7（因为Integer.MAX_VALUE的个位是7），就会溢出。 -
total = 10 * total + digit;：将当前数字加入到total中。 -
index++;：移动到下一个字符。
通过上述步骤，我们成功地将字符串转换为整数，并妥善处理了各种特殊情况，如前导空格、正负号和溢出等问题。
四、举几个栗子
栗子一：简单的正数
输入: "42"
- 丢弃前导空格：无
- 处理正负号：无
- 读入数字：42
- 处理溢出：无
- 返回结果：42
栗子二：带负号的数
输入: " -42"
- 丢弃前导空格：
"-42" - 处理正负号：负号，记为
sign = -1 - 读入数字：42
- 处理溢出：无
- 返回结果：
-42
栗子三：数字加文字
输入: "4193 with words"
- 丢弃前导空格：
"4193 with words" - 处理正负号：无
- 读入数字：4193
- 处理溢出：无
- 返回结果：4193
栗子四：文字加数字
输入: "words and 987"
- 丢弃前导空格：
"words and 987" - 处理正负号：无
- 读入数字：无
- 处理溢出：无
- 返回结果：0
栗子五：溢出数值
输入: "-91283472332"
- 丢弃前导空格：
"-91283472332" - 处理正负号：负号，记为
sign = -1 - 读入数字：91283472332
- 处理溢出：返回最小值
-2147483648 - 返回结果：
-2147483648
五、总结
通过这个题目，我们不仅学会了如何处理字符串到整数的转换问题，还练习了如何优雅地处理各种边界情况和特殊输入。就像生活中处理各种杂七杂八的问题一样，我们需要耐心、细心和周到的考虑。希望你通过这篇博客，不仅解决了这个LeetCode题目，还能在以后遇到类似问题时，轻松愉快地处理它们。
如果本文对您有所帮助的话，请收藏文章、关注作者、订阅专栏，感激不尽。
标签：index,digit,数字,VALUE,atoi,字符串,Integer,total,LeetCode From： https://blog.csdn.net/wjm1991/article/details/139307832