原题描述
+
请你来实现一个atoi函数,使其能将字符串转换成整数。
首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:
注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。
在任何情况下,若函数不能进行有效的转换时,请返回0。
提示:
示例 1
输入:"42"
输出:42
示例 2
输入:"-42"
输出:-42
示例 3
输入:"4193 with words"
输出:4193
示例 4
输入:"words and 987"
输出:0
解释:非法输入
示例 5
输入:"-91283472332"
输出:-2147483648
解释:下溢出
原题链接:https://leetcode-cn.com/problems/string-to-integer-atoi
思路解析
+
这道题可是大公司面试常客,我希望你能够一次性搞明白。
如果你上来就开始根据规则制定if else的逻辑,那么你大概率会死在各种corner case上。从20.4%的通过率也能看出这一点,明明是一道中等难度题,硬生生的做成了困难题。
其实对编程语言的处理可比这道题复杂多了,如果套用一堆if else,那么这一坨代码就太可怕了。所以在编译原理的课中我们学习到了有限自动机(DFA)这种东西,我们只要抽象出几种状态,以及状态转换的规则,然后在代码中用table存起来,就可以非常容易的handle各种各样的边界条件和corner case,也十分容易理解。
对于这道题来说,我们可以抽象出以下四种state:start(起始), sign(符号), num(数字), end(结束)。DFA每读入一个字符,就有可能发生状态的转移,这就是我们所说的action。根据题干给定的规则,action可以有'+','-',' ', digit和其他非法字符other。
所有的状态转换关系我们可以绘制如下图所示。
好了,把这个DFA以哈希表的形式初始化到你的class中吧~
复杂度分析
+
C++参考代码
+
class DFA {
public:
int get_col(char c) {
if (c == ' ') return 0;
else if (c == '+' || c == '-') return 1;
else if (isdigit(c)) return 2;
else return 3;
}
void transform(char c) {
cur_state = table[cur_state][get_col(c)];
if (cur_state == "sign") {
sign = c == '+' ? 1: -1;
} else if (cur_state == "num") {
abs = abs * 10 + (c - '0');
abs = sign == 1 ? min(abs, (long)INT_MAX) : min(abs, -(long)INT_MIN);
}
}
map<string, vector<string>> table = {
{"start", {"start", "sign", "num", "end"}},
{"sign", {"end", "end", "num", "end"}},
{"num", {"end", "end", "num", "end"}},
{"end", {"end", "end", "end", "end"}}
};
string cur_state = "start";
int sign = 1;
long abs = 0;
};
class Solution {
public:
int myAtoi(string str) {
DFA dfa;
for (int i = 0; i < str.size(); ++i) {
dfa.transform(str[i]);
}
return dfa.abs * dfa.sign;
}
};