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

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,返回最小值。

总结一下整个执行流程:

  1. 过滤掉前面若干个空格(如果有的话)
  2. 判断正号、负号位,如果是负号则记录下状态,表示输入的是负数。
  3. 循环判断后面的字符串是否是09,如果是则累加这个值
  4. 当前的值跟最大、最小32位整数比较看是否溢出
  • 如果是正数,且大于214748364,直接返回最大值
  • 如果是正数,且等于214748364,再判断最后一位是否大于7
  • 如果是负数,且小于-214748364,直接返回最小值
  • 如果是负数,且等于-214748364,再判断最后一位是否大于8
  1. 循环结束后,根据负号的标志位返回对应的正数或负数

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

发表评论

电子邮件地址不会被公开。