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 次阅读