題目描述
實作一個函數 divide(dividend, divisor)，計算兩個整數 dividend 和 divisor 的商，並返回其結果。
- 如果結果超出 32 位整數範圍 [-2^31, 2^31 - 1]，則返回 2^31 - 1 或 -2^31。
- 被除數 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。
解題思路
要解決這道題，我們需要考慮以下幾個方面：
- 符號處理：
- 商的符號由被除數和除數的符號決定，兩者異號則商為負數。
- 模擬除法：
- 使用減法或位運算來模擬除法運算。
- 邊界條件：
- 如果結果超出 32 位整數範圍，需返回邊界值。
- 特殊情況如 dividend = -2^31, divisor = -1。
解法一：減法模擬
思路
我們可以用多次減法來模擬除法運算：
- 不斷從被除數中減去除數，計算可以減去的次數。
- 注意符號的處理。
詳細步驟
- 紀錄結果的符號（正負）。
- 取絕對值處理，簡化計算。
- 使用一個迴圈不斷從被除數中減去除數，直到被除數小於除數。
- 檢查結果是否超出 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)。
解法二：倍增減法
思路
用單次減法效率較低，尤其是被除數很大時。我們可以採用指數倍增的方式來加速：
- 每次減去當前除數的倍數（例如 2⋅除數，4⋅除數 等），倍數每次翻倍。
- 當倍增的除數超過被除數時，回退到上一個倍數。
詳細步驟
- 紀錄符號並取絕對值。
- 使用一個倍增方式快速逼近被除數。
- 當倍數無法繼續增加時，將被除數減去當前倍增的值，並繼續迴圈。
程式碼實現
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，從而快速確定商的大小。
詳細步驟
- 紀錄結果符號並取絕對值。
- 將除數不斷向左移位，直到超過被除數。
- 每次找到一個可以減去的倍數，更新被除數並累加到結果。
程式碼實現
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(logn)，其中 n=被除數。最多進行 32 次迴圈操作。
- 空間複雜度：O(1)。
總結
- 暴力減法：簡單直觀，但效率較低。
- 倍增減法：用指數倍增來優化，效率更高。
- 位運算：利用位移操作，進一步優化時間複雜度。
倍增法與位移法是實際開發中常用的高效解法。如果你有任何疑問，歡迎留言討論！