文章目录
前言
在我重复刷力扣题：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状态是一样的，只要读到非数字，就直接转到结束状态。
四、代码实现
1class Solution { 2 3 4 5 6 public int myAtoi(String str) { 7 8 9 10 Automaton auto = new Automaton(); 11 char[] ch = str.toCharArray(); 12 13 for(char c : ch){ 14 15 16 17 //如果auto.calculate(c)是false,则终止循环 18 if(!auto.calculate(c)) break; 19 } 20 return auto.sum; 21 } 22} 23class Automaton{ 24 25 26 27 //设置确定有限状态机的状态 28 final String START = "start";//开始状态 29 final String SIGNED = "signed";//符号位状态 30 final String IN_NUMBER = "in_number";//数字位状态 31 final String END = "end";//结束状态 32 33 String state = START;//设置初始状态，start 34 int sum = 0;//记录字符转换为数字的结果 35 int sign = 1;//记录符号 36 37 //通过HashMap构建一个DFA表 38 Map<String, String[]> table; 39 public Automaton(){ 40 41 42 43 table = new HashMap<>(); 44 table.put(START, new String[]{ 45 46 47 START, SIGNED, IN_NUMBER, END}); 48 table.put(SIGNED, new String[]{ 49 50 51 END, END, IN_NUMBER, END}); 52 table.put(IN_NUMBER, new String[]{ 53 54 55 END, END, IN_NUMBER, END}); 56 table.put(END, new String[]{ 57 58 59 END, END, END, END}); 60 } 61 62 //用来获取该字符所对应的DFA表里的列 63 public int getState(char c){ 64 65 66 67 if(c == ' ') return 0; 68 if(c == '+' || c == '-') return 1; 69 if(c >= '0' && c <= '9') return 2; 70 return 3; 71 } 72 73 public boolean calculate(char c){ 74 75 76 77 //table.get(state)获取到DFA表里的行 78 //getState(c)获取该字符在DFA表里的列 79 //两者组合，获取到了一个确定的状态 80 state = table.get(state)[getState(c)]; 81 82 if(END.equals(state)){ 83 84 85 //结束状态，返回false，传达终止信号 86 return false; 87 }else if(SIGNED.equals(state)){ 88 89 90 //符号位状态，记录当前符号 91 sign = c == '-' ? -1 : 1; 92 }else if(IN_NUMBER.equals(state)){ 93 94 95 //数字位状态 96 int num = c - '0';//将char 转换为 int 97 //此处题目要求，只能用int来存储数据类型，所以通过该方法判断sum是否越界 98 //如果没越界 99 if(sum >= (Integer.MIN_VALUE + num) / 10 && sum <= (Integer.MAX_VALUE - num) / 10){ 100 101 102 103 sum = sum * 10 + (sign * num); 104 }else{ 105 106 107 //如果越界了 108 sum = sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; 109 return false; 110 } 111 } 112 return true;//传达继续判断信号 113 } 114}
总结
通过DFA解决该问题，在不新增状态的条件下，修改某些要求，大部分情况我们只需要修改上述代码构建的table表，而不需要去修改其他地方的代码
本文分享 CSDN - 弹弹霹雳。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。