每周算法：字符串转整数
Description
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: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
Example 1:
Input: "42"
Output: 42
Example 2:
Input: " -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.
Example 3:
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
Example 4:
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.
Example 5:
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.
Solution
Approach 1
这道题并不难，思路也比较容易想出来，下面就是我想到的解法。
可能需要注意的问题是：
- 字符到数字的转换，这个涉及到ascii码表的记忆，如果记不住了可以直接使用'0' 'a' 'A'
- 对于溢出的判断，我一开始只想到了使用
int temp=num*10; if (temp/10!=num)进行判断，实际上却忽略了2147483648（0x80000000）的边界情况，这个是需要特别注意的。
int parseChar(char ch) {
int num = ch - '0';
if (num > 9 || num < 0) {
return -1;
}
return num;
}
int myAtoi (string str) {
bool isNegative = false;
bool isOverflow = false;
int num = 0;
// 从前向后进行转换
size_t pos = 0;
// 去除多余的空格
while (str[pos] == ' ') {
++pos;
}
// 首先判断是否有符号位
if (str.length() > 0) {
if (str[pos] == '-') {
isNegative = true;
++pos;
}
else if (str[pos] == '+') {
++pos;
}
}
// 是否以数字进行开头
// 从左向右读取数字，每次读取需要判断是否溢出
for ( ; pos < str.length(); ++pos) {
int digit = parseChar(str[pos]);
if (digit < 0) {
// 负数说明该位不是数字了
break;
}
// 如何判断是否溢出
int temp = num*10;
if (temp/10 != num) {
isOverflow = true;
break;
}
num = temp + digit;
}
// 如果num变成负数，也是溢出了，相当于对最后一位检查溢出
if (isOverflow || num < 0) {
return isNegative ? INT_MIN : INT_MAX;
}
return isNegative ? -num : num;
}
Approach 2
下面这段代码目前是leetcode上运行速度最快的solution sample，仅仅耗时了4ms。作者使用了很多让程序跑得更快的方法，其中的技巧值得我学习。
static int fast = []() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
class Solution {
public:
int myAtoi(string str) {
long long sum = 0;
int base=10;
int n = str.size();
bool flag = true;
int sign = 1;
for(int i = 0; i < n; i++) {
if(isalpha(str[i])) {
return sum;
}
else if(str[i]==' '&&flag) {
continue;
}
else if(str[i]>='0' && str[i]<='9') {
sum = 10*sum + sign*(str[i] - '0');
flag = false;
}
else if(str[i] == '-' &&flag) {
sign = -1;
flag = false;
}
else if(str[i] == '+' && flag) {
flag = false;
}
else {
return sum;
}
if(sum > INT_MAX) {
return INT_MAX;
}
else if(sum < INT_MIN) {
return INT_MIN;
}
return sum;
}
};
- C++标准库中提供了判断是否是数字的接口
isdigit和判断是否是字母的接口isalpha。
- 使用以下代码能加速代码的运行速度，这段代码会停止C++和C输入输出流的同步，并且解除
cin和cout的捆绑，这里 有更详细的解释。效果很明显，将其添加到我的代码中，将我的代码的运行时间从20ms提升至8ms。
static int fast = []() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();