Kimi 进阶 LeetCode 29. 两数相除 Rust实现

LeetCode 29. 两数相除 - Rust 实现

核心思路

这道题要求不使用乘法、除法和取模运算符来实现整数除法。标准解法是倍增法（位移模拟）：

1. 处理符号：记录结果的符号，将两个数转为同号处理
2. 倍增逼近：将除数不断左移（×2），找到不超过被除数的最大值
3. 累加商值：对应左移的位数，累加1 << n到结果
4. 处理余数：用被除数减去已逼近的值，重复上述过程
5. 溢出处理：-2^31 / -1结果超出i32范围，需返回i32::MAX

implSolution{pubfndivide(dividend:i32,divisor:i32)->i32{// 处理溢出唯一情况：-2^31 / -1 = 2^31，超出 i32 范围ifdividend==i32::MIN&&divisor==-1{returni32::MAX;}// 判断结果符号：异号为负letnegative=(dividend>0)!=(divisor>0);// 转为 i64 并取绝对值，避免溢出（i32::MIN 的绝对值会溢出）letmutdvd=(dividendasi64).abs();letmutdvs=(divisorasi64).abs();letmutresult:i64=0;whiledvd>=dvs{letmuttemp=dvs;letmutmultiple=1_i64;// 倍增：除数不断左移（×2），直到超过被除数// temp << 1 等价于 temp * 2，但使用位移更直观whiledvd>=(temp<<1){temp<<=1;multiple<<=1;}// 减去已逼近的值，累加对应商dvd-=temp;result+=multiple;}// 根据符号返回结果ifnegative{-(resultasi32)}else{resultasi32}}}

复杂度分析

指标 复杂度 说明
时间 O(log²N) 外层循环 O(log N) 次，内层倍增 O(log N) 次
空间 O(1) 仅使用常数个变量

关键点说明

1. 为什么用i64？

   i32::MIN的绝对值是2^31，超出i32::MAX (2^31-1)，会溢出。转为i64后安全处理。

2. 为什么temp << 1不会溢出？

   循环条件dvd >= (temp << 1)保证了temp始终不超过dvd，而dvd最大为|i32::MIN| = 2^31，在i64范围内完全安全。

3. 位移与乘法的关系

   temp << 1等价于temp * 2，multiple << 1等价于multiple * 2。题目禁止乘法，但允许位移（位运算），这是标准解法。

4. 符号处理技巧

   (dividend > 0) != (divisor > 0)比分别判断四种情况更简洁：两数符号不同则为true（结果为负）。