当前位置：首页 > news >正文

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

news 2025/8/16 1:28:39

内容介绍

给你两个整数，被除数 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;}
}

思路详解

整体思路

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

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

详细步骤

处理特殊边界情况
- 当被除数为Integer.MIN_VALUE时，需要单独处理除数为1和-1的情况，因为直接计算会导致溢出。
- 当除数为Integer.MIN_VALUE时，只有当被除数也是Integer.MIN_VALUE时，商为1，否则为0。
处理除数为0的情况
- 当被除数为0时，直接返回0。
统一处理负数
- 将被除数和除数都转换为负数，这样只需考虑一种情况。同时记录转换次数，最后根据转换次数确定返回值的正负。
二分查找确定商的大小
- 初始化左边界为1，右边界为Integer.MAX_VALUE。
- 在二分查找过程中，计算中间值mid，并使用快速乘法判断mid * divisor是否大于等于dividend。
- 如果满足条件，更新答案ans，并将左边界更新为mid + 1；否则，将右边界更新为mid - 1。
快速乘法
- 由于不能使用除法，使用快速乘法来判断mid * divisor是否大于等于dividend。
- 通过位运算和加法模拟乘法操作，同时避免溢出。