題目：65. 有效數字

難度：困難

題目：

有效數字（按順序）可以分成以下幾個部分：

一個小數或者整數
（可選）一個 ‘e’ 或 ‘E’ ，後面跟着一個整數

小數（按順序）可以分成以下幾個部分：

（可選）一個符号字元（’+’ 或 ‘-’）
下述格式之一：
- 至少一位數字，後面跟着一個點 ‘.’
- 至少一位數字，後面跟着一個點 ‘.’ ，後面再跟着至少一位數字
- 一個點 ‘.’ ，後面跟着至少一位數字

整數（按順序）可以分成以下幾個部分：

（可選）一個符号字元（’+’ 或 ‘-’）
至少一位數字

部分有效數字列舉如下：

[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]

部分無效數字列舉如下：

[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”]

給你一個字元串 s ，如果 s 是一個有效數字，請傳回 true 。

示例1

輸入：s = “0”

輸出：true

示例2

輸入：s = “e”

輸出：false

示例3

輸入：s = “.”

輸出：false

示例4

輸入：s = “.1”

輸出：true

提示

1 <= s.length <= 20
s 僅含英文字母（大寫和小寫），數字（0-9），加号 ‘+’ ，減号 ‘-’ ，或者點 ‘.’ 。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/valid-number/

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題思路

（1）模拟法

最容易想到的方法就是模拟法，根據「有效數字定義」梳理各部分的限制。

定義幾個标志辨別：

isE

：是否有’E’或’e’，

isDot

：是否有點，

isSign

：是否有符号，

isNum

：是否有數字。

周遊字元串

，根據設計規則有以下情況：

遇到’E’或’e’：（1）已經有E了，錯誤（2）E之前需要有數字
遇到’+‘或’-’：（1）已有符号，錯誤（2）符号之前須有數字（3）符号之前不可有點
遇到’.’：//（1）已有點，錯誤（2）科學計算法之後需要是整數，是以不可有點（小數）
遇到數字： isNum = true
其它情況， return false

考慮到科學記數法的特殊性，是以在遇到’E’和’e’時，需要将

isE

、

isDot

、

isSign

三個标志位清除，因為在之後的判斷中又是重新的一輪判斷，不可被之前所影響。

class Solution {
public:
    bool isNumber(string s) {

        int n = s.size();
        int i = 0;
        bool isE = false, isDot = false, isSign = false, isNum = false;

        while (i < n)
        {
            if (s[i] == 'e' || s[i] == 'E')
            {
                //（1）已經有E了，錯誤（2）E之前需要有數字
                if (isE || !isNum) return false;
                //有了E之後，點、符号、數字等辨別符清空，因為之後又是一個新的是否有效數字判斷，該步十分關鍵
                isE = true; isDot = false; isSign = false; isNum = false;
            }
            else if (s[i] == '+' || s[i] == '-')
            {
                //（1）已有符号，錯誤（2）符号之前須有數字（3）符号之前不可有點
                if (isSign || isNum || isDot) return false;
                isSign = true;
            }
            else if (s[i] == '.')
            {
                //（1）已有點，錯誤（2）科學計算法之後需要是整數，是以不可有點（小數）
                if (isDot || isE) return false;
                isDot = true;
            }
            else if (s[i] >= '0' && s[i] <= '9')
            {
                isNum = true;
            }
            else
            {
                return false;
            }

            i++;
        }
        return isNum;
    }
};

（2）狀态機

确定有限狀态自動機，有一系列狀态：「初始狀态」、「接受狀态」。在算法領域，它與大名鼎鼎的字元串查找算法KMP 算法有着密切的關聯；在工程領域，它是實作正規表達式的基礎。

其運作的流程如下：

起初，這個自動機處于「初始狀态」。
随後，它順序地讀取字元串中的每一個字元，并根據目前狀态和讀入的字元，按照某個事先約定好的「轉移規則」，從目前狀态轉移到下一個狀态；
當狀态轉移完成後，它就讀取下一個字元。
當字元串全部讀取完畢後，如果自動機處于某個「接受狀态」，則判定該字元串「被接受」；否則，判定該字元串「被拒絕」。

對于本題，因為不同的字元将導緻判斷進入不同的狀态，是以使用狀态機求解是個不錯的選擇。用「目前處理到字元串的哪個部分」當作狀态的表述。根據這一技巧，不難挖掘出所有狀态：

初始狀态
符号位
整數部分
左側有整數的小數點
左側無整數的小數點（根據前面的第二條額外規則，需要對左側有無整數的兩種小數點做區分）
小數部分
字元 e
指數部分的符号位
指數部分的整數部分

根據合法字元串的格式，狀态機的轉換如下：

力扣每日一題：65. 有效數字題目：65. 有效數字解題思路

