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

• 方法一：細節題

class Solution {
public:
    bool isNumber(string s) {
        bool sign = false;//是否有+或-
        bool num = false;//是否有數字
        bool point = false;//小數部分是否合法
        bool exp = false;//e之前是否合法
        //周遊判斷每一個字元
        for(int i=0; i<s.size(); i++){
        	//如果不是第一次出現的+或-，傳回false
            if(s[i]=='+' || s[i]=='-'){
                if(sign){
                    return false;
                }//如果是第一次出現，且是第一個字元或e之後的字元，表示合法
                if(i==0 || s[i-1]=='e'|| s[i-1]=='E'){
                    sign = true;
                }else{
                    return false;
                }
            //如果不是第一次出現或在e之後出現，傳回false
            }else if(s[i] == '.'){
                if(exp || point){
                    return false;
                }//否則表示合法
                point = true;
            //如果不是第一次出現或e之前沒有有效數字，傳回false
            }else if(s[i] == 'e'|| s[i]=='E'){
                if(exp ||(num == false )){
                    return false;
                }else{//否則表示合法，為之後判斷e後是否有有效數字做準備
                    sign = false;
                    num = false;
                    exp = true;
                }
            //如果為數字則表示num為有效數字
            }else if('0' <= s[i] && s[i] <='9'){
                num = true;
            }else{
            	//除了以上四類字元外的任何字元都傳回false
                return false;
            }
        }
        return num;//傳回所有字元串周遊結束後num是否為有效數字
    }
};
           

• 時間複雜度O(n)
• 空間複雜度O(1)
• 思路
  • 一個有效數字可以由以下幾部分組成：符号+整數部分+小數點+小數部分+指數e/E+符号+整數部分
    • 符号為非必需
    • 有效數字必需存在，可以為整數+小數點+小數部分或整數或小數點+小數部分
    • 一旦出現指數e，則其前必需出現有效數字且其後必需出現有效數字
  • 定義四個邏輯變量
    • sign：此前是否出現過+/-
    • num:此前是否有整數部分或小數部分
    • point:此前是否出現過小數點
    • exp:此前是否出現過e
  • 周遊字元串，對每個字元做判斷
    • 如果目前字元為+或-。判斷是否為第一次出現，如果是第一次出現且為第一個字元或它的前一個字元為e，将sign設定為true，其餘情況傳回false。（出現e之後會将sign的狀态重置，故隻需要判斷是否為第一次出現）
    • 如果目前的字元為‘.’。判斷是否第一次出現且在e出現之前出現，如果是則将point設定為true，否則傳回false。（根據point判斷小數部分的位置是否合法，即在e之前，故可以将整數部分與小數部分合并為一個變量即num）
    • 如果目前的字元為e或E。如果此時e是第一次出現且它之前有有效數字，将exp設定為true且将num、sign設定為false（為了為之後判斷e之後是否有有效數字做準備），否則傳回false。
    • 如果目前字元在0到9之間。表示有有效數字，将num設定為true。
    • 如果該字元不屬于以上任何一種情況，傳回false
  • 傳回此時是否有有效數字
• 方法二：有限自動機

細節題參考詳解