LeetCode 8. String to Integer (atoi)

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 8. String to Integer (atoi) 原题链接中等

作者：

yxc , 2018-04-13 02:19:25 , 所有人可见 , 阅读 5153

16

4

题目描述

实现 atoi 函数，将以字符串(string)形式表示的整数，转换成整型(int)。
aoti 函数需要满足的条件：

忽略所有行首空格，找到第一个非空格字符，可以是 ‘$+/-$’ 表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数；
整数后可能有任意非数字字符，请将其忽略；
从前往后遍历时，如果第一段连续数字为空，则返回0；
如果整数大于INT_MAX，请返回int_MAX；如果整数小于INT_MIN，请返回INT_MIN；

算法

(模拟) $O(n)$

这道题的难点在于边界情况非常多，需要仔细考虑。
做这道题目时，推荐先写一个傻瓜版，然后提交，再根据Wrong Case去逐步添加针对各种情况的处理。

时间复杂度分析：假设字符串长度是 $n$，每个字符最多遍历一次，所以总时间复杂度是 $O(n)$.

C++ 代码

class Solution {
public:
    int myAtoi(string str) {
        int res = 0;
        int k = 0;
        while (k < str.size() && str[k] == ' ') k ++ ;
        if (k == str.size()) return 0;

        int minus = 1;
        if (str[k] == '-') minus = -1, k ++ ;
        if (str[k] == '+')
            if (minus == -1) return 0;
            else k ++ ;

        while (k < str.size() && str[k] >= '0' && str[k] <= '9') {
            int x = str[k] - '0';
            if (minus > 0 && res > (INT_MAX - x) / 10) return INT_MAX;
            if (minus < 0 && -res < (INT_MIN + x) / 10) return INT_MIN;
            if (-res * 10 - x == INT_MIN) return INT_MIN;
            res = res * 10 + x;
            k ++ ;
        }

        res *= minus;
        return res;
    }
};

11 评论

Xkai 2021-07-03 10:48

不用特判也能过啊

alin 2020-11-09 12:03

为什么要加if (-res * 10 - x == INT_MIN) return INT_MIN;不是很明白

machine_gun_lin 2021-02-25 15:07

视频9分15秒回答了这个问题，因为INT_MAX和INT_MIN绝对值不一样，INT_MIN是-2147483648，这句话是特判这个case。

726 10个月前

因为INT_MAX和INT_MIN绝对值不一样，INT_MIN是-2147483648, 在这段代码下面，我们要做的是 res = res * 10 + x，如果我们不测试这个case，res * 10 + x 就会溢出. 因为（-res10-x = -2147483648），这意味着 res10+x=2147483648 会溢出

Udsnf 2020-08-16 14:42

y总，我把负数直接累加到最终结果中，可以少一步特判，且好想一点。

class Solution {
public:
    int strToInt(string str) {
        int res = 0;
        int neg = 0;
        int i = 0;
        while (i < str.size() && str[i] == ' ') i++;
        if (str[i] == '-') neg = -1;
        if (str[i] == '+' || str[i] == '-') ++i;
        for (; i < str.size(); ++i)
        {
            if (str[i] < '0' || str[i] > '9') break;
            else 
            {
                int x = str[i] - '0';
                if (neg == -1) 
                {
                    x = -x;
                    if ((INT_MIN - x) / 10 <= res)
                    {
                        res *= 10;
                        res += x;
                    }
                    else return INT_MIN;
                }
                else 
                {
                    if ((INT_MAX - x) / 10 >= res)
                    {
                        res *= 10;
                        res += x;
                    }
                    else return INT_MAX;
                }
            }
        }
        return res;
    }
};

yxc 2020-08-19 15:25

dys 2020-06-01 16:41

为什么要去除’\t’呢？

 while(k < str.size() && (str[k] == ' ' || str[k] == '\t')) k ++ ;

萌王赛高 2020-06-02 10:13

应该是找到第一个出现‘0’ ~’9‘，‘+’，‘-’的位置吧,去除\t表示过滤tab跳空格

yxc 2020-06-08 15:48

之前lc上没说不包含制表符，所以也去除了一下。不过现在lc上添加了一个说明：不包含制表符，所以不用过滤了。

七栖 2019-04-17 15:09

if (res > INT_MAX * 10ll) break;这里为什么*1101？不可以直接>INT_MAX吗？

yxc 2019-04-17 15:28

可以去掉，这里有点多此一举。代码中已去~

App 内打开