文章目录
前言
在我重复刷力扣题:8. 字符串转换整数 (atoi) 时,发现了一个之前没发现的解法,就是确定有限状态机(DFA),此处对该解法做一个记录
一、确定有限状态机(DFA)是什么?
对于该题,就是逐字符读取题目给出的字符串,然后在当前状态下,读到该字符,应该转变为什么样子的状态,然后再通过该状态去进行相应的操作;
对于“有限”两字的理解,我的理解是,当前状态只会不断的朝着结束状态靠近,不会返回到上一级的状态,就是只会朝着可执行状态数量越来越少的方向靠近。
二、确定有限状态机(DFA)的作用
通过DFA,可以减少代码有过多的 if - else 条件判断语句(貌似这道题通过DFA并没有减少很多的 if - else语句,相反代码行数还挺多,应该是这道题的判断条件并不多,如果判断条件更加的多,更加的繁杂,通过DFA还是有相应的优化的);
使用DFA还可以增加代码的维护性,使代码更加容易修改和维护。
三、题目解析
对于该题,有四种状态,分别是:
start :读到空格时的状态
singed : 读到 - / + 号时的状态
in_number:读到数字时的状态
end:读到其他的字符时的状态
初始状态为start,作为该DFA的一个入口,可以列出下面这个状态表
‘ ’(空格)
+ / -
number(数字)
other(其他)
start
start
singed
number
other
singed
end
end
in_number
end
in_number
end
end
in_number
end
end
end
end
end
end
解释:(只举了其中一种可能的例子)
刚开始是start状态,如果刚开始读到的字符是空格,就对应的start的状态,不停的循环,直到读到非空格为止;
如果start的状态下读到了 + / - 号,那么就进入下一个状态singed状态,此状态下将读到的符号通过一个变量给存储下来。
根据题目的要求,符号的后面只能接数字,如果是非数字,那么这个字符串就无法转化为整数,直接返回0;所以,singed状态下如果读到了 空格、 符号、 其他字符,就直接跳转到结束状态,如果读到的是数字,那么就跳转到in_number状态,而in_number状态下和singed状态是一样的,只要读到非数字,就直接转到结束状态。
四、代码实现
class Solution {
public int myAtoi(String str) {
Automaton auto = new Automaton();
char[] ch = str.toCharArray();
for(char c : ch){
//如果auto.calculate(c)是false,则终止循环
if(!auto.calculate(c)) break;
}
return auto.sum;
}
}
class Automaton{
//设置确定有限状态机的状态
final String START = "start";//开始状态
final String SIGNED = "signed";//符号位状态
final String IN_NUMBER = "in_number";//数字位状态
final String END = "end";//结束状态
String state = START;//设置初始状态,start
int sum = 0;//记录字符转换为数字的结果
int sign = 1;//记录符号
//通过HashMap构建一个DFA表
Map<String, String[]> table;
public Automaton(){
table = new HashMap<>();
table.put(START, new String[]{
START, SIGNED, IN_NUMBER, END});
table.put(SIGNED, new String[]{
END, END, IN_NUMBER, END});
table.put(IN_NUMBER, new String[]{
END, END, IN_NUMBER, END});
table.put(END, new String[]{
END, END, END, END});
}
//用来获取该字符所对应的DFA表里的列
public int getState(char c){
if(c == ' ') return 0;
if(c == '+' || c == '-') return 1;
if(c >= '0' && c <= '9') return 2;
return 3;
}
public boolean calculate(char c){
//table.get(state)获取到DFA表里的行
//getState(c)获取该字符在DFA表里的列
//两者组合,获取到了一个确定的状态
state = table.get(state)[getState(c)];
if(END.equals(state)){
//结束状态,返回false,传达终止信号
return false;
}else if(SIGNED.equals(state)){
//符号位状态,记录当前符号
sign = c == '-' ? -1 : 1;
}else if(IN_NUMBER.equals(state)){
//数字位状态
int num = c - '0';//将char 转换为 int
//此处题目要求,只能用int来存储数据类型,所以通过该方法判断sum是否越界
//如果没越界
if(sum >= (Integer.MIN_VALUE + num) / 10 && sum <= (Integer.MAX_VALUE - num) / 10){
sum = sum * 10 + (sign * num);
}else{
//如果越界了
sum = sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
return false;
}
}
return true;//传达继续判断信号
}
}
总结
通过DFA解决该问题,在不新增状态的条件下,修改某些要求,大部分情况我们只需要修改上述代码构建的table表,而不需要去修改其他地方的代码
本文分享 CSDN - 弹弹霹雳。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。