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

题目描述
实现函数 atoi 。函数的功能为将字符串转化为整数
提示：仔细思考所有可能的输入情况。这个问题没有给出输入的限制，你需要自己考虑所有可能的情况。

方法一：遍历的方法

求解思路
对于本题目所给出的条件，由于对输入没有任何限制，因此参考部分作者的思路，写出如下需要注意的几点。
1、前缀0和空格要全部去掉
2、判断第一个符号为正号or负号的情况
3、输入非数字的处理
4、输入的数字超过了int类型的范围
5、空串的情况
然后我们根据上述情况，用index记录字符串的下表，按照上述的情况进行逐个字符的判断，然后求得结果。

图片说明

解题代码

class Solution {
public:
    int atoi(const char *str) {
        string mys = str; // 转换为string类型
        int n = mys.length();
        int index = 0; //遍历字符串的下标
        while(index < n) 
        {
            if (str[index] != ' ')
                break;
            index++;
        }
        if(index == n) // 考虑特殊情况，返回0
            return 0;
        int sign = 1;
        // 处理第 1 个非空字符为正负符号
        if(mys[index] == '+')
            index++;
        else if(mys[index] == '-') 
        {
            sign = -1;
            index++;
        }
        int myres = 0;
        while(index < n)
        {
            char c = mys[index];
            if(c < '0' || c > '9') //非数字跳出
                break;
            //int型最大最小
            if(myres > INT_MAX / 10 || (myres == INT_MAX / 10 && (c - '0') > INT_MAX % 10))
                return INT_MAX;
            if(myres < INT_MIN / 10 || (myres == INT_MIN / 10 && (c- '0') > -(INT_MIN % 10)))
                return INT_MIN;
            myres = myres * 10 + sign * (c - '0');
            index++;
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：状态机的思想求解

求解思路
对于本题目的求解，我们可以采用状态机的思想进行求解。对于字符串，我们将空格映射成数字0，数字0映射为数字1，数字1-9映射成数字2，其他非法字符映射成数字3，正负号映射成数字4。并且根据他们之间的关系，我们有如下状态机的关系：

图片说明

解题代码

class Solution {
public:
    int atoi(const char *str) {
        string s = str; // 转换为string类型
        vector<vector<int> > sta = 
        {
            {0,1,2,3,1},
            {3,1,2,3,3},
            {3,2,2,3,3},
        }; // 状态转移矩阵
        long myres = 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 = sta[state][0]; // 映射成数字0
            else if(c == '0')
                state = sta[state][1]; // 映射成数字1
            else if(c >= '1' && c <= '9')
                state = sta[state][2]; // 映射成数字2
            else if(c == '-' || c == '+'){
                state = sta[state][4]; // 映射成数字4
                if(state == 1) 
                    sign = (c == '-') ? -1 : 1;
                else 
                    break;
            }else 
                state = sta[state][3]; // 映射成数字3
            if(state == 2) 
            {
                myres = myres * 10 + int(c - '0');
                myres = (sign == 1) ? min(myres, top) : min(myres, -bottom); // 越界处理
            }
            if(state == 3) 
                break;
        }
        return (int)sign * myres; // 返回结果即可
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$