题解 | #把字符串转换成整数(atoi)#

把字符串转换成整数(atoi)

http://www.nowcoder.com/practice/d11471c3bf2d40f38b66bb12785df47f

题意整理

写一个函数StrToInt，实现把字符串转换成整数的功能。
不能直接使用库函数。
字符串可能以空格+正负号+字符串表达式（数字、字母、负号、空格）+空格的形式出现。

方法一（模拟）

1.解题思路

首先去掉首尾空格。
然后转化为字符数组，便于后续遍历。定义一个变量用于标记第一个位置是否为负号。
接着开始遍历字符数组，只要当前字符不在'0'-'9'范围内，直接终止循环。每次都将对应字符加在结果上，如果大于边界值，返回最大的Integer型整数或最小的Integer型整数。（这里对越界的处理看似没有考虑最小的Integer型整数，其实这种情况对应也会返回最小的Integer型整数，只是当成越界处理了）

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int StrToInt (String s) {
        //去掉首尾空格
        s=s.trim();
        //转化为字符数组
        char[] arr=s.toCharArray();
        //标记是否为负数
        boolean isNeg=false;
        //开始游标以及字符数组长度
        int start=1,n=arr.length;
        //特殊情况判断
        if(n==0) return 0;
        if(arr[0]=='-'){
            isNeg=true;
        }
        //如果没有出现正负号，从0位置开始遍历
        else if(arr[0]!='+'){
            start=0;
        }
        long res=0;
        //Integer型最大值
        int bound=Integer.MAX_VALUE;
        for(int i=start;i<n;i++){
            //如果不是'0'-'9'的字符，直接终止循环
            if(arr[i]<'0'||arr[i]>'9') break;
            //字符转化为对应数字并加在结果上
            res=res*10+arr[i]-'0';
            //如果越界，大于最大边界值，返回最大边界，小于最小边界值，返回最小边界
            if(res>bound){
                return isNeg?Integer.MIN_VALUE:Integer.MAX_VALUE;
            }           
        }
        return isNeg?(int)res*(-1):(int)res;
    }
}

3.复杂度分析

时间复杂度：需要遍历整个字符串，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。

方法二（边界值处理调整）

1.解题思路

思路和方法一差不多，只是优化了越界处理。不再需要定义结果变量为long类型，最后再强转。这里定义了最大整型的10分之一作为边界。然后在没有对结果做处理之前做一个判断。如果大于bound，显然已经越界了；如果等于bound，则要看当前字符的值在什么范围，如果大于等于'7'，加入到结果之后，一定会越界，否则，不会越界。对于最小的Integer型整数的处理，参考方法一，不用做另外的处理。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int StrToInt (String s) {
        //去掉首尾空格
        s=s.trim();
        //转化为字符数组
        char[] arr=s.toCharArray();
        //标记是否为负数
        boolean isNeg=false;
        //开始游标以及字符数组长度
        int start=1,n=arr.length;
        //特殊情况判断
        if(n==0) return 0;
        if(arr[0]=='-'){
            isNeg=true;
        }
        //如果没有出现正负号，从0位置开始遍历
        else if(arr[0]!='+'){
            start=0;
        }
        int res=0;
        //Integer型最大值的10分之一
        int bound=Integer.MAX_VALUE/10;
        for(int i=start;i<n;i++){
            //如果不是'0'-'9'的字符，直接终止循环
            if(arr[i]<'0'||arr[i]>'9') break;
            //如果越界，大于最大边界值，返回最大边界，小于最小边界值，返回最小边界
            if(res>bound||(res==bound&&arr[i]>'7')){
                return isNeg?Integer.MIN_VALUE:Integer.MAX_VALUE;
            }           
            //字符转化为对应数字并加在结果上
            res=res*10+arr[i]-'0';
        }
        return isNeg?res*(-1):res;
    }
}