Python世界：力扣29题两数相除算法实践

任务背景

本问题来自于力扣29题，在做完大数相乘后，顺带也看下两数相除。

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

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

注意提示：目的就是提醒越界问题：-2^31/-1=2&31，超过了整数表达范围。

实现思路

模拟思路

• 问题核心：只用减法，拼凑，直到小于除数
• 简化问题：不考虑正负，只考虑纯正数

编码实现

功能函数：

def get_sign(num: int) -> int:sign_num = 1if num < 0:sign_num = -1return sign_numclass Solution:def divide(self, dividend: int, divisor: int) -> int:# 注意处理两者的输入边界，负号取绝对值存在溢出的问题。dividendabs_dvd = abs(dividend)abs_dvs = abs(divisor)sign_dvd = get_sign(dividend)sign_dvs = get_sign(divisor)# corner caseif dividend == 0 or abs_dvd < abs_dvs:return 0if divisor == 1:return dividendif (divisor == -1):if (dividend != -2**31):return -dividendelse:return 2**31-1# 原始方法，耗时过大res = 0while (abs_dvd >= abs_dvs):abs_dvd -= abs_dvsres += 1if sign_dvd != sign_dvs:res *= -1return res

针对27-31行效率问题，倍增加法，加快收敛：

        # 优化版本res = 0sum_rm = 0 # 记录被减去的总数while (abs_dvd >= abs_dvs + sum_rm): # 固定步长，移动sum_rmbig_step = abs_dvsbig_cnt = 1while (abs_dvd >= big_step + big_step + sum_rm):big_step += big_step # 移动步长big_cnt += big_cnt # 倍数步长sum_rm += big_step # 计入累积步长res += big_cnt # 计入累计步数

测试套编写：

# 导入单元测试
import unittest# 编写测试套
class TestSol(unittest.TestCase):def test_bound1(self):num1 = 7num2 = 1ret = 7sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_bound2(self):num1 = 7num2 = 7ret = 1sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_bound3(self):num1 = 2147483647num2 = -1ret = -2147483647sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_bound4(self):num1 = -2147483648num2 = -2147483648ret = 1sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_bound5(self):num1 = -2147483648num2 = -2ret = 1073741824sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_bound6(self):num1 = 2147483647num2 = 2ret = 1073741823sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_special1(self): # 负数极大值场景num1 = -2147483648num2 = -1ret = 2147483647sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_special2(self):num1 = -2147483648num2 = 1ret = -2147483648sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_common_case1(self):num1 = 7num2 = -3ret = -2sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_common_case2(self):num1 = 10num2 = -3ret = -3sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)def test_common_case3(self):num1 = 10num2 = 3ret = 3sol = Solution()self.assertEqual(sol.divide(num1, num2), ret)

主调逻辑：

# 含测试套版本主调
if __name__ == '__main__':print('start!')unittest.main() # 启动单元测试print('done!')

本文小结

除法运算本质是减法，从理解原理到真正实现还是有距离，建议初步理解后，不参考任何代码，完全自己复现一遍，体会更深。

• 先完成粗略的（核心的）
• 再处理corner case
• 再优化提效

参考资料

1. LeetCode题目P29，两数相除
2. P29题解参考