LeetCode LCR 001. 两数相除
题目描述
题意分析
给定两个 32 位有符号整数
a、b，求整数商，舍弃小数部分并向零截断。除数保证不为零，计算中不能使用乘法、除法和取余运算符，也不能依赖比 32 位更宽的整数范围。商溢出时返回最大 32 位整数，唯一需要截断的组合是最小负数除以负一。最小负数的绝对值无法作为正
int保存，因此中间过程不能一律先转为正数。
解法：负数域倍增减法
核心思路
[!blue]
逐次减去除数虽然可以得到商，但商很大时需要过多循环。改为每轮先把除数不断翻倍，找到剩余量能够容纳的最大二进制倍数，再一次减去它，并把对应倍数加到商中。
本实现用负数保存被除数余量
a与除数b，用非负的answer保存已经累计的商的绝对值。正数取负总能在 32 位范围内表示，最小负数也无需转换；原结果是否同号在转换前记录，最后再应用符号。外层的
a <= b表示余量的绝对值还不小于除数。内层从x = b、cnt = 1开始，x代表本轮要减去的负倍数，cnt代表它含有多少份原除数。只要翻倍后仍能被余量容纳，就同时左移x与cnt，直到不能继续。左移前要先检查
x >= (Integer.MIN_VALUE >> 1)，保证翻倍仍在负数范围内，再判断a <= (x << 1)。顺序不能反，溢出后的倍数已经无法正确参与比较。选定后执行answer += cnt、a -= x，后者把负余量向零推进。始终有“原被除数的绝对值 = 已累计商对应的除数总量 + 当前余量绝对值”。最大可减倍数至少消耗一半当前余量，下一轮继续处理更小部分；当余量绝对值小于除数时结束，舍去它正好得到向零截断的商。
由于商按正数累计，需要提前处理
b == 1，直接返回a，并截断最小负数除以负一的溢出组合。这两处处理后，其余商的绝对值都能放入正int，cnt和answer的累计才安全；这与全程累计负商的实现有所不同。
解题步骤
- 除数为一时返回被除数；最小负数除以负一时返回最大正整数。
- 记录两操作数是否同号，再把正操作数取负，令
answer = 0。- 余量绝对值仍足够时，从一份除数开始，先验证移位安全，再不断翻倍寻找本轮最大可减倍数。
- 把倍数计入正商累计量，从负余量中减去该负倍数。
- 余量不足一份除数时结束，根据原符号返回
answer或-answer。
代码实现
class Solution {
public int divide(int a, int b) {
// 除数为 1 时商就是 a 本身，提前返回可以避开 a = MIN_VALUE 的溢出。
if (b == 1) {
return a;
}
// 唯一超出 int 上界的组合，按题意截断。
if (a == Integer.MIN_VALUE && b == -1) {
return Integer.MAX_VALUE;
}
boolean sign = (a > 0 && b > 0) || (a < 0 && b < 0);
// 统一到负数域：负半轴容得下正半轴的全部取值，取负不会溢出。
a = a > 0 ? -a : a;
b = b > 0 ? -b : b;
int answer = 0;
while (a <= b) {
int x = b;
int cnt = 1;
// 先卡住移位溢出，再判断翻倍后是否仍不超过剩余的被除数。
while (x >= (Integer.MIN_VALUE >> 1) && a <= (x << 1)) {
x <<= 1;
cnt <<= 1;
}
answer += cnt;
a -= x;
}
return sign ? answer : -answer;
}
}
import (
"math"
)
func divide(a int, b int) int {
if b == 1 {
return a
}
if a == math.MinInt32 && b == -1 {
return math.MaxInt32
}
sign := (a > 0 && b > 0) || (a < 0 && b < 0)
if a > 0 {
a = -a
}
if b > 0 {
b = -b
}
answer := 0
for a <= b {
x := b
cnt := 1
for x >= (math.MinInt32>>1) && a <= (x<<1) {
x <<= 1
cnt <<= 1
}
answer += cnt
a -= x
}
if sign {
return answer
}
return -answer
}
复杂度分析
- 时间复杂度：设
W为输入整数位宽，最坏 $O(W^2)$。外层每轮至少将余量绝对值减半，至多W轮；内层每轮都从原除数重新倍增，至多再做W次。题目固定位宽为 32，一般也可用输入数值写作 $O(1 + \log^2(\lvert a\rvert + 1))$。- 空间复杂度：$O(1)$，只维护符号、余量、商和本轮倍数等固定变量。
关键点总结
[!green]
- 负数域保存余量，正数累计商，两类变量的范围问题要分别处理。
x和cnt同步翻倍，分别表示可减数值与要增加的商。- 负数越小绝对值越大，因此
a <= x才表示余量足够。- 必须先验证翻倍不溢出，再判断这个倍数是否能减去。
- 内层每轮重新倍增，不能只看外层次数就把这份实现写成单次对数时间。
易错点总结
[!yellow]
- 先对最小负数取正的绝对值会溢出，应将正操作数转负。
- 本实现的
answer是正的绝对值累计量，不能删除为它保障范围的两个入口处理。- 内层先移位后检查范围，可能已经把正确倍数变成错误值。
- 只增加商却忘记扣除余量，会重复计算同一部分并无法结束。
- 向零截断只舍弃不足一份除数的余量，不是对负数向下取整。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 50. Pow(x, n) | 中等 | 同样按二进制拆分次数并成倍处理，原题通过平方加速幂，本题通过倍增除数确定商。 |