LeetCode 008 — String to Integer

String to Integer (atoi)

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

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

  1. 字符可能以多个空格开始,处理的时候要舍弃左边的空格,从第一个不为空格的字符开始处理;
  2. 数值字符串可能以+-号开头,要正确处理;
  3. 数值字符串后可能带有多余的非数字字符,这些字符不会对结果造成影响,处理的时候要忽略;
  4. 第一个非空格字符不是合法的数字字符或者+-号的时候,这个字符串不是合法的数值字符串,要返回 0;
  5. 结果大于 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;
}
};
  1. 首先用 string::erase 配合 string::find_first_not_of(' ') 去掉字符串开头的空格;
  2. 接下来去掉数值字符串后面的多余字符,仅保留要处理的数值字符串;
  3. 这个时候可能只剩下一个空字符串或者单个+或者-字符,这里就直接返回结果;
  4. 到了真正处理数值字符串的时候了,先判断第一个字符是不是+-符号并记下正负标记;
  5. 接下来从前往后遍历,并处理数值,中途要是发现数值已经超过了32位整型就可以根据正负标记直接返回相应结果;
  6. 最后根据正负标记返回最终结果,完成!

总结

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

- EOF -

如果这篇文章对你有所帮助,请随意赞赏。
微信赞赏

微信赞赏

加载 Disqus 评论