[LeetCode解題攻略] 29. Divide Two Integers

題目描述

實作一個函數 divide(dividend, divisor)，計算兩個整數 dividend 和 divisor 的商，並返回其結果。

注意：不允許使用乘法、除法和取模運算子。

條件限制：

1. 如果結果超出 32 位整數範圍 [-2^31, 2^31 - 1]，則返回 2^31 - 1 或 -2^31。
2. 被除數 dividend和除數 divisor的範圍是 [-2^31, 2^31 - 1]，且除數不為 0。

範例 1：

輸入：

dividend = 10, divisor = 3

輸出：

3

解釋：10 除以 3，商為 3。

範例 2：

輸入：

dividend = 7, divisor = -3

輸出：

-2

解釋：7 除以 -3，商為 -2。

範例 3：

輸入：

dividend = -2147483648, divisor = -1

輸出：

2147483647

解釋：結果超出 32 位整數範圍，返回 2^31 - 1。

解題思路

要解決這道題，我們需要考慮以下幾個方面：

1. 符號處理：
2. • 商的符號由被除數和除數的符號決定，兩者異號則商為負數。
2. 模擬除法：
3. • 使用減法或位運算來模擬除法運算。
3. 邊界條件：
4. • 如果結果超出 32 位整數範圍，需返回邊界值。
   • 特殊情況如 dividend = -2^31, divisor = -1。

解法一：減法模擬

思路

我們可以用多次減法來模擬除法運算：

1. 不斷從被除數中減去除數，計算可以減去的次數。
2. 注意符號的處理。

詳細步驟

1. 紀錄結果的符號（正負）。
2. 取絕對值處理，簡化計算。
3. 使用一個迴圈不斷從被除數中減去除數，直到被除數小於除數。
4. 檢查結果是否超出 32 位整數範圍。

程式碼實現

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == -2**31 and divisor == -1:
            return 2**31 - 1  # 處理溢出情況

        # 確定結果的正負
        negative = (dividend < 0) ^ (divisor < 0)
        
        # 取絕對值進行計算
        dividend, divisor = abs(dividend), abs(divisor)
        
        result = 0
        while dividend >= divisor:
            dividend -= divisor
            result += 1
        
        # 恢復符號
        result = -result if negative else result
        
        return max(-2**31, min(result, 2**31 - 1))

時間與空間複雜度

• 時間複雜度：O(n)，其中 n=商值，因為每次減去一個除數。
• 空間複雜度：O(1)。

解法二：倍增減法

思路

用單次減法效率較低，尤其是被除數很大時。我們可以採用指數倍增的方式來加速：

1. 每次減去當前除數的倍數（例如 2⋅除數，4⋅除數 等），倍數每次翻倍。
2. 當倍增的除數超過被除數時，回退到上一個倍數。

詳細步驟

1. 紀錄符號並取絕對值。
2. 使用一個倍增方式快速逼近被除數。
3. 當倍數無法繼續增加時，將被除數減去當前倍增的值，並繼續迴圈。

程式碼實現

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == -2**31 and divisor == -1:
            return 2**31 - 1  # 處理溢出情況

        # 確定結果的正負
        negative = (dividend < 0) ^ (divisor < 0)
        
        # 取絕對值進行計算
        dividend, divisor = abs(dividend), abs(divisor)
        
        result = 0
        while dividend >= divisor:
            temp_divisor, multiple = divisor, 1
            while dividend >= (temp_divisor << 1):
                temp_divisor <<= 1
                multiple <<= 1
            
            dividend -= temp_divisor
            result += multiple
        
        # 恢復符號
        result = -result if negative else result
        
        return max(-2**31, min(result, 2**31 - 1))

時間與空間複雜度

• 時間複雜度：O(logn)，其中 n=被除數。倍增法每次將剩餘的被除數減小到一半。
• 空間複雜度：O(1)。

解法三：位運算（位移法）

思路

位運算的基本思路是利用位移操作來高效計算倍增。通過計算 divisor 向左移動幾位可以逼近 dividend，從而快速確定商的大小。

詳細步驟

1. 紀錄結果符號並取絕對值。
2. 將除數不斷向左移位，直到超過被除數。
3. 每次找到一個可以減去的倍數，更新被除數並累加到結果。

程式碼實現

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == -2**31 and divisor == -1:
            return 2**31 - 1  # 處理溢出情況

        # 確定結果的正負
        negative = (dividend < 0) ^ (divisor < 0)
        
        # 取絕對值
        dividend, divisor = abs(dividend), abs(divisor)
        
        result = 0
        for i in range(31, -1, -1):
            if (dividend >> i) >= divisor:
                result += 1 << i
                dividend -= divisor << i
        
        # 恢復符號
        result = -result if negative else result
        
        return max(-2**31, min(result, 2**31 - 1))

時間與空間複雜度

• 時間複雜度：O(log⁡n)，其中 n=被除數。最多進行 32 次迴圈操作。
• 空間複雜度：O(1)。

總結

• 暴力減法：簡單直觀，但效率較低。
• 倍增減法：用指數倍增來優化，效率更高。
• 位運算：利用位移操作，進一步優化時間複雜度。

倍增法與位移法是實際開發中常用的高效解法。如果你有任何疑問，歡迎留言討論！