[LeetCode解題攻略] 8. String to Integer (atoi)

這篇文章將介紹 LeetCode 題目 8. String to Integer (atoi)，這是一道實現 atoi 函數的題目。此題的核心在於如何解析字串中的數字並轉換成整數，同時需要考慮各種特殊情況和邊界條件。

題目概述

給定一個字串 s，將字串轉換為一個 32 位整數（類似於 C/C++ 中的 atoi 函數）。需要處理一些特殊情況，比如：

• 字串中是否有空格。
• 是否存在正負號。
• 數字是否會溢出。
• 非數字字符的截斷。

Input: s = "42"
Output: 42

Input: s = "-042"
Output: -42

Input: s = "0-1"
Output: 0

Input: s = "words and 987"
Output: 0

Input: s = "-91283472332"
Output: -2147483648

思路分析

此題的實現分為多個步驟，需要依次處理空格、正負號、數字轉換和溢出判斷。以下是詳細步驟：

1. 忽略開頭的空格：先去除字串左側的空格。
2. 處理符號：如果遇到 + 或 -，記錄符號（預設為正）。
3. 轉換數字：遍歷字串中的字符，遇到數字字符時進行數字組合；遇到非數字字符時停止。
4. 檢查溢出：轉換過程中保持數字在 32 位整數範圍內，如果溢出，返回邊界值。

解法：逐步解析字串

為了實現這個過程，可以使用字串操作來逐步處理每個字符。此方法會遍歷字串中的每一部分，並在不滿足條件時結束。

步驟

1. 去除開頭空格。
2. 判斷符號，將結果的符號設為 sign。
3. 遍歷數字字符並累積數字到 num。
4. 在累積數字時檢查是否溢出。
5. 返回結果，考慮符號和溢出。

實作 (Python)

def myAtoi(s):class Solution:
    def myAtoi(self, s: str) -> int:
        
        INT_MAX, INT_MIN = 2**31 - 1, -2**31
        i, n = 0, len(s)
        sign = 1
        num = 0

        # 去除開頭空格
        while i < n and s[i] == ' ':
            i += 1

        # 處理符號
        if i < n and s[i] in ('+', '-'):
            sign = -1 if s[i] == '-' else 1
            i += 1

        # 轉換數字字符
        while i < n and s[i].isdigit():
            digit = int(s[i])
            
            # 檢查溢出條件
            if num > (INT_MAX - digit) // 10:
                return INT_MAX if sign == 1 else INT_MIN
            
            num = num * 10 + digit
            i += 1

        return sign * num

複雜度分析

• 時間複雜度：O(n)，其中 n 是字串長度。我們最多遍歷一次字串。
• 空間複雜度：O(1)，只使用了固定的變數。

特殊情況和邊界條件

在解題時，需考慮以下情況：

1. 只有空格：直接返回 0。
2. 只有符號：無數字時返回 0。
3. 大於 32 位整數的數字：如 "-91283472332" 會返回 -2147483648。
4. 數字後有非數字字符：如 "4193 with words"，僅解析數字部分。

總結

這道題目是對字串解析和數字處理的綜合考驗。此解法按步驟進行處理，適用於各種邊界情況：

• 數字解析：按位解析，並處理溢出。
• 邊界條件：詳細考慮各種特殊情況和輸入格式。

希望這篇文章能幫助你掌握 String to Integer (atoi) 的解法！