?LeetCode刷題實戰(zhàn)29：兩數(shù)相除

今天和大家聊的問題叫做?兩數(shù)相除，我們先來看題面：

https://leetcode-cn.com/problems/divide-two-integers/

給定兩個整數(shù)，被除數(shù)和除數(shù)，要求在不使用除法的情況下計算出兩數(shù)的商

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

樣例 1:

Input: dividend = 10, divisor = 3
Output: 3

樣例 2:

Input: dividend = 7, divisor = -3
Output: -2

注意:

• 除數(shù)和被除數(shù)都在32位int的范圍內(nèi)

• 除數(shù)不為0

• 對于超界的情況返回

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [?, ??? 1]. For the purpose of this problem, assume that your function returns??? 1 when the division result overflows.

題解

暴力

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 判斷是否同號
        flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
        ret = 0
        # 全部賦值為正
        dividend, divisor = abs(dividend), abs(divisor)
        
        start = 0
        # 模擬除法
        while start + divisor <= dividend:
            start += divisor
            ret += 1
            
        # 防止越界，注意只有正數(shù)才有可能越界
        return min(ret, (1 << 31) - 1) if flag else -ret

二進制優(yōu)化

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 前面處理和之前一樣
        flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
        ret = 0
        dividend, divisor = abs(dividend), abs(divisor)
        
        # 預處理二進制數(shù)組
        binary = [0 for _ in range(33)]
        # 第0位即2的零次方乘上除數(shù)，所以就是除數(shù)本身
        binary[0] = divisor
        for i in range(1, 33):
            # 后面每一位是前面一位的兩倍，因為二進制
            # << 是位運算左移操作，等價于*2，但是速度更快
            binary[i] = binary[i-1] << 1
            
        for i in range(32, -1, -1):
            if binary[i] <= dividend:
                dividend -= binary[i]
                # 答案加上2^i
                ret += (1 << i)
        return min(ret, (1 << 31) - 1) if flag else -ret