LeetCode 8. 字符串转换整数 (atoi)

发表于 | 更新于 | 分类于

题意

实现一个atoi函数，具体功能如下：

  1. 丢弃开头无用的空格，直到找到第一个非空格的字符为止。
  2. 当寻找到的第一个非空字符为正负号时或数字时，将其与后面尽可能多的连续数字组合起来形成整数。剩余的部分忽略。
  3. 如果第一个字符非上面三种情况时，则返回0。
  4. 如果数值超过了int的范围则返回INT_MAX或INT_MIN。

思路

  • 直接模拟，注意细节就好了。时间复杂度$O(n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int myAtoi(string str) {

        int len = str.size(), st = 0;
        for(int i = 0; i < len; ++i)
            if(str[i] != ' ')
            {
                st = i;
                break;
            }

        //cout << st << ' ' << str[st] << endl;

        bool flag = true;
        if(str[st] == '+')
            ++st;
        else if(str[st] == '-')
        {
            flag = false;
            ++st;
        }

        //cout << flag << endl;

        int res = 0;
        if(isdigit(str[st]))
        {
            while(st < len && isdigit(str[st]))
            {
                //cout << "res = " << res << endl;
                int add = str[st++] - '0';
                if( flag && ( res > INT_MAX / 10 || ( res == INT_MAX / 10 && add >= 7)))   return INT_MAX;
                if(!flag && (-res < INT_MIN / 10 || (-res == INT_MIN / 10 && add >= 8)))   return INT_MIN;
                res = res * 10 + add;
                //cout << res << ' ' << add << ' ' << st << endl;
            }
            //cout << res << endl;
            if(!flag)   res = -res;
            return res;
        }
        else
            return 0;

    }
};

总结

运行时间只击败了60%的用户。。看了下最快的代码，思路没啥区别，就是少了几个判断，没必要再“优化”了。

如：中间的存储答案的变量是用的long（我一开始也打算用long的）、判断符号位直接用的int（符号和正号的ASSIC码正好差2——用44 - str[i] 正好等于1或-1）。

Donate comment here
0%