【LeetCode 题解】算法:29.两数相除

在算法的世界里，常常会出现一些打破常规、挑战思维的题目。LeetCode 第 29 题 “两数相除” 便是其中之一。这道题不仅要求我们在不能使用乘法、除法和取余运算的前提下实现两数相除，还需要处理 32 位有符号整数的溢出问题，对编程者的逻辑思维和代码实现能力提出了较高要求。接下来，就让我们一起剖析这道题的解题思路和实现方法。​

一、深入剖析题目要求​

1. 运算限制​

题目明确禁止使用乘法、除法和取余运算。这意味着我们需要另辟蹊径，借助其他数学运算和编程技巧来实现相除的功能。​

2. 结果截断​

整数除法需向零截断，即舍去小数部分。比如，8.345截断为8，-2.7335截断为-2。​

3. 溢出处理​

由于环境只能存储 32 位有符号整数，范围是[-2^31, 2^31 - 1]。因此，计算结果若超出这个范围，就需要返回相应的边界值。​

二、解题思路探索​

1. 朴素减法方案​

最容易想到的方法是反复从被除数中减去除数，通过统计相减的次数得到商。以10 / 3为例，计算过程如下：​

10 - 3 = 7 (第1次)​

7 - 3 = 4 (第2次)​

4 - 3 = 1 (第3次)​

​

一共减了 3 次，所以商为 3。然而，当被除数非常大，除数非常小时，这种方法的时间复杂度会变得很高，效率极其低下。​

2. 倍增优化方案​

为了提升效率，我们可以采用倍增的思想。每次尝试减去除数的倍数，而不是固定减去一个除数。例如，在计算10 / 3时：​

首先，我们判断10是否大于3 * 2（即6），若大于，就减去6，此时相当于一次减去了 2 个除数。然后，再从剩余的10 - 6 = 4中继续计算。通过这种方式，能够大幅减少运算次数。​

3. 位运算加速方案​

计算机在处理二进制数据时，位运算的速度非常快。在二进制中，左移一位相当于乘以 2，右移一位相当于除以 2。利用这一特性，我们可以通过左移除数，快速找到接近被除数的数值，再进行减法操作，从而进一步提升计算效率。​

三、Java 代码实现​

​

public class DivideTwoIntegers {​public int divide(int dividend, int divisor) {​// 处理除数为零的情况​if (divisor == 0) {​throw new IllegalArgumentException("除数不能为零");​}​​// 判断结果的正负​boolean isNegative = (dividend < 0) ^ (divisor < 0);​​// 将被除数和除数转换为负数，避免正数溢出问题​long dividendLong = convertToNegative(dividend);​long divisorLong = convertToNegative(divisor);​​// 执行核心计算​int result = calculateQuotient(dividendLong, divisorLong);​​// 根据结果的正负返回相应值，并处理溢出​return isNegative? handleNegativeResult(result) : handlePositiveResult(result);​}​​private long convertToNegative(int num) {​return num == Integer.MIN_VALUE? num : -Math.abs(num);​}​​private int calculateQuotient(long dividendLong, long divisorLong) {​int result = 0;​while (dividendLong <= divisorLong) {​long temp = divisorLong;​int multiple = 1;​while (dividendLong <= temp << 1) {​temp <<= 1;​multiple <<= 1;​}​dividendLong -= temp;​result += multiple;​}​return result;​}​​private int handleNegativeResult(int result) {​return result < Integer.MIN_VALUE? Integer.MIN_VALUE : -result;​}​​private int handlePositiveResult(int result) {​return result > Integer.MAX_VALUE? Integer.MAX_VALUE : result;​}​}​​

四、代码详细解析​

1. divide方法​

该方法是整个程序的入口，负责协调各个部分的逻辑。首先，检查除数是否为零，若为零则抛出异常。接着，通过异或运算判断结果的正负。为了避免在处理正数时因Integer.MIN_VALUE取相反数导致溢出，将被除数和除数转换为负数。之后，调用calculateQuotient方法进行核心计算，最后根据结果的正负进行相应处理，确保结果在 32 位有符号整数的范围内。​

2. convertToNegative方法​

此方法将传入的整数转换为负数。如果传入的数是Integer.MIN_VALUE，由于其取相反数会溢出，所以直接返回该值。否则，通过-Math.abs(num)将其转换为负数。​

3. calculateQuotient方法​

这是实现相除运算的核心方法。通过外层while循环，不断从被除数中减去合适倍数的除数。内层while循环利用位运算<<找到最大的可以减去的倍数，每次减去相应倍数的除数后，将倍数累加到结果中。​

4. handleNegativeResult和handlePositiveResult方法​

这两个方法分别处理计算结果为负数和正数的情况，确保结果不会超出 32 位有符号整数的取值范围。​

五、代码测试​

为了验证代码的正确性，我们可以编写测试用例：​

​

public class Main {​public static void main(String[] args) {​DivideTwoIntegers solution = new DivideTwoIntegers();​System.out.println(solution.divide(10, 3)); // 输出: 3​System.out.println(solution.divide(7, -3)); // 输出: -2​System.out.println(solution.divide(0, 5)); // 可以正常处理被除数为零的情况，输出: 0​System.out.println(solution.divide(1, 1)); // 常规正数测试，输出: 1​System.out.println(solution.divide(-1, -1)); // 常规负数测试，输出: 1​}​}​​

六、复杂度分析​

1. 时间复杂度​

在最坏情况下，时间复杂度为O(log n)，其中n为被除数的绝对值。因为每次通过位运算<<找到可以减去的最大倍数，相当于将问题规模减半。​

2. 空间复杂度​

空间复杂度为O(1)，在计算过程中，只使用了有限的额外空间，没有随着输入规模的增加而增加。

 

感谢各位的阅读，后续将持续给大家讲解力扣中的算法题和数据库题，如果觉得这篇内容对你有帮助，别忘了点赞和关注，后续还有更多精彩的算法解析与你分享！