有限状态机及练习
对对象行为进行建模，描述对象在其声明周期的状态序列，以及如何响应外接的各种事件。如典型的TCP协议状态机。
如果把业务模型抽象成一个有限状态机，代码逻辑结构就会比较规整。
状态机四要素
- 现态：当前所处的状态
- 条件：又称事件。当一个条件满足时，触发一个动作，实现一次状态迁移。
- 动作：条件满足后执行的动作，可以迁移到新的状态，也可以不变。
- 次态：条件满足后要前往的新状态。
示例
剑指 Offer 20. 表示数值的字符串
可能出现的最复杂情况：+3.123e-12，首尾可能有空格。按照此形式定义几种状态：
注意：1.2、2.和.5的形式都是正确的，也就是说出现小数点那一刻（否则会有多个小数点情况），小数点和数字的性质是一样的，最开始，最末尾或者中间都是对的。
- 0，最开始的空格
- 1，e前面数字的符号
- 2，小数点前数字，✔️
- 3，小数点、小数点后数字✔️
- 4，小数点前无数字时，小数点、小数点后的数字，因为
-.是不可以的，而-1.是可以的。 - 5，e
- 6，e后面的符号
- 7，数字✔️
- 8，空白✔️
其中，2,3,4,8为合理结束的状态。
考虑状态迁移：
0：--空白-->0，--数字--> 2，--符号--> 1，--小数点--> 4
1：--数字-->2，--小数点-->4
2：--数字-->2，--小数点-->3，--e-->5，--空白-->8
3：--数字-->3，--e-->5，--空白-->8
4：--数字-->3
5：--符号-->6，--数字-->7
6：--数字-->7
7：--数字-->7，--空白-->8
8：--空白-->8
匿名内部类测试代码：
Map map = new HashMap<Character,Integer>() { { put('a',0); put('b',1); } };匿名内部类：
final class test$1 extends HashMap<Character, Integer> { test$1() { this.put('a', 0); this.put('b', 1); } }
代码：
class Solution {
public boolean isNumber(String s) {
Map[] states = {
new HashMap<Character,Integer>(){{put(' ',0); put('s',1);put('d',2);put('.',4);}}, //0
new HashMap<Character,Integer>(){{put('d',2);put('.',4);}}, //1
new HashMap<Character,Integer>(){{put('e',5); put(' ',8);put('d',2);put('.',3);}}, //2
new HashMap<Character,Integer>(){{put(' ',8); put('d',3);put('e',5);}}, //3
new HashMap<Character,Integer>(){{put('d',3);}}, //4
new HashMap<Character,Integer>(){{put('s',6);put('d',7);}}, //5
new HashMap<Character,Integer>(){{put('d',7);}}, //6
new HashMap<Character,Integer>(){{put('d',7);put(' ',8);}}, //7
new HashMap<Character,Integer>(){{put(' ',8);}} //8
};
int p = 0;
char t;
for(char c:s.toCharArray()) {
if(c>='0'&&c<='9') t='d';
else if(c=='+' || c=='-') t='s';
else if(c=='e' || c=='E') t='e';
else if(c=='.' || c==' ') t=c;
else t='?';
if(!states[p].containsKey(t)) return false;
p = (int)states[p].get(t);
}
return p==2||p==3||p==7||p==8;
}
}
总结：要写对不容易，状态首先要想对，状态之间的迁移也不能漏，像是这题的第四个：小数点前无数字时，小数点、小数点后的数字，就容易漏掉，状态的转移也自然写不对了。
剑指 Offer 67. 把字符串转换成整数
这个没啥必要用状态机，只是为了锻炼一下思维。
class Solution {
public int strToInt(String str) {
//0: 初始状态，--空白-->0，--符号-->1，--数字-->2
//1: 符号，--数字-->2,
//2: 数字，--数字-->2
Map[] states = {
new HashMap<Character,Integer>() {{put(' ',0);put('s',1);put('d',2);}},//0
new HashMap<Character,Integer>() {{put('d',2);}},//1
new HashMap<Character,Integer>() {{ put('d',2);}} //2
};
int curState = 0;
char key = ' ';
long cur = 0;
int sign = 1;
for(int i=0;i<str.length();i++) {
key = str.charAt(i);
if(key>='0'&&key<='9') key='d';
else if(key=='+'||key=='-') {
if(key=='-') sign=-1;
key='s';
}
else if(key==' ') key=' ';
else key='?';
if(!states[curState].containsKey(key)) {
break;
}
curState = (int)states[curState].get(key);
if(key=='d') {
cur=cur*10+(int)(str.charAt(i)-'0')*sign;
//System.out.println(cur);
if(cur>Integer.MAX_VALUE) return Integer.MAX_VALUE;
else if(cur<Integer.MIN_VALUE) return Integer.MIN_VALUE;
}
}
return curState==2?(int)cur:0;
}
}