8.String to Integer (atoi)

Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function. If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed. If no valid conversion could be performed, a zero value is returned.
Note:Only the space character ' ' is considered as whitespace character. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: ([−2^{31}, 2^{31} − 1]). If the numerical value is out of the range of representable values, INT_MAX ((2^{31} − 1)) or INT_MIN ((−2^{31})) is returned.

思路分析

  1. 删除字符串首的若干空格,在第一个非空格字符后出现的空格均视为非法字符
  2. 处理正负号
  3. 对所有的数字字符进行转换,遇到非数字字符为止

实现细节

  • 在删除空格的操作中,由于使用的是replace()函数将空格替换为空字符,因此应始终判断字符串的第0位是否为空格,迭代变量不需要自加
  • 可以使用函数find_first_not_of()来进行删除空格的操作,类似的函数还有find_first_of()find_last_of()find_last_not_of()
  • 在C++中,双引号表示字符串,单引号表示字符,因此str[0]=="a"是不合法的,str.replace(0, 1, 'a')也是不合法的
  • 对于正负号的处理,使用一个整型变量indicator更加方便

代码实现

Approach1

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
class  {
public:
int myAtoi(string str) {
int len = str.size();
int i = 0;
while(i < len && str[i] == ' '){
str.replace(i, 1, "");

}
long ans = 0;
if (str[0] != '+' && str[0] != '-'){
str.insert(0, "+");
}
len = str.size();
i = 1;
while(str[i] <= '9' && str[i] >= '0'){
ans *= 10;
ans += int(str[i]) - 48;
i += 1;
if (str[0] == '+' && ans >= INT_MAX) return INT_MAX;
if (str[0] == '-' && -ans <= INT_MIN) return INT_MIN;
}
ans = str[0] == '+' ? ans : -ans;
return ans;
}
};

Approach2

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
class  {
public:
int myAtoi(string str) {
int len = str.size();
int i = 0;
int indicator = 1;
long ans = 0;
while(i < len && str[i] == ' '){
str.replace(i, 1, "");
}
if (str[0] == '+' || str[0] == '-'){
indicator = (str[0] == '-') ? -1 : 1;
i += 1;
}
len = str.size();
while(str[i] <= '9' && str[i] >= '0'){
ans *= 10;
ans += int(str[i]) - 48;
i += 1;
if (ans * indicator >= INT_MAX) return INT_MAX;
if (ans * indicator <= INT_MIN) return INT_MIN;
}
return ans * indicator;
}
};