7,8-整数反转,字符串转换整数(atoi)

7. 整数反转

法一：按位转换

  • 弹出 和 推入数字
    • 弹出：num = x%10; x/=10
    • 推入：result = result x 10 + num (这里有可能溢出)
  • 模式识别：整数运算注意溢出
    • 转换为 INT_MAX / INT_MIN的逆运算

判断某数乘十是否会溢出，就把该数 和 INT_MAX 除10 进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
		public int reverse(int x){
				int rev = 0;
      	while(x!=0){
          	if(rev < Integer.MIN_VALUE /10 || rev > Integer.MAX_VALUE/10){
              	return 0;
            }
          	int digit = x % 10;
          	x /= 10;
          	rev = rev * 10 + digit;
        }
      	return rev;
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
  	def reverse(self, x):
      	INT_MIN, INT_MAX = -2**31 , 2**31-1
        rev = 0
        while x!=0:
          	# INT_MIN也是一个负数，不能写成 rev < INT_MIN //10
            if rev < INT_MIN//10 +1 or rev > INT_MAX//10:
              	return 0
            digit =x %10
            # python3 的 取模运算在x为负时也会返回[0,9) 以内的数，因此需要进行特殊判断
            if x<0 and digit >0:
              	digit -= 10
            # 同理python3的整数除法在x为负数时会向下(更小的负数)取整，因此不能写成 x//=10
            x = (x - digit) // 10
            rev = rev * 10 + digit
     return rev

8. 字符串转换整数 (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
循环结束后，根据负号的标志位返回对应的正数或负数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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;
	}
}