leetcode29. 两数相除-medium

news/2025/3/18 21:45:18/

1 题目：两数相除

官方标定难度：中

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

2 solution

这道题如果完全按照题目要求还是挺麻烦的，因为计算过程中很容易就溢出了，所以要额外增加很多判断。
总体思路，二分法：
1 用移位运算代替除以 2 的运算
2 要保证计算过程中溢出，而不是判断结果
3 注意不是所有的负数都能变成正数而不溢出

代码

class Solution {
public:
int divide(int a, int b, int c) { // a > b * c// a, b < 0,  c > 0while (c) {if (a > b) return 1; // a > b * c;if (c & 1) {a -= b;if (a > 0) return 1;}if (c > 1 && b < -(1 << 30)) return 1; // a > b + cb <<= 1;c >>= 1;}return a;
}int divide(int dividend, int divisor) {// 可能会溢出的情况if (dividend == INT32_MIN && divisor == -1) return INT32_MAX;if (divisor == 1) return dividend;// 先变成负数相除int symbol = 1;if (dividend > 0) {dividend = -dividend;symbol = -symbol;}if (divisor > 0) {divisor = -divisor;symbol = -symbol;}// 二分法int left = 0, right = INT32_MAX;while (left <= right) {int mid = left + ((right - left) >> 1); //  a > b * cint x = divide(dividend, divisor, mid);if (x == 0) return symbol * mid;else if (x > 0) right = mid - 1;else left = mid + 1;}return symbol * right;
}
};