<aside> 💡 DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。
</aside>
<aside> 💡 NFA: 不确定有穷自动机: 当一个状态面对一个输入符号的时候,它所转换到的可能不只一个状态,可以是一个状态集合。 DFA与NFA的区别在于:DFA的每一次输入只对应一个结果,而NFA的依次输入可能对应多个结果,形成一个结果集,可以使用子集法将NFA构造为DFA
</aside>
class Solution {
public int myAtoi(String s) {
Automaton automaton = new Automaton();
for (int i = 0; i < s.length(); i++) {
automaton.process(s.charAt(i));
}
return (int) (automaton.sign * automaton.ans);
}
}
class Automaton {
// 表示数组的正负数, 如果碰到 - 则要变为 -1
public int sign = 1;
// 表示最终计算出来的数字
public long ans = 0;
// 表示当前状态
private String state = "start";
private Map<String, String[]> table = new HashMap<String, String[]>() {{
// 0 1 2 3
// ' ' +/- number other
// 因为包含前导空格, 所以碰到空格要再次转为start状态
put("start", new String[]{"start", "signed", "in_number", "end"});
put("signed", new String[]{"end", "end", "in_number", "end"});
put("in_number", new String[]{"end", "end", "in_number", "end"});
put("end", new String[]{"end", "end", "end", "end"});
}};
public void process(char c) {
// 根据当前状态获取碰到c字符之后的下个状态
state = table.get(state)[getCol(c)];
if ("in_number".equals(state)) {
// - '0' 是因为直接ascii码计算
ans = ans * 10 + c - '0';
// 如果是正数, 防止溢出, 则直接取min
// 如果是负数, 防止溢出, 则ans变负数取max然后转正数
ans = sign == 1 ? Math.min(ans, Integer.MAX_VALUE) : -Math.max(-ans, Integer.MIN_VALUE);
} else if ("signed".equals(state)) {
sign = c == '+' ? 1 : -1;
}
// start和end不需要任何操作
}
// 根据字符获取状态index
public int getCol(char c) {
if (c == ' ') return 0;
if (c == '+' || c == '-') return 1;
if (Character.isDigit(c)) return 2;
return 3;
}
}