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

JZ49 把字符串转换成整数

题意分析：

将给的合法字符串转化为整数

示例输入："+2147483647"
返回：2147483647

示例输入："1a33"

返回值：0。输入是不合法的，因此结果是0

题解一（枚举各种情况）：

在字符串的开头，可能有如下几种情况

空格打头：删除空格
符号打头：记录符号
数字打头：直接开始处理
非以上三种情况：return 0；

我们遍历字符串，然后将数字不断添加到结果中，添加语句为ret = ret*10+s[i]。

我们不知道到最后生成的数字有多大，因此我们使用long long存储ret。

int StrToInt(string str) {
    int sign=1;
    long long ret = 0;
    for(int i=0;i<str.size();i++){
        if(str[i]==' '){
            continue;
        }
        else if(str[i]=='-'){
            sign=-1;
        }
        else if(str[i]=='+'){
        }
        else if(str[i]>='0'&&str[i]<='9'){
            ret = ret*10+(str[i]-'0');
        }
        else{
            return 0;
        }
    }
    return sign * ret;
}

题解二：

题目少了一个重要的限制条件，只能存储32 位大小的有符号整数。我不知道题目都没要求这个条件，许多题解你分析个啥？？？

下面就如果有这一限制条件，我们的代码该怎么修改？

在语句ret = ret*10+s[i]中。我们的ret现在是int类型，其取值范围为[INT_MIN,INT_MAX]。在这条语句中，ret*10是可能溢出的。比如当ret=214748365，ret*10=2147483650，大于INT_MAX。我们不能将乘过后的值与INT_MAX比较，因为我们没有那么到空间存储ret*10=2147483650。但是我们可以反过来思考，当ret>214748364时，必然不可以进行乘10操作。这时候如果依然需要转换，直接返回INT_MAX即可。

同理当ret*10没有超出int范围，ret10+s[i]依然可能会超出int范围，我们只需要加一个判断即可，当ret\10=2147483640,s[i]>'7'即可判定它会溢出，返回INT_MAX即可。

对于负数溢出，将判断s[i]>'7'变为s[i]>8即可。

int StrToInt(string str) {
    int sign = 1;
    int ret = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == ' ') {
            continue;
        } else if (str[i] == '-') {
            sign = -1;
        } else if (str[i] == '+') {
        } else if (str[i] >= '0' && str[i] <= '9') {
            // 以下是增加的判断，以防溢出
            if (ret > 214748364) {
                return 0;
            }
            ret = ret * 10;
            if (sign == 1 && ret == 2147483640 && str[i] > '7') {
                return 0;
            } else if (sign == 0 && ret == 2147483640 && str[i] > '8') {
                return 0;
            }
            ret += (str[i] - '0');
        } else {
            return 0;
        }
    }
    return sign * ret;
}

时间复杂度 $O(N)$ ，N为字符长度。

空间复杂福： $O(1)$ ，没有使用额外的空间。