LeetCode 008 字符串轉整數 (atoi) 詳細題解與 Java 實現

LeetCode 008 字符串轉整數 (atoi) 詳細題解與 Java 實現

一、題目要求

實現 atoi：將字符串轉為 32 位有符號整數。

• 忽略前導空白
• 可選 +/- 號
• 連續數字字符構成數值
• 非數字字符終止解析
• 空字符串/無有效數字 → 0
• 溢出 → 返回 INT_MAX (2147483647) 或 INT_MIN (-2147483648)

二、核心邏法

1. trim() 去除首尾空白
2. toCharArray() 轉字符數組
3. 標志位記錄符號位，將符號位置為 '0' 統一處理
4. 確定最高位 (連續數字長度)
5. 循環累加：sum += (ch - '0') * 10^pos，用 long 防溢出
6. 應用符號位，邊界檢查截斷

三、完整 Java 實現

class Solution {
    public int myAtoi(String str) {
        char[] arr = str.trim().toCharArray();
        if (arr.length == 0) return 0;

        int sign = 1;
        long sum = 0;

        // 處理符號位
        if (arr[0] == '+' || arr[0] == '-' || (arr[0] >= '0' && arr[0] <= '9')) {
            if (arr[0] == '+') { arr[0] = '0'; sign = 1; }
            else if (arr[0] == '-') { arr[0] = '0'; sign = -1; }

            // 確定最高位
            int maxLevel = 0;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] >= '0' && arr[i] <= '9') maxLevel++;
                else break;
            }

            // 累加賦值
            int copy = maxLevel;
            for (int i = 0; i < maxLevel; i++) {
                sum += (arr[i] - '0') * Math.pow(10, --copy);
            }

            long val = sum * sign;
            if (val > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (val < Integer.MIN_VALUE) return Integer.MIN_VALUE;
            return (int) val;
        }
        return 0;
    }
}

四、關鍵易錯點

五、測試用例

"42"              → 42
"   -42"          → -42
"4193 with words" → 4193
"words and 987"   → 0
"-91283472332"    → -2147483648 (INT_MIN)
"3.14159"         → 3
""                → 0
"   "             → 0

六、優化方向

• 避免 Math.pow 浮點運算，改用整數乘法累加：sum = sum * 10 + (ch - '0')
• 單次遍歷邊判斷邊累加，無需兩次循環
• 使用 Character.isDigit(ch) 替代範圍判斷

七、相關鏈接

• LeetCode 官方：String to Integer (atoi)
• GitHub 測試代碼：Q008.java