8. String to Integer (atoi)

📘 題目敘述

請實作 myAtoi(string s)，將字串轉換成 32-bit 有號整數（signed integer）。

轉換規則如下：

1. 先忽略字串開頭的空白字元（space）。
2. 接著可以讀取一個可選的正負號 '+' 或 '-'。
3. 然後讀取連續的數字字元（'0' 到 '9'），並將其視為整數。
4. 讀取數字結束後，停止轉換；其後的字元不再處理。
5. 若沒有讀取到任何數字，結果為 0。
6. 若結果超出 32-bit 有號整數範圍 [-2^31, 2^31 - 1]，則需要截斷：
   • 小於 -2^31 回傳 -2^31
   • 大於 2^31 - 1 回傳 2^31 - 1

條件限制

• 0 <= s.length <= 200
• s 由英文字母、數字、空白 ' '、'+'、'-'、'.' 等字元組成

🧠 解題思路

我把這題想成「從左到右掃描字串」，並且用幾個變數記錄目前處理到哪個階段。

所有變數

• start：是否仍在「前置處理階段」
  • start = true：表示我還在處理開頭空白、以及正負號（數字還沒開始）
  • start = false：表示我已經開始讀數字（或已經確認過正負號），接下來遇到非數字就應該停止
• sign：結果的正負號
  • 初始為 +1
  • 若遇到 '-'，就改成 -1
• ans：目前累積出來的數字（用 long long 暫存，避免中途溢位）
• max / min：32-bit 有號整數範圍上界與下界，用來做溢位截斷

接下來我逐字掃描 s[i]，會遇到以下幾種情況：

情況一：遇到空白字元 ' '（且仍在 start 階段）

• 表示目前還在處理字串開頭的前導空白
• 在這個階段，空白字元對數值轉換沒有意義，應該被忽略

我的做法是：

• 直接將這個空白字元從字串中刪除：s.erase(i, 1)
• 接著將 i--，讓下一次迴圈仍然檢查同一個位置

這樣的效果等同於「跳過所有前面的空白」。

情況二：遇到 '+' 或 '-'（且仍在 start 階段）

• 代表目前讀到的是數字的正負號
• 如果是 '-'，表示最後的結果應該是負數，因此將 sign 設為 -1
• 不論是 '+' 或 '-'，都表示「符號已經處理完成」

因此在讀到正負號後：

• 會將 start 設為 false
• 表示接下來應該開始讀取數字，一旦再遇到非數字字元，就必須停止轉換

情況三：遇到數字字元 '0' 到 '9'

• 表示正式開始（或持續）累積整數值
• 一旦進入數字階段，就將 start 設為 false

在把數字加進 ans 之前，我會先進行「溢位檢查」：

• 若是正數，且下一步會超過 2147483647，直接回傳最大值
• 若是負數，且下一步會小於 -2147483648，直接回傳最小值

只有在確認不會溢位的情況下，才會執行：

• ans = ans * 10 + (s[i] - '0')

情況四：遇到其他非數字字元

這時代表數字讀取應該停止。

我的做法是：

• 直接把 i 後面的全部刪掉：s.erase(i)
• 然後 break 結束迴圈

最後回傳

• 回傳 sign * ans
• 若從頭到尾都沒遇到數字，ans 會維持 0，因此自然回傳 0

💻 程式碼實作

class Solution {
public:
    int myAtoi(string s) {
        bool start = true;
        int sign = 1;
        long long int ans = 0;
        int max = 2147483647;
        int min = -2147483648;
        for (int i = 0; i < s.size(); i++) {
            if ((s[i] >= '0') && (s[i] <= '9')) {
                start = false;
                if ((sign == 1) &&
                    (ans > (max / 10) || (ans == (max / 10) && (s[i] > '7')))) {
                    return max;
                } else if ((sign == -1) &&
                           (ans > (max / 10) ||
                            (ans == (max / 10) && (s[i] > '8')))) {
                    return min;
                }
                ans = ans * 10 + (s[i] - '0');
            } else if (start && (s[i] == ' ')) {
                s.erase(i, 1);
                i--;
            } else if (start && ((s[i] == '+') || (s[i] == '-'))) {
                if (s[i] == '-') {
                    sign = -1;
                }
                start = false;
            } else {
                s.erase(i);
                break;
            }
        }
        return sign * ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/string-to-integer-atoi/