leetCode有一些看上去簡(jiǎn)單，其實(shí)讓人頭疼的題，比如有限狀態(tài)機(jī)DFA
DFA（deterministic finite automaton ）有限狀態(tài)機(jī)
狀態(tài)機(jī)表示若干個(gè)狀態(tài)以及在這些狀態(tài)之間的轉(zhuǎn)移和動(dòng)作等行為的數(shù)學(xué)模型。
通俗的描述狀態(tài)機(jī)就是定義了一套狀態(tài)変更的流程：狀態(tài)機(jī)包含一個(gè)狀態(tài)集合，
定義當(dāng)狀態(tài)機(jī)處于某一個(gè)狀態(tài)的時(shí)候它所能接收的事件以及可執(zhí)行的行為，執(zhí)行完成后，狀態(tài)機(jī)所處的狀態(tài)。
DFA是一個(gè)含5個(gè)元素的元祖(S, q0, T, F, Σ)
S：狀態(tài)的集合
q0：初始化狀態(tài)
T：過(guò)渡方式？（transition function，此處翻譯的不大準(zhǔn)確）
F：結(jié)束狀態(tài)的集合
Σ：全部的字母表
比如說(shuō)圖G1就是一個(gè)DFA圖，那么
S:{0,1,2}
q0:{0}
T:此處可以列個(gè)表
| state/letter | a | b |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 2 | 0 |
| 2 | 2 | 2 |
F:{2}
Σ:{a,b}
上面其實(shí)不重要=。=，直接看題吧，看似很簡(jiǎn)單，實(shí)際好麻煩。來(lái)看LeetCode題
LeetCode很少題有5個(gè)示例的，狀態(tài)之多，越寫(xiě)越懵==
簡(jiǎn)單分析一下，要干的事其實(shí)不難，把一個(gè)字符串轉(zhuǎn)換成int類型的整數(shù)，首先要找到一個(gè)非空的字符，如果第一個(gè)非空的字符不是數(shù)字"0~9" 和'+','-'，返回0；如果第一個(gè)字符是數(shù)字（包含+','-'），后面出現(xiàn)非數(shù)字截止。。
紙上分析一下問(wèn)題的狀態(tài)圖（實(shí)際上是盜官方的圖）：
- 都有哪幾種狀態(tài)
有start，end兩個(gè)狀態(tài)，還有兩個(gè)中間態(tài)sign（判斷符號(hào)）,in_number（數(shù)字） - 確定自動(dòng)機(jī)中需要考慮的數(shù)據(jù)分類
答：數(shù)據(jù)有4類：數(shù)字，正負(fù)符號(hào)，空格和其他 - 確定自動(dòng)機(jī)中數(shù)據(jù)的狀態(tài)
答：自動(dòng)機(jī)最后返回的結(jié)果為數(shù)字＊正負(fù)符號(hào)，若是遇到其他則返回0，空格不影響結(jié)果。 - 確定自動(dòng)機(jī)的開(kāi)始和結(jié)束
答：當(dāng)遇到數(shù)字，或者正負(fù)符號(hào)的時(shí)候，自動(dòng)機(jī)開(kāi)始。
當(dāng)數(shù)字溢出，或者遇到其他，或者得到最后的結(jié)果，自動(dòng)機(jī)結(jié)束。 - 確定自動(dòng)機(jī)開(kāi)始后的流程
- 遇到數(shù)字，［自動(dòng)機(jī)開(kāi)始］，進(jìn)行計(jì)算，［溢出返回或計(jì)算結(jié)束返回，自動(dòng)機(jī)結(jié)束］
- 遇到正負(fù)符號(hào)，［自動(dòng)機(jī)開(kāi)始］，符號(hào)保留
- 遇到不是數(shù)字，不是空格的，直接返回0
- [自動(dòng)機(jī)開(kāi)始］的狀態(tài)下，遇到非數(shù)字，［自動(dòng)機(jī)結(jié)束］
嗯，流程已經(jīng)比較清晰了，代碼就是把分析好的流程翻譯一下
class Solution {
public int myAtoi(String str) {
boolean flag = true;// 符號(hào)位
Long result = 0L;//數(shù)值結(jié)果，因?yàn)橐袛鄆nt最大值，long方便一點(diǎn)
boolean begin = false;
char[] charArray = str.toCharArray();
for (char c : charArray) {
if (c >= '0' && c <= '9') {
result = result * 10 + c - '0';
if (flag && result >= Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (!flag && -result <= Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
begin = true;
} else {
if (!begin && c == '-') {
flag = false;
begin = true;
continue;
}
if (!begin && c == '+') {
flag = true;
begin = true;
continue;
}
if (begin && (c < '0' || c > '9')) {
break;
}
if (!begin && c != ' ') {
return 0;
}
}
}
return flag ? Integer.parseInt(result.toString()) : -Integer.parseInt(result.toString());
}
}
邊界值還是很煩。。
