LeetCode 008 — String to Integer

String to Integer (atoi)

https://leetcode.com/problems/string-to-integer-atoi/

题目大意就是自己实现一个 atoi 函数把字符串转换成一个整型数字

字符可能以多个空格开始，处理的时候要舍弃左边的空格，从第一个不为空格的字符开始处理；
数值字符串可能以+-号开头，要正确处理；
数值字符串后可能带有多余的非数字字符，这些字符不会对结果造成影响，处理的时候要忽略；
第一个非空格字符不是合法的数字字符或者+-号的时候，这个字符串不是合法的数值字符串，要返回 0；
结果大于 INT_MAX (2^31 − 1) 的时候返回 INT_MAX，结果小于 INT_MIN (−2^31) 的时候返回 INT_MIN 。

这题目看起来并不难，我上手一通操作提交之后，连错了三次，尴尬。。。

以下是可能碰到的部分容易出错的情况：

越界，这个字符串数值可能远远超过了32位整型所能表示的大小，甚至超过了64位。所以不要试图用 long long 来存储最终算出来的数值再跟 INT_MAX 比较，应该在计算过程中随时跟 INT_MAX 发现超过了，就可以停止计算，直接返回相应结果，这样既节省时间，又不会造成 long long 越界；
字符串以多个+-号开头，比如 “+–1234”。从第二个符号开始，并不是数字，那么这个字符串就是非法的，返回 0；
数值字符串和非数字字符中间可能并没有空格，不要被 Example 误导了，比如 “12AB”结果是 12；
+-号出现在字符串的中间，比如 “34+1”。这里的+号只能当做普通的非数字字符处理，因此结果返回 34；

Solution

class Solution {
public:
    int myAtoi(string str) {
        str.erase(0, str.find_first_not_of(' '));
        int last_pos = 0;
        for(last_pos = 0; last_pos < str.length(); ++last_pos) {
            if (last_pos == 0) {
                if (str[last_pos] != '+' && str[last_pos] != '-'
                    && (!(str[last_pos] >= '0' && str[last_pos] <= '9'))) {
                    break;
                }
            }
            else {
                if (!(str[last_pos] >= '0' && str[last_pos] <= '9')) {
                    break;
                }
            }
        }

        str.erase(last_pos);
        //cout<<"_"<<str<<"_"<<endl;

        if (str.empty()) {
            return 0;
        }

        if ((str[0] == '+' || str[0] == '-')) {
            if (str.length() == 1) {
                return 0;
            }
        }

        long long res = 0;
        bool is_negative = false;
        int i = 0;
        if (str[i] == '+' || str[i] == '-') {
            if (str[i] == '-') {
                is_negative = true;
            }
            ++i;
        }

        for (;i < str.length(); ++i) {
            res *= 10;
            res += str[i] - '0';
            if (res > INT32_MAX) {
                return is_negative ? INT32_MIN : INT32_MAX;
            }
        }

        return is_negative ? -res : res;
    }
};

首先用 string::erase 配合 string::find_first_not_of(' ') 去掉字符串开头的空格；
接下来去掉数值字符串后面的多余字符，仅保留要处理的数值字符串；
这个时候可能只剩下一个空字符串或者单个+或者-字符，这里就直接返回结果；
到了真正处理数值字符串的时候了，先判断第一个字符是不是+-符号并记下正负标记；
接下来从前往后遍历，并处理数值，中途要是发现数值已经超过了32位整型就可以根据正负标记直接返回相应结果；
最后根据正负标记返回最终结果，完成！

总结

从这题的 14.6% 的通过率来看 Medium 难度不是浪得虚名，要仔细研究题目里说的可能发生的每一种情况，并做好相应的处理，不然想一次 Accept 还是有难度的。

String to Integer (atoi)#

Solution#

总结#

String to Integer (atoi)

Solution

总结