题解 | #将字符串转化为整数#

思路：

题目的主要信息：
写一个atoi函数，将字符串转变成int型数字，输入没有任何限制，需要注意以下几点：

• 前导0与前导空格要全部去掉
• 第一个符号是正负号的情况
• 输入了非数字要直接跳出
• 输入达到了int型表示边界
• 空串返回0

方法一：遍历法
具体做法：
用一个index全程记录字符串下标。按照上面提到的点，先排除前导空格，再检查符号，最后转换数字，注意边界等情况。一个遍历可以解决。

class Solution {
public:
    int atoi(const char *str) {
        string s = str;  //转换为string类型
        int n = s.length();
        // 去除前导空格
        int index = 0; //遍历字符串的下标
        while(index < n) {
            if (str[index] != ' ')
                break;
            index++;
        }
        if(index == n) //除了0就没有了
            return 0;
        int sign = 1;
        // 处理第 1 个非空字符为正负符号
        if(s[index] == '+')
            index++;
        else if(s[index] == '-') {
            sign = -1;
            index++;
        }
        int res = 0;
        while(index < n){
            char c = s[index];
            if(c < '0' || c > '9') //非数字跳出
                break;
            //int型最大最小
            if(res > INT_MAX / 10 || (res == INT_MAX / 10 && (c - '0') > INT_MAX % 10))
                return INT_MAX;
            if(res < INT_MIN / 10 || (res == INT_MIN / 10 && (c- '0') > -(INT_MIN % 10)))
                return INT_MIN;
            res = res * 10 + sign * (c - '0');
            index++;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，都是单层遍历
• 空间复杂度：，无额外空间使用

方法二：状态机
字符串无非就是这些类型：[ ' ', 0, [1-9], 其它非法字符，'-/+' ]，我们可以将其映射成数字： [0,1,2,3,4]，一共有4种状态 0，1，2，3， 其中3退出状态机。状态机如下：

具体做法：
根据状态图写出状态矩阵，再遍历一次字符串，依据状态机转换即可。

class Solution {
public:
    int atoi(const char *str) {
        string s = str; //转换为string类型
        vector<vector<int> > states = {
            {0,1,2,3,1},
            {3,1,2,3,3},
            {3,2,2,3,3},
        };  //状态转移矩阵
        long res = 0;
        long top = INT_MAX;  //与int边界比较
        long bottom = INT_MIN;
        int n = s.length();
        int sign = 1;
        int state = 0; //状态从“ ”开始
        for(int i = 0; i < n; i++){
            char c = s[i];
            if(c == ' ')
                state = states[state][0];
            else if(c == '0')
                state = states[state][1];
            else if(c >= '1' && c <= '9')
                state = states[state][2];
            else if(c == '-' || c == '+'){
                state = states[state][4];
                if(state == 1) 
                    sign = (c == '-') ? -1 : 1;
                else 
                    break;
            }else 
                state = states[state][3];

            if(state == 2) {
                res = res * 10 + int(c - '0');
                res = (sign == 1) ? min(res, top) : min(res, -bottom); //越界处理
            }
            if(state == 3) 
                break;
        }

        return (int)sign * res;
    }
};

复杂度分析：

• 时间复杂度：，都是单层遍历
• 空间复杂度：，状态矩阵常数空间