题目的主要信息：

• 将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数
• 值为0或者字符串不是一个合法的数值则返回0
• 输入字符串包括数字字母符号,可以为空

方法一：遍历法

具体做法：

我们遍历字符串，用index记录全程的下标。首先要排除前导空格，然后检查符号，最后是转换数字，如果在转换数字过程中出现字符则认为这是不合法的，返回0。当然转换数字的时候还要注意判断int型边界的情况。

class Solution {
public:
    int StrToInt(string str) {
        int res = 0;
        int index = 0;
        int n = str.length();
        while(index < n){ //去掉前导空格，如果有
            if(str[index] == ' ')
                index++;
            break;
        }
        int sign = 1;
        //处理第一个符号是正负号的情况
        if(str[index] == '+')
            index++;
        else if(str[index] == '-'){
            index++;
            sign = -1;
        }
        if(index == n) //去掉符号就什么都没有了
            return 0;
        while(index < n){
            char c = str[index];
            if(c < '0' || c > '9')  //非法字符，输出0
                return 0;
            //处理越界
            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\left(n\right)O(n)$O(n)，$nn$n为字符串长度，一个遍历解决
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用

方法二：状态机

具体做法：

字符串无非就是这些类型：[ ' '（空格）, 0（前导或者数字中间的）, [1-9], 其它非法字符，'-/+' ]，我们可以将其映射成数字： [0,1,2,3,4]，一共有4种状态 0，1，2，3， 其中3退出状态机且返回0。状态机如下图：

class Solution {
public:
    int StrToInt(string 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 = str.length();
        int sign = 1;
        int state = 0; //状态从“ ”开始
        for(int i = 0; i < n; i++){
            char c = str[i];
            if(c == ' ')
                state = states[state][0]; //空格
            else if(c == '0')
                state = states[state][1]; //前导0或者中间的0
            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)
                return 0;
        }
 
        return (int)sign * res;
    }
};

复杂度分析：

• 时间复杂度：$O\left(n\right)O(n)$O(n)，遍历一次字符串
• 空间复杂度：$O\left(1\right)O(1)$O(1)，状态矩阵属于常数空间