题目的主要信息：

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

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

方法一：遍历法

具体做法：

用一个index全程记录字符串下标。按照题目要求的点，先排除前导空格，再检查符号，最后转换数字，遇到非数字即停止转换，直接输出前面部分，最后注意边界等情况。一个遍历即可解决。

class Solution {
public:
    int StrToInt(string s) {
        int n = s.length();
        // 去除前导空格
        int index = 0; //遍历字符串的下标
        while(index < n) {
            if (s[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;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串的长度，一次遍历
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外空间

方法二：状态机

具体做法：

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

直接根据状态图写出状态矩阵，再遍历一次字符串，依据状态机转换即可。

class Solution {
public:
    int StrToInt(string s) {
        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;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串的长度，一次遍历
• 空间复杂度：$O(1)O(1)$，矩阵空间属于常数空间