同時，轉移失敗即下一字元找不到「接受狀态」，則判斷該字元串「不接受」，比對結束。

class Solution {
public:
    enum State 
    {
        STATE_INITIAL,
        STATE_SIGN,
        STATE_INTEGER,
        STATE_DOT_DECIMALS,
        STATE_DOT_INTEGER,
        STATE_DOT,
        STATE_EXP,
        STATE_EXP_SIGN,
        STATE_EXP_NUM,
        STATE_END
    };

    enum CharType
    {
        CHAR_NUM,
        CHAR_EXP,
        CHAR_DOT,
        CHAR_SIGN,
        CHAR_ERROR
    };
    CharType getType(char ch)
    {
        if (ch >= '0' && ch <= '9')
        {
            return CHAR_NUM;
        }
        else if (ch == 'E' || ch == 'e')
        {
            return CHAR_EXP;
        }
        else if (ch == '.')
        {
            return CHAR_DOT;
        }
        else if (ch == '+' || ch == '-')
        {
            return CHAR_SIGN;
        }
        else
        {
            return CHAR_ERROR;
        }
    }
    bool isNumber(string s) {

        unordered_map<State, unordered_map<CharType, State>> mapState= {

            {
                STATE_INITIAL, {
                    {CHAR_NUM, STATE_INTEGER},
                    {CHAR_DOT, STATE_DOT_DECIMALS},
                    {CHAR_SIGN, STATE_SIGN}
                }
            },

            {
                STATE_SIGN, {
                    {CHAR_NUM, STATE_INTEGER},
                    {CHAR_DOT, STATE_DOT_DECIMALS}
                }
            },

            {
                STATE_INTEGER, {
                    {CHAR_NUM, STATE_INTEGER},
                    {CHAR_DOT, STATE_DOT_INTEGER},
                    {CHAR_EXP, STATE_EXP}
                }
            },

            {
                STATE_DOT_DECIMALS, {
                    {CHAR_NUM, STATE_DOT}
                }
            },

            {
                STATE_DOT_INTEGER, {
                    {CHAR_NUM, STATE_DOT},
                    {CHAR_EXP, STATE_EXP}
                }
            },

            {
                STATE_DOT, {
                    {CHAR_NUM, STATE_DOT},
                    {CHAR_EXP, STATE_EXP}
                }
            },

            {
                STATE_EXP, {
                    {CHAR_SIGN, STATE_EXP_SIGN},
                    {CHAR_NUM, STATE_EXP_NUM}
                }
            },

            {
                STATE_EXP_SIGN, {
                    {CHAR_NUM, STATE_EXP_NUM}
                }
            },

            {
                STATE_EXP_NUM, {
                    {CHAR_NUM, STATE_EXP_NUM}
                }
            }
        };


        //開始
        int n = s.size();
        State st = STATE_INITIAL;

        for (int i = 0; i < n; i++)
        {
            CharType ct = getType(s[i]);
            if (mapState[st].find(ct) == mapState[st].end())
            {
                return false;
            }
            else
            {
                st = mapState[st][ct];//修改狀态
            }
        }

        //整數、小數、科學記數法整數、左邊為整數小數點
        return st == STATE_INTEGER || st == STATE_DOT || st == STATE_EXP_NUM || st == STATE_DOT_INTEGER;
        
    }
};

（3）正規表達式

注意，正規表達式pattern使用類的靜态變量或者全局變量，避免重複構造的開銷。

class Solution {
public:
    static const regex pattern;

    bool isNumber(string s) {

        return regex_match(s, pattern);
    }
};
const regex Solution::pattern("[+-]?(?:\\d+\\.?\\d*|\\.\\d+)(?:[Ee][+-]?\\d+)?");

const regex pattern = regex("[+-]?(?:\\d+\\.?\\d*|\\.\\d+)(?:[Ee][+-]?\\d+)?");
class Solution {
public:
    bool isNumber(string s) {

        return regex_match(s, pattern);
    }
};

力扣每日一題：65. 有效數字題目：65. 有效數字解題思路

目錄

題目：65. 有效數字

示例1

示例2

示例3

示例4

提示

解題思路

（1）模拟法

（2）狀态機

（3）正規表達式

繼續閱讀

python之判斷字元裡面有沒有|8

淺談MFC CSting類拼接效率

C和java中關于字元串與字元數組的定義和轉化

Java：String類字元串與數組之間的轉換

Java中 byte[] 數組與 String 字元串的轉化

對角線周遊LeetCode–對角線周遊

回文樹學習小結

GSL--GNU Scientific Library

查找算法之二分查找查找算法之二分查找

查找檔案中的字元串

LeetCode-110-平衡二叉樹-C語言

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

neo4j之cypher使用文檔

LeetCode OJ Binary Tree Right Side View

leetcode809