题目：
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
--如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
--假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
--该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−2^31) 。
解答：
解答一：状态机
class Automation2 { public: int getInt(string str) { for (char c: str) { int val = getChar(c); state = table[state][val]; if (state == "signed") sign = (c == '+') ? 1 : -1; else if (state == "number") { result = result * 10 + c - '0'; if (sign == 1) { if (result > (long long)INT_MAX) return INT_MAX; } //如果符号为-1 if (result*sign < INT_MIN) return INT_MIN; } else if (state == "end") break; } if (sign == 1) { if (result > (long long)INT_MAX) return INT_MAX; return result; } //如果符号为-1 if (result*sign < INT_MIN) return INT_MIN; return (result*sign); } private: //0-空格（去掉第一个非空字符之前的空格） //1-正负号 //2-数字 //3-其他 unordered_map< string, vector<string>> table = { { "start", { "start", "signed", "number", "end" } }, { "signed", { "end", "end", "number", "end" } }, { "number", { "end", "end", "number", "end" } }, { "end", { "end", "end", "end", "end" } } }; string state = "start"; int sign = 1; //+1 -1，注意设置初始值，不然为随机数; long long result = 0; //功能：根据输入字符，获取对应的标志; int getChar(char c) { if (isspace(c)) return 0; else if (c == '+' || c == '-') return 1; else if (isdigit(c)) return 2; return 3; } }; class Solution { public: int myAtoi(string s) { Automation2 au; return au.getInt(s); } };
解答二：C风格
int myAtoi2(string str) { int index = 0; int sign = 1; long long result = 0; while(str[index] == ' ') //去掉开头的空格 index++; if (str[index] == '+' || str[index] == '-')//判断符号 { if (str[index] == '-') sign = -1; index++; } while (isdigit(str[index])) { result = result * 10 + str[index] - '0'; if (sign == 1) { if (result > INT_MAX) { return INT_MAX; } } else { if (-1 * result < INT_MIN) { return INT_MIN; } } index++; } return sign*result; }
然后发现与速度排在前面的代码差不多，但是排名有差距，看了代码发现有一些改进的地方：
1.没有判断第一个字符是否是有效的，即数字、+、-，如果不是直接返回：
修改后，还是有差距，
2.没有判断输入字符串s是否有效，如果为空则直接返回0：
最后代码：
int myAtoi2(string str) { if (str.empty()) return 0; int index = 0; int sign = 1; long long result = 0; while(str[index] == ' ') //去掉开头的空格 index++; //判断是否是非法的，是的话直接返回 if (isdigit(str[index]) == false && (str[index] != '+') && (str[index] != '-')) return 0; if (str[index] == '+' || str[index] == '-')//判断符号 { if (str[index] == '-') sign = -1; index++; } while (isdigit(str[index])) { result = result * 10 + str[index] - '0'; if (sign == 1) { if (result > INT_MAX) { return INT_MAX; } } else { if (-1 * result < INT_MIN) { return INT_MIN; } } index++; } return sign*result; }
溢出判断：
while (i < s.length() && (s[i] <= '9' && s[i] >= '0'))//获取数字 { if (flag == 0 && res >= INT_MAX / 10) //溢出判定 { if (res == INT_MAX / 10 && (s[i] == '8' || s[i] == '9')) return INT_MAX; if (res > INT_MAX / 10) return INT_MAX; } if (flag == 1 && res >= INT_MAX / 10) { if (res == INT_MAX / 10 && (s[i] == '8' || s[i] == '9')) return INT_MIN; if(res > INT_MAX / 10) return INT_MIN; } res = res * 10 + (s[i] - '0'); i++; }
可以不使用long long来简化代码，判断result*10之前有无大于INT_MAX，这样可以减少内存使用。
总结：
1.fsm不会用！多看下；
2.使用C风格时，注意一些条件的判断，以减少没必要的代码执行；