8. String to Integer (atoi)

String to Integer (atoi)

題目描述：實作 myAtoi(string s) 函式，將字串轉換為 32 位元有號整數，需依序處理：略過前導空白、識別正負號、讀取數字字元、處理超出 [-2^31, 2^31-1] 範圍的溢位情況。

解題思路：

這道題考的是仔細的逐步解析與溢位偵測，沒有複雜的演算法，但需要處理多種邊界情況。

解析步驟：

1. 略過前導空白：用 while 迴圈跳過所有空格字元（s[i] == ' '）。
2. 處理符號：若當前字元是 + 或 -，記錄符號並移動索引。
3. 讀取數字：持續讀取 '0'~'9' 的字元，每次將當前數字乘以 10 再加上新的數字。
4. 溢位偵測（最關鍵）：在每次更新結果前，需先檢查是否會超出 INT_MAX (2,147,483,647)。

溢位判斷技巧：

溢位條件：result > INT_MAX / 10，或 result == INT_MAX / 10 && digit > 7（因為 INT_MAX 個位數是 7）。為何是 7？因為 INT_MAX = 2147483647，而 INT_MIN = -2147483648。若為正數，最後一位最大是 7；若為負數，最後一位最大是 8，但由於我們先用正數計算再加符號，統一用 7 即可（多 1 的情況 -2147483648 在加上負號後仍合法）。一旦偵測到溢位，立即返回 INT_MAX 或 INT_MIN。

時間複雜度：O(N) — 其中 N 是字串長度。我們最多遍歷字串一次，每個字元只被處理一次（跳過空白、讀取符號、讀取數字各最多一次線性掃描）。

空間複雜度：O(1) — 只使用常數個變數（索引、符號、結果），不需要額外的資料結構。

有限狀態機（DFA） O(N)：將解析過程建模為有限狀態自動機，狀態包括 start、signed、in_number、end。每次讀取一個字元根據當前狀態和輸入字元決定下一個狀態與動作。這個方法在處理更複雜的數字格式（如浮點數）時更具擴展性，也是工業級詞法分析器的標準做法，但對這道題來說程式碼較為冗長。

正規表達式 O(N)：用 regex 匹配 ^\s*[+-]?\d+ 提取數字部分後再轉換。這種方式程式碼簡潔，但在 C++ 中 regex 效能較差，且面試中通常不被鼓勵使用，因為無法展示對溢位處理的理解。

1. 如果需要解析浮點數（如 "3.14" 或 "-0.5e2"），你會如何修改現有的解析邏輯？
2. 溢位偵測使用了 INT_MAX / 10 的技巧，若改用 long long 中間變數來偵測溢位，有什麼優缺點？
3. 在什麼情況下字串解析應該使用有限狀態機（DFA）而非逐步 if-else？請舉例說明。