題目

有效數(shù)字

有效數(shù)字（按順序）可以分成以下幾個(gè)部分：

• 若干空格
• 一個(gè)小數(shù)或者整數(shù)
• （可選）一個(gè)’e’或’E’，后面跟著一個(gè)整數(shù)
• 若干空格

小數(shù)（按順序）可以分成以下幾個(gè)部分：

• （可選）一個(gè)符號(hào)字符（‘+‘或’-’）
• 下述格式之一：
  • 至少一位數(shù)字，后面跟著一個(gè)點(diǎn) ‘.’
  • 至少一位數(shù)字，后面跟著一個(gè)點(diǎn) ‘.’,后面再跟著至少一位數(shù)字
  • 一個(gè)點(diǎn) ‘.’,后面跟著至少一位數(shù)字

整數(shù)（按順序）可以分成以下幾個(gè)部分：

• （可選）一個(gè)符號(hào)字符（‘+‘或’-’）
• 至少一位數(shù)字

部分有效數(shù)字列舉如下：[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”,
“-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]

部分無(wú)效數(shù)字列舉如下：[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”,
“95a54e53”]

給你一個(gè)字符串 s，如果 s 是一個(gè)有效數(shù)字，請(qǐng)返回 true。

示例 1：

輸入：s = “0” 輸出：true

示例 2：

輸入：s = “e” 輸出：false

示例 3：

輸入：s = “.” 輸出：false

提示：

1 <= s.length <= 20 s 僅含英文字母（大寫(xiě)和小寫(xiě)），數(shù)字（0-9），加號(hào)’+‘，減號(hào)’-‘，空格’ ‘或者點(diǎn)’.'。

解法

• 這道題很容易想到遍歷字符串，對(duì)不同情況進(jìn)行判斷，遇到不符合題意的情況就直接退出
• 但是情況數(shù)比較多，需要寫(xiě)很多判斷分支，比如底數(shù)是否有正負(fù)符號(hào)就有3種情況，指數(shù)有沒(méi)有正負(fù)符號(hào)又是三種情況，這已經(jīng)有九種情況符合題意了
• 能不能有一種方法，以簡(jiǎn)潔的方式規(guī)定好每種情況后面可以出現(xiàn)的情況，一旦出現(xiàn)了不在規(guī)定里的情況，就不為有效數(shù)字；并且如果在還未完成有效數(shù)字時(shí)，在某個(gè)中間情況戛然而止，也不為有效數(shù)字
• 這其實(shí)有點(diǎn)像拓?fù)渑判?#xff0c;在這題中，對(duì)有向無(wú)環(huán)圖，定義每個(gè)節(jié)點(diǎn)以及所有有效的最終節(jié)點(diǎn)，查找從起始節(jié)點(diǎn) u 是否有路徑 u->v 通往最終節(jié)點(diǎn) v
  

class Solution {
public:bool validNumber(string s) {//0.前導(dǎo)空格->0,1,2,4//1.底數(shù)正負(fù)符號(hào)->2,4//2.底數(shù)有整數(shù)部分的整數(shù)（234的2）->2,3,5,8//3.小數(shù)點(diǎn)或者點(diǎn)后的數(shù)字->3,5,8//4.底數(shù)沒(méi)有整數(shù)部分時(shí)的小數(shù)點(diǎn)（.123的.），當(dāng)小數(shù)點(diǎn)后有數(shù)字->3//5.e或者E->6,7//6.指數(shù)正負(fù)符號(hào)->7//7.指數(shù)部分的數(shù)字->7,8//8.后導(dǎo)空格->8//2,3,7,8為正確的出口vector<map<char, int>> states = {{{' ',0}, {'s',1}, {'d',2}, {'.',4}},   //在0狀態(tài)遍歷到的符號(hào)對(duì)應(yīng)的可以轉(zhuǎn)移的狀態(tài){{'d',2}, {'.',4}},                     //1狀態(tài)轉(zhuǎn)移{{'d',2}, {'.',3}, {'e',5}, {' ',8}},   //2狀態(tài)轉(zhuǎn)移{{'d',3}, {'e',5}, {' ',8}},            //3{{'d',3}},                              //4{{'s',6}, {'d',7}},                     //5{{'d',7}},                              //6{{'d',7}, {' ',8}},                     //7{{' ',8}}                               //8};char curChType = '?';//當(dāng)前字符類(lèi)型，數(shù)字'd'、符號(hào)'s'、冪符號(hào)'e'、點(diǎn)'.'、空格' 'int curState = 0;//初始狀態(tài)設(shè)置為0，因?yàn)?沒(méi)有前驅(qū)狀態(tài)for(auto &ch:s){if(isdigit(ch)) curChType='d';else if(ch=='+' || ch=='-') curChType='s';else if(ch=='e' || ch=='E') curChType='e';else if(ch=='.') curChType='.';else if(ch==' ') curChType=' ';else return false;if(states[curState].find(curChType) != states[curState].end()){curState = states[curState].find(curChType)->second;}else return false;}return curState==2 || curState==3 || curState==7 || curState==8;}
};