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

题解一：模拟
解题思路：模拟考虑各种特殊情况：
1、负号“-”与正号“+”只能出现在第一个i=0的位置；

2、不能出现除0~9与+、-之外的任何字符；

3、不能出现前置零；

4、最后结果判断是否越界(INT_MIN<=res<=INT_MAX)；
特判所有的特殊情况后，如示例将字符串转换成整数：

复杂度分析：
时间复杂度:O(n),遍历字符串
空间复杂度:O(1)

实现如下:

class Solution {
public:
    int StrToInt(string str) {
        int flag = 0;//标记数字正负
        long long res = 0;
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] == '-' || str[i] == '+') {//判断第一个
                if (i != 0) return 0;
                flag = str[i] == '-' ? 1 : 0;
            }
            else if (str[i] >= '0'&&str[i]<='9') {//将字符串转变成int类型
                if (str[i] == '0') {
                    if (res == 0)return 0;//前置零的情况特判；
                    else res = res * 10 + 0;
                }
                else {
                    res = res * 10 + str[i] - '0';
                }
            }
            else {
                return 0;
            }
        }
        //负数
        if(flag){
            //负数
            res=-res;
            if(res<INT_MIN)return 0;//小于int最小值
            return res;
        }
        //正数
        if(res>INT_MAX)return 0;//大于int最大值
        return res;
    }
};

题解二：递归
解题思路：同题解一；
注意事项：注意递归的结束条件;
复杂度分析:
时间复杂度:O(n),遍历整个字符串
空间复杂度:O(n),递归最大深度；

实现如下：

class Solution {
public:
    long long res=0,flag=0; 
    void f(string &str,int i){
        if(i<str.size()){
            if (str[i] == '-' || str[i] == '+') {//判断第一个
                    if (i != 0) {res=0; return ;}
                    flag = str[i] == '-' ? 1 : 0;
            }else if(str[i] >= '0'&&str[i]<='9'){
                if (str[i] == '0') {
                        if (res == 0){res=0; return ;}//前置零的情况特判；
                        else {
                            res = res * 10 + 0;
                        }
                    }
                    else {
                        res = res * 10 + str[i] - '0';//将当前值计算到最终结果上
                    }
            }else{
                res=0; 
                return ;
            }
            f(str,i+1);//递归下一层
        }
    }
    int StrToInt(string str) {
        f(str,0);
        //处理最后的结果
       if(flag){
            //负数
            res=-res;
            if(res<INT_MIN)return 0;//小于int最小值
            return res;
        }
        //正数
        if(res>INT_MAX)return 0;//大于int最大值
        return res;
    }
};