力扣第二十九题——两数相除

内容介绍

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

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

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

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

示例 1:

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

示例 2:

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

提示：

• -231 <= dividend, divisor <= 231 - 1
• divisor != 0

完整代码

 class Solution {public int divide(int dividend, int divisor) {if (dividend == Integer.MIN_VALUE) {if (divisor == 1) {return Integer.MIN_VALUE;}if (divisor == -1) {return Integer.MAX_VALUE;}}if (divisor == Integer.MIN_VALUE) {return dividend == Integer.MIN_VALUE ? 1 : 0;}if (dividend == 0) {return 0;}boolean rev = false;if (dividend > 0) {dividend = -dividend;rev = !rev;}if (divisor > 0) {divisor = -divisor;rev = !rev;}int left = 1, right = Integer.MAX_VALUE, ans = 0;while (left <= right) {int mid = left + ((right - left) >> 1);boolean check = quickAdd(divisor, mid, dividend);if (check) {ans = mid;if (mid == Integer.MAX_VALUE) {break;}left = mid + 1;} else {right = mid - 1;}}return rev ? -ans : ans;}public boolean quickAdd(int y, int z, int x) {int result = 0, add = y;while (z != 0) {if ((z & 1) != 0) {if (result < x - add) {return false;}result += add;}if (z != 1) {if (add < x - add) {return false;}add += add;}z >>= 1;}return true;}
}

思路详解

整体思路

该代码实现了一个整数除法功能，主要解决以下问题：

1. 处理特殊边界情况，如被除数或除数为整数最小值。
2. 处理除数为0的情况。
3. 通过二分查找确定商的大小。
4. 使用快速乘法判断二分查找中的中间值是否满足条件。

详细步骤

1. 处理特殊边界情况

   • 当被除数为Integer.MIN_VALUE时，需要单独处理除数为1和-1的情况，因为直接计算会导致溢出。
   • 当除数为Integer.MIN_VALUE时，只有当被除数也是Integer.MIN_VALUE时，商为1，否则为0。

2. 处理除数为0的情况

   • 当被除数为0时，直接返回0。

3. 统一处理负数

   • 将被除数和除数都转换为负数，这样只需考虑一种情况。同时记录转换次数，最后根据转换次数确定返回值的正负。

4. 二分查找确定商的大小

   • 初始化左边界为1，右边界为Integer.MAX_VALUE。
   • 在二分查找过程中，计算中间值mid，并使用快速乘法判断mid * divisor是否大于等于dividend。
   • 如果满足条件，更新答案ans，并将左边界更新为mid + 1；否则，将右边界更新为mid - 1。

5. 快速乘法

   • 由于不能使用除法，使用快速乘法来判断mid * divisor是否大于等于dividend。
   • 通过位运算和加法模拟乘法操作，同时避免溢出。

代码注释说明

• rev：记录被除数和除数转换为负数的次数，用于最后确定返回值的正负。
• quickAdd：快速乘法函数，用于判断y * z是否大于等于x。
• left、right、ans：二分查找的左边界、右边界和当前答案。
• mid：二分查找的中间值。
• check：用于判断mid * divisor是否大于等于dividend。

知识点精炼

特殊情况处理

1. 整数最小值：处理Integer.MIN_VALUE作为被除数或除数的情况，防止溢出。
2. 除数为0：明确除数为0时，结果为0。

负数统一处理

1. 符号转换：将被除数和除数统一转换为负数，简化问题处理。
2. 符号记录：使用布尔变量记录被除数和除数的符号转换次数，以确定最终结果的符号。

二分查找

1. 查找范围：初始化左边界为1，右边界为Integer.MAX_VALUE。
2. 中间值计算：使用位运算计算中间值，避免溢出。
3. 条件判断：通过快速乘法判断中间值是否满足条件。

快速乘法

1. 位运算：利用位运算模拟乘法操作，避免直接使用乘法导致溢出。
2. 加法替代：通过加法累加结果，判断是否满足条件。

防溢出

1. 边界检查：在计算过程中，确保不发生溢出。
2. 无除法：全程不使用除法操作，避免因除法导致的精度问题。