从“倒水问题”到“裴蜀定理”辗转相除法在面试算法题中的实战应用在技术面试中算法题往往看似孤立实则暗藏数学原理的巧妙连接。当你面对用5L和7L杯子量出3L水这类问题时是否意识到它背后隐藏着2300年前的数学智慧这道经典面试题不仅是逻辑思维的试金石更是打开数论世界的一把钥匙——它直接关联着欧几里得算法与裴蜀定理的核心思想。1. 倒水问题的数学本质想象你面前有两个容量分别为A和B的杯子A≠B如何通过装满、倒空和互相倒水的操作得到指定容量C的水这个看似简单的游戏实则是可计算性理论的微型实验室。关键观察在任何操作步骤中杯子中的水量总是A和B的线性组合。用数学语言表达就是# 水量变化的数学表达 current_water x*A y*B # x,y为整数这个发现将实际问题转化为数学方程是否存在整数x,y使得Ax By C成立操作合法性验证水量不能为负x,y可以负表示倒空操作水量不能超过杯子容量最终C必须出现在某个杯子中示例推演5L和7L杯子得到3L水填满7L杯(0,7) → 0×5 1×7 77L倒入5L(5,2) → 1×5 1×7 12倒空5L杯(0,2) → 0×5 1×7 77L倒入5L(2,0) → 1×5 (-1)×7 -2填满7L杯(2,7) → 1×5 2×7 197L倒入5L至满(5,4) → 2×5 2×7 24此时7L杯中有4L重复操作可得3L2. 辗转相除法的实战变形欧几里得算法在面试中常以三种形式出现递归版最简实现def gcd(a, b): return a if b 0 else gcd(b, a % b)迭代版空间效率更优def gcd_iter(a, b): while b: a, b b, a % b return a二进制优化版适合大数运算def binary_gcd(a, b): if a b: return a if a 0: return b if b 0: return a # 移除公共的2因子 shift 0 while ((a | b) 1) 0: a 1 b 1 shift 1 # 确保a是奇数 while (a 1) 0: a 1 while b ! 0: # 确保b是奇数 while (b 1) 0: b 1 # 现在a,b都是奇数 if a b: a, b b, a b - a return a shift性能对比方法类型时间复杂度空间复杂度适用场景递归版O(log min(a,b))O(log min(a,b))代码简洁迭代版O(log min(a,b))O(1)默认选择二进制版O(log min(a,b))O(1)大数运算3. 裴蜀定理的算法映射裴蜀定理指出对于整数a,b存在整数x,y使得ax by gcd(a,b)。这在算法实现中表现为扩展欧几里得算法def extended_gcd(a, b): if b 0: return (a, 1, 0) else: g, x, y extended_gcd(b, a % b) return (g, y, x - (a // b) * y)应用案例模逆元计算求解ax ≡ 1 mod m线性同余方程解ax ≡ b mod m组合数学证明某些计数问题的可解性面试变体题给定硬币面值能否凑出指定金额硬币问题判断两点之间是否存在整数路径射线投射算法字符串周期检测KMP算法的数学基础4. 算法思想的跨界应用辗转相除法的思想可迁移到多个领域链表环检测快慢指针法def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False数学原理 设环长为L快指针速度是慢指针的k倍则相遇时k×t ≡ t mod L ⇒ (k-1)×t ≡ 0 mod L当k2时最小tL/ gcd(L,1)L数组轮转问题def rotate(nums, k): n len(nums) k % n count gcd(k, n) for i in range(count): current i prev nums[i] while True: next_idx (current k) % n nums[next_idx], prev prev, nums[next_idx] current next_idx if current i: break操作步骤计算实际旋转步数k k mod n确定循环次数count gcd(n, k)每个循环处理n/count个元素字符串旋转匹配def is_rotation(s1, s2): return len(s1) len(s2) and s2 in s1 s1这个看似简单的解法其效率优化的核心仍与最大公约数计算相关。