LeetCode【0029】两数相除

1 中文题目

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的 商 。

注意：假设环境只能存储 32 位 有符号整数，其数值范围是 $[-2^{31},2^{31}-1]$ 。本题中，如果商 严格大于 $2^{31}-1$ ，则返回 $2^{31}-1$ ；如果商 严格小于 $-2^{31}$ ，则返回 $-2^{31}$ 。

示例：

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

提示：

• $-2^{31}\le dividend,divisor\le 2^{31}-1$
• divisor != 0

---

2 求解方法：位运算

2.1 方法思路

方法核心

• 使用位运算实现除法
• 通过倍增法快速逼近商

实现步骤

(1)符号处理：

• 使用异或确定结果符号
• 将被除数和除数转为正数处理

(2)快速逼近：

• 使用位运算倍增除数
• 通过减法求得商

(3)结果处理：

• 应用正确的符号
• 处理溢出情况

方法示例

输入：dividend = 10, divisor = 3

过程演示：
1. 初始状态：
   dividend = 10, divisor = 3
   result = 0

2. 第一次循环：
   curr_divisor = 3
   multiple = 1
   位运算后：curr_divisor = 6, multiple = 2
   dividend = 10 - 6 = 4
   result = 2

3. 第二次循环：
   curr_divisor = 3
   multiple = 1
   dividend = 4 - 3 = 1
   result = 3

4. 结束循环：
   dividend < divisor

返回：3

2.2 Python代码

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 处理特殊情况
        INT_MIN, INT_MAX = -2**31, 2**31 - 1
        
        # 处理除数为0的情况
        if divisor == 0:
            return INT_MAX
        
        # 处理溢出情况
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX
            
        # 记录结果的符号
        # 异或运算：相同为0，不同为1
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        
        # 将被除数和除数都转为正数
        dividend = abs(dividend)
        divisor = abs(divisor)
        
        # 结果
        result = 0
        
        # 使用位运算优化
        while dividend >= divisor:
            # 当前除数
            curr_divisor = divisor
            # 当前商（从1开始）
            multiple = 1
            
            # 快速逼近
            # dividend >= curr_divisor << 1 确保不会溢出
            while dividend >= (curr_divisor << 1) and (curr_divisor << 1) > 0:
                curr_divisor <<= 1  # 除数左移一位（乘2）
                multiple <<= 1      # 商左移一位（乘2）
            
            # 减去当前最大的可能值
            dividend -= curr_divisor
            # 添加到结果中
            result += multiple
        
        # 应用符号并处理溢出
        result = -result if sign == -1 else result
        
        # 确保结果在32位整数范围内
        if result > INT_MAX:
            return INT_MAX
        if result < INT_MIN:
            return INT_MIN
            
        return result

2.3 复杂度分析

• 时间复杂度：O(log n)，n是被除数的大小
  • 每次循环被除数至少减半
• 空间复杂度：O(1)
  • 只使用常数级别的额外空间

---

3 题目总结

题目难度：中等
数据类型：整数
应用算法：位运算

原文地址：https://blog.csdn.net/qq_32882309/article/details/143737768

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！