LeetCode 8. String to Integer (atoi) - 完整邊界情況處理

問題描述

實現 atoi：將字符串轉換為 32 位有符號整數。需處理前導空格、可選正負號、數字字符、非數字截停、溢出鉗制 (INT_MIN=-2³¹, INT_MAX=2³¹-1)。

標準庫 atoi 行為參考

• 跳過前導空白字符 (isspace)。
• 讀取可選 + 或 -。
• 讀取盡可能多的數字字符構成整數。
• 後續非數字字符忽略。
• 無有效數字返回 0。
• 溢出行為未定義 (本題要求鉗制)。

關鍵邊界情況

Java 參考實現

public class Solution {
    public int myAtoi(String str) {
        if (str == null) return 0;
        str = str.trim(); // 去除首尾空格
        if (str.isEmpty()) return 0;

        int sign = 1, i = 0;
        if (str.charAt(0) == '-') { sign = -1; i++; }
        else if (str.charAt(0) == '+') { i++; }

        long result = 0;
        for (; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c < '0' || c > '9') break;
            result = result * 10 + (c - '0');
            // 溢出檢查
            if (sign == 1 && result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (sign == -1 && -result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }
        return sign * (int)result;
    }
}

C++ 參考實現 (更貼近底層)

class Solution {
public:
    int myAtoi(string str) {
        int i = 0, n = str.size();
        // 1. 跳過空格
        while (i < n && str[i] == ' ') i++;
        if (i == n) return 0;

        // 2. 符號
        int sign = 1;
        if (str[i] == '-') { sign = -1; i++; }
        else if (str[i] == '+') { i++; }

        // 3. 數字累積
        long long result = 0;
        while (i < n && isdigit(str[i])) {
            result = result * 10 + (str[i] - '0');
            // 4. 溢出鉗制
            if (sign == 1 && result > INT_MAX) return INT_MAX;
            if (sign == -1 && -result < INT_MIN) return INT_MIN;
            i++;
        }
        return sign * (int)result;
    }
};

核心技巧總結

1. 用 long long 累積，避免中間過程溢出導致未定義行為。
2. 逐位檢查溢出，而非最後檢查，能精確鉗制。
3. isdigit 判斷數字字符，標準庫函數更安全。
4. trim 只去首尾空格，中間空格視為非數字截停 (題目要求)。

複雜度

• 時間 O(n)，n 為字符串長度。
• 空間 O(1)。