題目描述:判斷給定字串 s 是否表示一個有效數字。有效數字包含:整數(可帶符號)、十進位小數,以及科學記號(e 或 E 後接整數)。
解題思路:使用規則驅動的逐字元掃描,追蹤五個狀態旗標:
seenDigit:已見到至少一個數字。seenDot:已見到小數點('.')。seenE:已見到指數符號('e' 或 'E')。seenSign:本段已見到符號('+' 或 '-')。seenDigitAfterE:指數部分已見到數字(驗證指數非空)。掃描規則:
seenDigit = true(若已過 'e' 則設 seenDigitAfterE = true)。'+' / '-':只能出現在最開頭或緊接在 'e'/'E' 之後;若 seenSign 或 seenDigit(非剛遇到 e)已設,則非法。'.':只能出現一次且不能在 'e' 之後。'e' / 'E':只能出現一次,且其前必須有數字;出現後重置 seenDigit、seenDot、seenSign 的相關限制。false。最終:seenDigit(整數部或指數部必須有數字)且若有 'e' 則 seenDigitAfterE 也必須為真。
時間複雜度:O(n) — 只需對字串進行一次線性掃描,每個字元的處理為 O(1),其中 n 為字串長度。
空間複雜度:O(1) — 只使用常數個布林旗標,不需要額外的動態記憶體。
1. Initialize flags: seenDigit=false, seenDot=false, seenE=false.
2. For each character c at index i in s:
a. If c is '0'-'9': set seenDigit = true.
b. If c is '+' or '-':
- If i != 0 AND s[i-1] is not 'e'/'E': return false.
c. If c is '.':
- If seenDot OR seenE: return false.
- Set seenDot = true.
d. If c is 'e' or 'E':
- If seenE OR NOT seenDigit: return false.
- Set seenE = true, seenDigit = false.
e. Else: return false.
3. Return seenDigit.方法一:有限狀態機(DFA) 將所有合法輸入轉換定義為狀態轉移表(約 8-10 個狀態),逐字元查表轉換狀態。最終判斷當前狀態是否為接受狀態。時間複雜度 O(n),空間複雜度 O(1)。優點是邏輯嚴謹、易擴展,缺點是定義狀態和轉移表較繁瑣。
方法二:正規表達式
使用 std::regex 比對模式 [+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?。時間複雜度依實作而定(通常 O(n)),程式碼極短,但在面試中通常不被接受且 C++ regex 效能較差。
0x1A3F)或二進位數字(如 0b1010),需要如何修改旗標和判斷邏輯?" 3.14 "),是否應先 trim 再判斷?這在實際語言解析器中是如何處理的?