atoi(字符串转化成整型)问题

Atoi(String to Integer)

该问题在面试中比较常见，难度一般，主要在于细节上的考虑。闲来无事，周末又刷一下LeeCode。邂逅此题String to Integer，也是坑里游了一把，但也是收获颇丰。遂有此文。

套路.png

我最初的解法

class Solution {
    public int myAtoi(String str) {
        //1.非法输入
        if(str == null) return 0;
       //移除字符串中的多余空格
        str = str.trim();
        if(str.length() == 0) return 0;
        //转换的结果可能溢出(overflow),所以使用long型
        long result = 0;
        //2.考虑结果的正负号问题
        boolean neg = false;
        if(str.charAt(0) == '-'){
            neg = true;
            str = str.substring(1);//去除符号位
        }else if(str.charAt(0)=='+'){
            str = str.substring(1);//去除符号位
        }
        
        for(int i=0,len=str.length();i<len;i++){
            char c = str.charAt(i);
            if(c >= '0' && c <= '9'){
                result = result * 10 + (c - '0');
                System.out.println("result = "+ result);
            }else{
                break;//不是数字
            }
        }
        //添加符号
        result = neg ? -result :result;
        //判断是否溢出
        if(result > Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }else if(result < Integer.MIN_VALUE){
            return Integer.MIN_VALUE;
        }else{
            return (int)result;
        }
    }
}

这个解法是最先想到的，也非常直观，我在编辑器上也做了些测试，结果OK。于是窃喜之余，submit the code.但是很遗憾，出错了。

出错提示
一脸懵逼的我赶紧在编辑器上测试此Input,确实是我错了。Check the code 我还是感觉没有问题。但是根据错误提示，很明显出错在溢出处理。人家要最大，我却给了个最小的。明摆着败我人品嘛
虽然我坚信思路是正确的，但是问题摆在那里，我也只能硬着头皮看啦。这么大个数怎么可能比Integer.MIN_VALUE还小呢。最后发现运行到运行到最后，结果突然变成-9223372036854775808。

// 声明long型变量后面要加L(不推荐使用小写)
long value = 9223372036854775809L;//报错了 ，你敢信？
/**
*查看了Long型的MAX_VALUE才发现，最大值是
* @Native public static final long MAX_VALUE = 0x7fffffffffffffffL; 
* @Native public static final long MIN_VALUE = 0x8000000000000000L;
* 输出一下看：
* Long型最大值是：9223372036854775807L
* Long型最小值是：-9223372036854775808L
*/

咋就这么巧呢？
不知道的，你可以做个测试：

  // Integer
  System.out.println("Integer的最大值+1："+(Integer.MAX_VALUE+1));//-2147483648 即Integer最小值
  System.out.println("Integer的最小值-1："+(Integer.MIN_VALUE-1));//2147483647  即Integer最大值
  // Long
  System.out.println("Long的最大值+1："+(Long.MAX_VALUE+1));//-9223372036854775808L 即Long的最小值
  System.out.println("Long的最小值-1："+(Long.MIN_VALUE-1));//9223372036854775807L  即Long的最大值

显然，错误的原因是：该值居然也超过了Long型的最大值。

知道真相的我，大吃一斤
小样，还治不了你。于是我立刻将result 的类型改为 BigInteger。
具体代码：
import java.math.BigInteger;

class Solution {
public int myAtoi(String str) {
BigInteger ten = new BigInteger(Integer.toString(10));
BigInteger negOne = new BigInteger(Integer.toString(-1));

    //1.非法输入的讨论
    if(str == null || str.length() == 0) return 0;
    //2.转换的结果可能溢出(overflow)
    // long result = 0;
    BigInteger result = BigInteger.ZERO; //"9223372036854775809"

    //3.移除字符串中的多余空格
    str = str.trim();
    //4.考虑结果的正负号问题
    boolean neg = false;
    if(str.charAt(0) == '-'){
        neg = true;
        str = str.substring(1);//去除符号位
    }else if(str.charAt(0)=='+'){
        str = str.substring(1);//去除符号位
    }
    
    for(int i=0,len=str.length();i<len;i++){
        char c = str.charAt(i);
        if(c >= '0' && c <= '9'){
            // result = result * 10 + (c - '0');
                            result = result.multiply(ten).add(new BigInteger(Integer.toString((c-'0'))));// '0'的整形值是48
        }else{
            break;//不是数字
        }
    }
    //添加符号
    result = neg ? result.multiply(negOne):result;
    //判断是否溢出
     if (result.compareTo(new BigInteger(Integer.toString(Integer.MAX_VALUE)))==1) {
        return Integer.MAX_VALUE;
    } else if (result.compareTo(new BigInteger(Integer.toString(Integer.MIN_VALUE)))==-1) {
        return Integer.MIN_VALUE;
    } else {
        return result.intValue();
    }
    // if(result > Integer.MAX_VALUE){
    //     return Integer.MAX_VALUE;
    // }else if(result < Integer.MIN_VALUE){
    //     return Integer.MIN_VALUE;
    // }else{
    //     return (int)result;
    // }
}

}
问题解决了，但是感觉好low啊。本来解题成功是高兴的，but我就像个泄气的皮球。这绝对不是最优解，肯定有更好的办法来解决overflow问题。于是赶紧滚去参看大神的啦。

找答案.png

第二种解法：

class Solution {
    public int myAtoi(String str) {
        if(str == null) return 0;
        str = str.trim();
        if(str.length() == 0) return 0;
        int index = 0;
        int result = 0;
        boolean isNeg = false;
        int len = str.length();
        int maxDivTen = Integer.MAX_VALUE / 10;
        int digit = 0;
        char c = str.charAt(index);
        if(c == '-' || c == '+'){
            isNeg = c == '-'?true:false;
            index ++;
        }
        
        while(index < len){
            c = str.charAt(index);
            digit = c - '0';
            if(c < '0' || c > '9') break;
            // 重点就在于这里，对于overflow的处理
            if(result > maxDivTen || result == maxDivTen && Integer.MAX_VALUE % 10 < digit){
               return  result = isNeg?Integer.MIN_VALUE:Integer.MAX_VALUE;
            }
            result = result * 10 + digit;
            index ++;
        }
        
        return isNeg? -result :result;
    }
}

代码很简单，就做过多解释啦。其实此解法就是在处理overflow比较高明，在处理的过程中，一旦超过临界值，直接返回结果，无需往下执行。

---

分解整数

这个思维非常重要，再次强调一下：

An Integer 6789 can be formed in for steps.
Step1: 6
Step2: 610 + 7 = 60 + 7 = 67
Step3: 6710 + 8 = 670 + 8 = 678
Step4: 678*10 + 9 = 6780 + 9 = 6789

仔细揣摩一下，会有不同的发现。Good Luck !!!