LEETCODE 8. 字符串转换整数 (atoi)
题目描述
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储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)。
题目地址:
https://leetcode-cn.com/problems/string-to-integer-atoi/
题解
这道题的难点在于要考虑到各种边界问题，一不留神少了一步判断可能执行就报错了。
根据题目描述，可能会出现各种输入条件，比如：
-
" 123" -
" -345 " -
" -+7890" -
"11223344556677889900" -
" -112233.44.55aabb" -
等等…
我们总结一下，字符串可能包含下面三种类型:
紫色的第一部分是空格，在转换的时候需要过滤掉
黄色的部分是正负号，如果是正号则忽略，是负号则需要记录这个正负号状态
蓝色是第三部分，这部分字符串中会包含任意字符，但我们只需要"0"到"9"这几个字符
蓝色部分可能包含如下内容:
此外，对于11223344556677889900这样的字符串，明显是超长了，所以当字符串大于最大的32位整数，或者小于最小的32位整数，后面就不用判断了。
题目要求是只能存储32位大小的有符号整数，所以不能用long做存储，而且需要提前判断整数的大小。
上图绿色的是最大的32位整数，三个蓝色的数组代表三种不同的输入。
如果是第一种2147483650，这个值本身就比最大32位整数要大了，存到int里面就溢出了，所以提前一位判断，也就是到黄色格子那一位的时候就要判断了。第一种情况当前的值大于214748364直接返回最大值即可。
对于第二种、第三种情况，如果当前的值等于214748364，即前面若干位都一样，再单独判断最后一位，也就是橙色格子那一位。如果最后一位大于等于7，同样也是直接返回最大值。
对于负数也是类似的判断方式:
如果当前值小于-214748364，直接返回最小值即可。
如果当前值等于-214748364，再判断最后一位，如果大于等于8，返回最小值。
总结一下整个执行流程:
-
过滤掉前面若干个空格(如果有的话) -
判断正号、负号位，如果是负号则记录下状态，表示输入的是负数。 -
循环判断后面的字符串是否是 0到9，如果是则累加这个值 -
当前的值跟最大、最小32位整数比较看是否溢出
-
如果是正数，且大于 214748364，直接返回最大值 -
如果是正数，且等于 214748364，再判断最后一位是否大于7 -
如果是负数，且小于 -214748364，直接返回最小值 -
如果是负数，且等于 -214748364，再判断最后一位是否大于8
-
循环结束后，根据负号的标志位返回对应的正数或负数
java代码:
class Solution {
public int myAtoi(String str) {
if(str==null) {
return 0;
}
int n = str.length();
int i = 0;
int res = 0;
boolean is_negative = false;
//第一步，跳过前面若干个空格
while(i<n && str.charAt(i)==' ') {
++i;
}
//如果字符串全是空格直接返回
if(i==n) {
return 0;
}
//第二步，判断正负号
if(str.charAt(i)=='-') {
is_negative = true;
}
//如果是正负号，还需要将指针i，跳过一位
if(str.charAt(i)=='-' || str.charAt(i)=='+') {
++i;
}
//第三步，循环判断字符是否在 0~9之间
while(i<n && str.charAt(i)>='0' && str.charAt(i)<='9') {
//'0'的ASCII码是48，'1'的是49，这么一减就从就可以得到真正的整数值
int tmp = str.charAt(i)-48;
//判断是否大于 最大32位整数
if(!is_negative &&(res>214748364 ||(res==214748364 && tmp>=7))) {
return 2147483647;
}
//判断是否小于 最小32位整数
if(is_negative &&(-res<-214748364 || (-res==-214748364 && tmp>=8))) {
return -2147483648;
}
res = res*10 + tmp;
++i;
}
//如果有负号标记则返回负数
if(is_negative) {
return -res;
}
return res;
}
}
python代码:
class Solution(object):
def myAtoi(self, str):
if not str:
return 0
n = len(str)
res = 0
i = 0
# 第一步，跳过前面若干个空格
while i<n and str[i]==' ':
i += 1
# 如果字符串全是空格直接返回
if i==n:
return 0
# 第二步，判断正负号
is_negative = True if str[i]=='-' else False
# 如果是正负号，还需要将指针i，跳过一位
if str[i] in ('-','+'):
i += 1
# 第三步，循环判断字符是否在 0~9之间
while i<n and str[i]>='0' and str[i]<='9':
# '0'的ASCII码是48，'1'的是49，这么一减就从就可以得到真正的整数值
tmp = ord(str[i])-ord('0')
# 判断是否大于 最大32位整数
if not is_negative and (res>214748364 or (res==214748364 and tmp>=7)):
return 2147483647
# 判断是否小于 最小32位整数
if is_negative and (-res<-214748364 or (-res==-214748364 and tmp>=8)):
return -2147483648
res = res*10 + tmp
i += 1
# 如果有负号标记则返回负数
return -res if is_negative else res
(全文完)
5 次阅读