1. 项目概述从一道题看“归零”的算法艺术最近在刷LeetCode的时候碰到了第2169题“得到 0 的操作数”。乍一看标题你可能会有点懵操作数得到0这到底是要干什么其实这是一道非常典型的模拟题它不涉及高深的动态规划或者复杂的图论核心考察的是你对问题逻辑的理解、代码实现的严谨性以及那么一点点的数学直觉。简单来说题目给了你两个正整数num1和num2你需要反复执行一个操作用较大的数减去较小的数直到其中一个数变成0。题目要求你返回执行这个操作的次数。举个例子如果num1 10,num2 10那么一步操作后两个数都变成了0操作次数就是1。如果num1 2,num2 3过程是(3,2) - (1,2) - (1,1) - (0,1)操作次数是3。这道题适合所有正在学习编程基础、想要巩固循环和条件判断的同学也适合想寻找清晰逻辑训练的老手。它就像算法世界里的“磨刀石”看似简单但要想写出高效、优雅的解法并透彻理解其背后的数学原理还真得花点心思。接下来我就带你彻底拆解这道题从最直接的暴力模拟到优化思路再到其背后隐藏的“欧几里得算法”影子让你不仅AC这道题更能收获一类问题的解决心法。2. 问题核心与思路拆解2.1 题意解析与输入输出规范题目描述非常清晰给定两个正整数num1和num2。在每一步操作中你需要比较当前的两个数然后用较大的数减去较小的数。注意操作完成后被减的数较大的数更新为差值而较小的数保持不变。重复这个过程直到两个数中至少有一个变为 0。你需要计算并返回总共执行的操作次数。这里有几个关键点需要明确这些往往是第一次做题时容易忽略的坑点操作对象每次操作只改变两个数中的一个即较大的那个数。较小的数在本轮操作中不变。终止条件是“直到两个数中至少有一个变为 0”。这意味着当num1或num2中任意一个为0时循环立即停止。不需要两个同时为0虽然在某些情况下会同时为0。操作计数每一次“比较-相减”算作一次操作无论差值是多少。输入范围题目明确是正整数所以不需要处理0或负数的情况这简化了边界条件。输入输出示例输入num1 10, num2 10 输出1 解释第一轮操作后两个数都变为0。输入num1 2, num2 3 输出3 解释(3,2)-(1,2)-(1,1)-(0,1)理解题意后最直观的想法就是模拟这个过程。这也是面试官常常期望候选人首先给出的解法清晰、正确、易于理解和沟通。2.2 模拟法最直接的实现路径模拟法完全按照题目描述的步骤来写代码思路直白是验证我们对问题理解是否正确的最佳方式。我们可以用一个while循环只要两个数都不为0就持续执行操作。算法步骤初始化操作计数器count 0。使用while循环条件为num1 0 num2 0即两个数都大于0。在循环体内 a. 比较num1和num2。 b. 如果num1 num2则num1 num1 - num2。 c. 否则num2 num2 - num1。 d. 计数器count加 1。循环结束后返回count。代码实现以Python为例def countOperations(num1: int, num2: int) - int: count 0 while num1 0 and num2 0: if num1 num2: num1 - num2 else: num2 - num1 count 1 return count这个解法的时间复杂度和空间复杂度分析是面试中的常见问题。时间复杂度在最坏情况下会很高。考虑num1 1,num2 10^9的情况每次只能将num2减去1需要循环大约10^9次这显然是无法接受的会导致超时。空间复杂度是 O(1)因为我们只使用了常数个变量。注意虽然模拟法思路简单但正是通过实现它我们才能切身感受到其效率瓶颈从而自然引出优化的必要性。在面试或竞赛中即使你一眼就看出了更优解先阐述这个基础解法也是一个很好的沟通策略它展示了你的思维过程。3. 优化策略洞察本质与数学联系3.1 从模拟到“类辗转相除”的优化当我们模拟num1 1000,num2 2这个过程时会发现要进行500次操作(1000,2)-(998,2)-(996,2)...。这一步一步的减法本质上不就是1000 // 2 500次吗因为每次都是用num1减去num2直到num1 num2。这给了我们一个强烈的优化提示当一个大数远大于小数时我们可以直接计算大数最多可以减去多少次小数而不是一次一次地减。优化后的思路如下在循环中我们仍然判断num1和num2的大小。如果num1 num2那么本轮可以连续执行num1 // num2次操作整除。操作次数直接加上这个商。同时num1更新为num1 % num2余数。反之亦然如果num2 num1则操作次数加上num2 // num1num2更新为num2 % num1。当任意一个数变为0时循环结束。优化后的代码实现def countOperations(num1: int, num2: int) - int: count 0 while num1 0 and num2 0: if num1 num2: count num1 // num2 # 一次性加上多次操作 num1 % num2 # 更新为余数 else: count num2 // num1 num2 % num1 return count这个优化非常关键。对于(1000, 2)的例子它只需要一次循环迭代count 1000//2 500,num1 1000%2 0循环结束。时间复杂度从 O(n) 降到了 O(log(min(num1, num2)))因为每次迭代至少会使其中一个数减少到小于另一个数这个过程类似于辗转相除法效率极高。3.2 深入本质与欧几里得算法的关联如果你熟悉“欧几里得算法”又称辗转相除法用于计算最大公约数GCD你会发现我们上面的优化过程几乎就是它的翻版。欧几里得算法的核心是gcd(a, b) gcd(b, a % b)直到余数为0。我们的操作过程呢同样是反复用大数减小数或取模直到出现0。这里存在一个美妙的数学关系题目中使一个数变为0所需的总操作次数与用辗转相除法求这两个数的最大公约数时所经历的步骤数密切相关。让我们更精确地描述一下。在辗转相除法中我们记录的是“递归调用”或“循环迭代”的次数。而在本题的优化模拟中我们记录的是“减法/取模”的总次数这个总次数等于所有整除商的和。例如求gcd(1071, 462)1071 462 * 2 147 - 商2462 147 * 3 21 - 商3147 21 * 7 0 - 商7 总操作次数如果一步步减就是 2 3 7 12。而辗转相除法的迭代次数是3次。因此本题可以理解为“带权重的欧几里得算法步骤计数”。理解这层关系不仅能帮助我们更好地优化代码还能让我们洞察到题目更深的数学背景。在面试中如果能指出这层联系无疑是巨大的加分项。4. 代码实现与细节剖析4.1 各语言实现示例与对比理解了优化算法后我们来看看在不同编程语言中如何优雅地实现它。关键在于高效地处理整除和取模运算并清晰地进行计数。Python 实现Python的实现非常简洁利用其动态类型和整数除法特性。def countOperations(num1: int, num2: int) - int: ops 0 while num1 and num2: # 当num1和num2都不为0时继续 if num1 num2: ops num1 // num2 num1 % num2 else: ops num2 // num1 num2 % num1 return opsPython中while num1 and num2利用了非零整数为True的特性写法很Pythonic。Java 实现Java是静态类型语言需要注意变量类型和循环条件。public int countOperations(int num1, int num2) { int count 0; while (num1 0 num2 0) { if (num1 num2) { count num1 / num2; // 整数除法 num1 % num2; } else { count num2 / num1; num2 % num1; } } return count; }C 实现与Java类似但通常放在类方法中。class Solution { public: int countOperations(int num1, int num2) { int ans 0; while (num1 0 num2 0) { if (num1 num2) { ans num1 / num2; num1 % num2; } else { ans num2 / num1; num2 % num1; } } return ans; } };JavaScript 实现var countOperations function(num1, num2) { let count 0; while (num1 0 num2 0) { if (num1 num2) { count Math.floor(num1 / num2); // JS需要显式取整 num1 % num2; } else { count Math.floor(num2 / num1); num2 % num1; } } return count; };在JavaScript中需要特别注意除法/的结果是浮点数必须用Math.floor取整才能得到正确的商。实操心得在不同语言间切换时要特别注意整数除法的行为。Python和C/Java的/在整数间运算时是整除而JavaScript不是。这是一个常见的跨语言陷阱。在写算法题时明确你所用语言的除法语义至关重要。4.2 边界条件与特殊用例处理即使算法核心正确忽略边界条件也会导致错误。让我们系统地检查一下初始即为0的情况题目说输入是正整数所以理论上不会出现0。但如果我们写的函数可能被复用处理num10或num20是良好的习惯。根据题意如果一开始就有0那么操作次数应为0。我们的while循环条件num10 num20已经完美处理了这种情况循环不会进入直接返回初始值0。相等的情况num1 num2时例如 (5,5)。按照我们的算法假设num1 num2成立则ops 5//5 1num1 5%5 0。循环结束返回1。这符合预期一次操作后两个数都变为0。大数极小数的极端情况这是优化算法展现威力的地方。例如(10^9, 1)模拟法需要10^9次循环必然超时。而优化算法第一次循环ops 10^9 // 1 10^9num1 10^9 % 1 0循环结束瞬间返回结果。时间复杂度是 O(1)。互质的情况例如(8,5)。算法过程8 5:ops1,num13。 (状态: 3,5)5 3:ops1,num22。 (状态: 3,2)3 2:ops1,num11。 (状态: 1,2)2 1:ops2,num20。 (状态: 1,0) 总操作数 1112 5。可以手动验证这个结果是正确的。通过以上测试我们的优化算法是健壮的。在面试中主动提出并测试这些边界情况能体现你思维的严密性。5. 复杂度分析与算法对比5.1 时间复杂度深度剖析我们详细分析一下优化后算法的时间复杂度。关键在于理解while循环的迭代次数。在每次循环中我们至少会使较大的那个数减少到小于较小的那个数。更准确地说我们是在执行一个类似辗转相除的过程。设a max(num1, num2),b min(num1, num2)。最坏情况是什么是让每次迭代的商尽可能小最好是1。这发生在连续两次迭代的商都是1时这对应于斐波那契数列相邻项的情况。例如计算gcd(F_{n1}, F_n)其中 F 是斐波那契数F_00, F_11这会导致大约 n 次迭代而F_n是指数级增长的。因此迭代次数 O(logφ(min(a, b)))其中 φ 是黄金比例 (≈1.618)。由于每次迭代内部的操作比较、除法、取模、加法都是 O(1) 的所以总的时间复杂度是O(log(min(a, b)))。这与未经优化的模拟法在最坏情况下的O(max(a, b))形成了天壤之别。对于大的输入值例如 (10^9, 1)O(log(1)) ~ O(1) 对比 O(10^9)优化效果是决定性的。5.2 空间复杂度与常数优化空间复杂度非常直观。我们只使用了固定数量的整数变量num1,num2,count以及循环中的临时比较结果不随输入规模增长。因此空间复杂度是O(1)即常数空间。关于常数优化在这个算法中余地不大因为核心操作已经很精简。但有一点可以注意在循环内部我们每次都要进行if-else判断。有些写法会尝试在循环外预先判断或使用交换技巧但在这个场景下收益微乎其微甚至可能因为额外的赋值操作而降低可读性。保持代码清晰易懂是更重要的。算法对比总结表特性朴素模拟法优化模拟辗转思想法核心思想严格按题意一次减一步利用整除批量计算减法次数时间复杂度O(max(a, b)) (最坏)O(log(min(a, b)))空间复杂度O(1)O(1)代码复杂度简单直观中等需要理解取模运算适用场景仅用于理解题意输入极小解决题目的标准答案关键缺陷大输入超时无显然优化模拟法是解决本题的唯一可行方案。它完美地平衡了效率和实现难度。6. 常见“踩坑点”与调试技巧6.1 典型错误代码示例分析即便思路正确实现时也容易掉进一些坑里。下面列举几个常见的错误错误1忘记更新循环条件中的变量# 错误示例 while num1 0 and num2 0: if num1 num2: num1 num1 - num2 else: num2 num2 - num1 # 这里错了 count 1仔细看在else分支里应该是num2 num2 - num1但有人会写成num2 num1 - num2这会导致逻辑完全错误甚至产生负数使循环无法终止。错误2整数除法行为不一致尤其在JavaScript中// JavaScript 错误示例 while (num1 0 num2 0) { if (num1 num2) { count num1 / num2; // 错误未取整 num1 % num2; } // ... }在JS中num1 / num2得到的是浮点数比如5/22.5。直接加到整数count上最终结果可能是小数不符合题目要求。必须使用Math.floor(num1 / num2)。错误3未能处理“一次性减完”导致余数为0的情况这个其实我们的优化算法已经处理了。但思维上要清楚当num1 // num2的余数num1 % num2为0时意味着num1被num2整除了。此时num1应变为0循环条件num1 0将在下一次判断时为假循环正确终止。如果在这里不小心可能会错误地让循环多跑一次。6.2 调试方法与测试用例设计当你怀疑代码有问题时系统化的调试是关键。打印中间状态在循环内打印num1,num2,count的值。这是最直接的方法。def countOperations(num1, num2): count 0 while num1 0 and num2 0: print(fBefore: num1{num1}, num2{num2}, count{count}) if num1 num2: quotient num1 // num2 count quotient num1 % num2 print(f Action: num1 num2, added {quotient} ops, num1-{num1}) else: quotient num2 // num1 count quotient num2 % num1 print(f Action: num2 num1, added {quotient} ops, num2-{num2}) print(fResult: {count}) return count设计全面的测试用例不要只测一两个例子。一个好的测试集应该包括最小输入(1, 1)。预期结果1。包含0的输入边界(0, 5)。预期结果0。相等数字(7, 7)。预期结果1。大数 vs 小数(1000000, 2)。用模拟法会极慢用优化法应瞬间得出结果500000。互质数(8, 5)。预期结果5过程见前文。一个数是另一个的倍数(15, 5)。预期结果315//53一步归零。顺序无关性(a, b)和(b, a)的结果应该相同。测试(10,4)和(4,10)。使用在线判题系统的测试用例如果是在LeetCode上做题利用其提供的“运行代码”功能针对出错的特定用例进行调试。仔细对比你的输出和预期输出回溯你的逻辑。避坑技巧在写出最终代码前先在脑子里或纸上模拟一遍算法在几个典型用例上的运行过程。这能帮你提前发现逻辑漏洞比如更新变量的顺序、循环条件等。对于这道题在纸上画一画(8,5)和(15,5)的过程比直接写代码然后调试更节省时间。7. 举一反三相关题型与思维扩展7.1 LeetCode中的相似题目解决一个问题后联想和对比相似题目是巩固学习效果、建立知识网络的最佳方式。LeetCode 2169 属于“模拟过程”和“数学”交叉的题目。与之相关的题目有LeetCode 1979. Find Greatest Common Divisor of Array找出数组最大公约数。直接应用欧几里得算法。LeetCode 2543. Check if Point Is Reachable一道困难题但核心也涉及到辗转相除的思想来判断点的可达性是本题数学思想的深度扩展。LeetCode 780. Reaching Points另一道关于通过特定操作类似本题的减法但规则不同能否到达目标点的题目需要更复杂的数学推理。LeetCode 2183. Count Array Pairs Divisible by K虽然主题不同但解题中巧妙用到最大公约数的性质来统计配对。这些题目都在不同程度上考察了你对整数操作、模运算和最大公约数性质的理解。把2169题吃透理解其与欧几里得算法的关联会为你解决这些更复杂的问题打下坚实的基础。7.2 从“操作次数”到“计算过程”的思维转变本题要求的是操作次数。我们是否可以扩展一下要求记录下每一步操作后的数对状态呢这是一个很自然的扩展。例如对于输入(2,3)输出操作序列[(3,2), (1,2), (1,1), (0,1)]。实现这个扩展并不难只需要在循环中在执行更新前将当前状态(num1, num2)保存到一个列表里即可。但这里有一个细节需要注意我们优化后的算法是“批量”减法它跳过了中间相同的状态。例如(10,2)优化算法一步就得到(0,2)但实际上过程是(10,2)-(8,2)-(6,2)-(4,2)-(2,2)-(0,2)。如果我们想记录所有中间状态就必须回到最朴素的、一次减一的模拟法或者对优化算法进行修改在批量减法的循环内再嵌套一个循环来生成中间状态。这体现了问题目标不同最优算法可能不同。在面试中如果面试官提出这个变体一定要先澄清需求是要最终次数还是要完整过程另一个思维扩展是如果操作不是减法而是其他运算呢比如每次用大数除以小数整数除直到出现1或0这类问题往往需要重新分析其数学性质但思考框架是相似的先模拟找规律尝试优化洞察其与经典算法或数学概念的关联。这道“得到0的操作数”的题目就像一颗投入湖面的石子。它的涟漪可以波及到模拟、数论、算法优化等多个领域。掌握它不仅仅是解决了一道题更是掌握了一种分析问题、优化求解的思维模式。下次再遇到那种“反复操作直到满足某个条件”的题目时你会自然而然地想到它的本质是什么过程能否加速和哪些经典算法有关联这才是刷题带给我们的真正价值。 LeetCode 2169 题解：从模拟到欧几里得算法，掌握“归零”操作数的优化技巧
1. 项目概述从一道题看“归零”的算法艺术最近在刷LeetCode的时候碰到了第2169题“得到 0 的操作数”。乍一看标题你可能会有点懵操作数得到0这到底是要干什么其实这是一道非常典型的模拟题它不涉及高深的动态规划或者复杂的图论核心考察的是你对问题逻辑的理解、代码实现的严谨性以及那么一点点的数学直觉。简单来说题目给了你两个正整数num1和num2你需要反复执行一个操作用较大的数减去较小的数直到其中一个数变成0。题目要求你返回执行这个操作的次数。举个例子如果num1 10,num2 10那么一步操作后两个数都变成了0操作次数就是1。如果num1 2,num2 3过程是(3,2) - (1,2) - (1,1) - (0,1)操作次数是3。这道题适合所有正在学习编程基础、想要巩固循环和条件判断的同学也适合想寻找清晰逻辑训练的老手。它就像算法世界里的“磨刀石”看似简单但要想写出高效、优雅的解法并透彻理解其背后的数学原理还真得花点心思。接下来我就带你彻底拆解这道题从最直接的暴力模拟到优化思路再到其背后隐藏的“欧几里得算法”影子让你不仅AC这道题更能收获一类问题的解决心法。2. 问题核心与思路拆解2.1 题意解析与输入输出规范题目描述非常清晰给定两个正整数num1和num2。在每一步操作中你需要比较当前的两个数然后用较大的数减去较小的数。注意操作完成后被减的数较大的数更新为差值而较小的数保持不变。重复这个过程直到两个数中至少有一个变为 0。你需要计算并返回总共执行的操作次数。这里有几个关键点需要明确这些往往是第一次做题时容易忽略的坑点操作对象每次操作只改变两个数中的一个即较大的那个数。较小的数在本轮操作中不变。终止条件是“直到两个数中至少有一个变为 0”。这意味着当num1或num2中任意一个为0时循环立即停止。不需要两个同时为0虽然在某些情况下会同时为0。操作计数每一次“比较-相减”算作一次操作无论差值是多少。输入范围题目明确是正整数所以不需要处理0或负数的情况这简化了边界条件。输入输出示例输入num1 10, num2 10 输出1 解释第一轮操作后两个数都变为0。输入num1 2, num2 3 输出3 解释(3,2)-(1,2)-(1,1)-(0,1)理解题意后最直观的想法就是模拟这个过程。这也是面试官常常期望候选人首先给出的解法清晰、正确、易于理解和沟通。2.2 模拟法最直接的实现路径模拟法完全按照题目描述的步骤来写代码思路直白是验证我们对问题理解是否正确的最佳方式。我们可以用一个while循环只要两个数都不为0就持续执行操作。算法步骤初始化操作计数器count 0。使用while循环条件为num1 0 num2 0即两个数都大于0。在循环体内 a. 比较num1和num2。 b. 如果num1 num2则num1 num1 - num2。 c. 否则num2 num2 - num1。 d. 计数器count加 1。循环结束后返回count。代码实现以Python为例def countOperations(num1: int, num2: int) - int: count 0 while num1 0 and num2 0: if num1 num2: num1 - num2 else: num2 - num1 count 1 return count这个解法的时间复杂度和空间复杂度分析是面试中的常见问题。时间复杂度在最坏情况下会很高。考虑num1 1,num2 10^9的情况每次只能将num2减去1需要循环大约10^9次这显然是无法接受的会导致超时。空间复杂度是 O(1)因为我们只使用了常数个变量。注意虽然模拟法思路简单但正是通过实现它我们才能切身感受到其效率瓶颈从而自然引出优化的必要性。在面试或竞赛中即使你一眼就看出了更优解先阐述这个基础解法也是一个很好的沟通策略它展示了你的思维过程。3. 优化策略洞察本质与数学联系3.1 从模拟到“类辗转相除”的优化当我们模拟num1 1000,num2 2这个过程时会发现要进行500次操作(1000,2)-(998,2)-(996,2)...。这一步一步的减法本质上不就是1000 // 2 500次吗因为每次都是用num1减去num2直到num1 num2。这给了我们一个强烈的优化提示当一个大数远大于小数时我们可以直接计算大数最多可以减去多少次小数而不是一次一次地减。优化后的思路如下在循环中我们仍然判断num1和num2的大小。如果num1 num2那么本轮可以连续执行num1 // num2次操作整除。操作次数直接加上这个商。同时num1更新为num1 % num2余数。反之亦然如果num2 num1则操作次数加上num2 // num1num2更新为num2 % num1。当任意一个数变为0时循环结束。优化后的代码实现def countOperations(num1: int, num2: int) - int: count 0 while num1 0 and num2 0: if num1 num2: count num1 // num2 # 一次性加上多次操作 num1 % num2 # 更新为余数 else: count num2 // num1 num2 % num1 return count这个优化非常关键。对于(1000, 2)的例子它只需要一次循环迭代count 1000//2 500,num1 1000%2 0循环结束。时间复杂度从 O(n) 降到了 O(log(min(num1, num2)))因为每次迭代至少会使其中一个数减少到小于另一个数这个过程类似于辗转相除法效率极高。3.2 深入本质与欧几里得算法的关联如果你熟悉“欧几里得算法”又称辗转相除法用于计算最大公约数GCD你会发现我们上面的优化过程几乎就是它的翻版。欧几里得算法的核心是gcd(a, b) gcd(b, a % b)直到余数为0。我们的操作过程呢同样是反复用大数减小数或取模直到出现0。这里存在一个美妙的数学关系题目中使一个数变为0所需的总操作次数与用辗转相除法求这两个数的最大公约数时所经历的步骤数密切相关。让我们更精确地描述一下。在辗转相除法中我们记录的是“递归调用”或“循环迭代”的次数。而在本题的优化模拟中我们记录的是“减法/取模”的总次数这个总次数等于所有整除商的和。例如求gcd(1071, 462)1071 462 * 2 147 - 商2462 147 * 3 21 - 商3147 21 * 7 0 - 商7 总操作次数如果一步步减就是 2 3 7 12。而辗转相除法的迭代次数是3次。因此本题可以理解为“带权重的欧几里得算法步骤计数”。理解这层关系不仅能帮助我们更好地优化代码还能让我们洞察到题目更深的数学背景。在面试中如果能指出这层联系无疑是巨大的加分项。4. 代码实现与细节剖析4.1 各语言实现示例与对比理解了优化算法后我们来看看在不同编程语言中如何优雅地实现它。关键在于高效地处理整除和取模运算并清晰地进行计数。Python 实现Python的实现非常简洁利用其动态类型和整数除法特性。def countOperations(num1: int, num2: int) - int: ops 0 while num1 and num2: # 当num1和num2都不为0时继续 if num1 num2: ops num1 // num2 num1 % num2 else: ops num2 // num1 num2 % num1 return opsPython中while num1 and num2利用了非零整数为True的特性写法很Pythonic。Java 实现Java是静态类型语言需要注意变量类型和循环条件。public int countOperations(int num1, int num2) { int count 0; while (num1 0 num2 0) { if (num1 num2) { count num1 / num2; // 整数除法 num1 % num2; } else { count num2 / num1; num2 % num1; } } return count; }C 实现与Java类似但通常放在类方法中。class Solution { public: int countOperations(int num1, int num2) { int ans 0; while (num1 0 num2 0) { if (num1 num2) { ans num1 / num2; num1 % num2; } else { ans num2 / num1; num2 % num1; } } return ans; } };JavaScript 实现var countOperations function(num1, num2) { let count 0; while (num1 0 num2 0) { if (num1 num2) { count Math.floor(num1 / num2); // JS需要显式取整 num1 % num2; } else { count Math.floor(num2 / num1); num2 % num1; } } return count; };在JavaScript中需要特别注意除法/的结果是浮点数必须用Math.floor取整才能得到正确的商。实操心得在不同语言间切换时要特别注意整数除法的行为。Python和C/Java的/在整数间运算时是整除而JavaScript不是。这是一个常见的跨语言陷阱。在写算法题时明确你所用语言的除法语义至关重要。4.2 边界条件与特殊用例处理即使算法核心正确忽略边界条件也会导致错误。让我们系统地检查一下初始即为0的情况题目说输入是正整数所以理论上不会出现0。但如果我们写的函数可能被复用处理num10或num20是良好的习惯。根据题意如果一开始就有0那么操作次数应为0。我们的while循环条件num10 num20已经完美处理了这种情况循环不会进入直接返回初始值0。相等的情况num1 num2时例如 (5,5)。按照我们的算法假设num1 num2成立则ops 5//5 1num1 5%5 0。循环结束返回1。这符合预期一次操作后两个数都变为0。大数极小数的极端情况这是优化算法展现威力的地方。例如(10^9, 1)模拟法需要10^9次循环必然超时。而优化算法第一次循环ops 10^9 // 1 10^9num1 10^9 % 1 0循环结束瞬间返回结果。时间复杂度是 O(1)。互质的情况例如(8,5)。算法过程8 5:ops1,num13。 (状态: 3,5)5 3:ops1,num22。 (状态: 3,2)3 2:ops1,num11。 (状态: 1,2)2 1:ops2,num20。 (状态: 1,0) 总操作数 1112 5。可以手动验证这个结果是正确的。通过以上测试我们的优化算法是健壮的。在面试中主动提出并测试这些边界情况能体现你思维的严密性。5. 复杂度分析与算法对比5.1 时间复杂度深度剖析我们详细分析一下优化后算法的时间复杂度。关键在于理解while循环的迭代次数。在每次循环中我们至少会使较大的那个数减少到小于较小的那个数。更准确地说我们是在执行一个类似辗转相除的过程。设a max(num1, num2),b min(num1, num2)。最坏情况是什么是让每次迭代的商尽可能小最好是1。这发生在连续两次迭代的商都是1时这对应于斐波那契数列相邻项的情况。例如计算gcd(F_{n1}, F_n)其中 F 是斐波那契数F_00, F_11这会导致大约 n 次迭代而F_n是指数级增长的。因此迭代次数 O(logφ(min(a, b)))其中 φ 是黄金比例 (≈1.618)。由于每次迭代内部的操作比较、除法、取模、加法都是 O(1) 的所以总的时间复杂度是O(log(min(a, b)))。这与未经优化的模拟法在最坏情况下的O(max(a, b))形成了天壤之别。对于大的输入值例如 (10^9, 1)O(log(1)) ~ O(1) 对比 O(10^9)优化效果是决定性的。5.2 空间复杂度与常数优化空间复杂度非常直观。我们只使用了固定数量的整数变量num1,num2,count以及循环中的临时比较结果不随输入规模增长。因此空间复杂度是O(1)即常数空间。关于常数优化在这个算法中余地不大因为核心操作已经很精简。但有一点可以注意在循环内部我们每次都要进行if-else判断。有些写法会尝试在循环外预先判断或使用交换技巧但在这个场景下收益微乎其微甚至可能因为额外的赋值操作而降低可读性。保持代码清晰易懂是更重要的。算法对比总结表特性朴素模拟法优化模拟辗转思想法核心思想严格按题意一次减一步利用整除批量计算减法次数时间复杂度O(max(a, b)) (最坏)O(log(min(a, b)))空间复杂度O(1)O(1)代码复杂度简单直观中等需要理解取模运算适用场景仅用于理解题意输入极小解决题目的标准答案关键缺陷大输入超时无显然优化模拟法是解决本题的唯一可行方案。它完美地平衡了效率和实现难度。6. 常见“踩坑点”与调试技巧6.1 典型错误代码示例分析即便思路正确实现时也容易掉进一些坑里。下面列举几个常见的错误错误1忘记更新循环条件中的变量# 错误示例 while num1 0 and num2 0: if num1 num2: num1 num1 - num2 else: num2 num2 - num1 # 这里错了 count 1仔细看在else分支里应该是num2 num2 - num1但有人会写成num2 num1 - num2这会导致逻辑完全错误甚至产生负数使循环无法终止。错误2整数除法行为不一致尤其在JavaScript中// JavaScript 错误示例 while (num1 0 num2 0) { if (num1 num2) { count num1 / num2; // 错误未取整 num1 % num2; } // ... }在JS中num1 / num2得到的是浮点数比如5/22.5。直接加到整数count上最终结果可能是小数不符合题目要求。必须使用Math.floor(num1 / num2)。错误3未能处理“一次性减完”导致余数为0的情况这个其实我们的优化算法已经处理了。但思维上要清楚当num1 // num2的余数num1 % num2为0时意味着num1被num2整除了。此时num1应变为0循环条件num1 0将在下一次判断时为假循环正确终止。如果在这里不小心可能会错误地让循环多跑一次。6.2 调试方法与测试用例设计当你怀疑代码有问题时系统化的调试是关键。打印中间状态在循环内打印num1,num2,count的值。这是最直接的方法。def countOperations(num1, num2): count 0 while num1 0 and num2 0: print(fBefore: num1{num1}, num2{num2}, count{count}) if num1 num2: quotient num1 // num2 count quotient num1 % num2 print(f Action: num1 num2, added {quotient} ops, num1-{num1}) else: quotient num2 // num1 count quotient num2 % num1 print(f Action: num2 num1, added {quotient} ops, num2-{num2}) print(fResult: {count}) return count设计全面的测试用例不要只测一两个例子。一个好的测试集应该包括最小输入(1, 1)。预期结果1。包含0的输入边界(0, 5)。预期结果0。相等数字(7, 7)。预期结果1。大数 vs 小数(1000000, 2)。用模拟法会极慢用优化法应瞬间得出结果500000。互质数(8, 5)。预期结果5过程见前文。一个数是另一个的倍数(15, 5)。预期结果315//53一步归零。顺序无关性(a, b)和(b, a)的结果应该相同。测试(10,4)和(4,10)。使用在线判题系统的测试用例如果是在LeetCode上做题利用其提供的“运行代码”功能针对出错的特定用例进行调试。仔细对比你的输出和预期输出回溯你的逻辑。避坑技巧在写出最终代码前先在脑子里或纸上模拟一遍算法在几个典型用例上的运行过程。这能帮你提前发现逻辑漏洞比如更新变量的顺序、循环条件等。对于这道题在纸上画一画(8,5)和(15,5)的过程比直接写代码然后调试更节省时间。7. 举一反三相关题型与思维扩展7.1 LeetCode中的相似题目解决一个问题后联想和对比相似题目是巩固学习效果、建立知识网络的最佳方式。LeetCode 2169 属于“模拟过程”和“数学”交叉的题目。与之相关的题目有LeetCode 1979. Find Greatest Common Divisor of Array找出数组最大公约数。直接应用欧几里得算法。LeetCode 2543. Check if Point Is Reachable一道困难题但核心也涉及到辗转相除的思想来判断点的可达性是本题数学思想的深度扩展。LeetCode 780. Reaching Points另一道关于通过特定操作类似本题的减法但规则不同能否到达目标点的题目需要更复杂的数学推理。LeetCode 2183. Count Array Pairs Divisible by K虽然主题不同但解题中巧妙用到最大公约数的性质来统计配对。这些题目都在不同程度上考察了你对整数操作、模运算和最大公约数性质的理解。把2169题吃透理解其与欧几里得算法的关联会为你解决这些更复杂的问题打下坚实的基础。7.2 从“操作次数”到“计算过程”的思维转变本题要求的是操作次数。我们是否可以扩展一下要求记录下每一步操作后的数对状态呢这是一个很自然的扩展。例如对于输入(2,3)输出操作序列[(3,2), (1,2), (1,1), (0,1)]。实现这个扩展并不难只需要在循环中在执行更新前将当前状态(num1, num2)保存到一个列表里即可。但这里有一个细节需要注意我们优化后的算法是“批量”减法它跳过了中间相同的状态。例如(10,2)优化算法一步就得到(0,2)但实际上过程是(10,2)-(8,2)-(6,2)-(4,2)-(2,2)-(0,2)。如果我们想记录所有中间状态就必须回到最朴素的、一次减一的模拟法或者对优化算法进行修改在批量减法的循环内再嵌套一个循环来生成中间状态。这体现了问题目标不同最优算法可能不同。在面试中如果面试官提出这个变体一定要先澄清需求是要最终次数还是要完整过程另一个思维扩展是如果操作不是减法而是其他运算呢比如每次用大数除以小数整数除直到出现1或0这类问题往往需要重新分析其数学性质但思考框架是相似的先模拟找规律尝试优化洞察其与经典算法或数学概念的关联。这道“得到0的操作数”的题目就像一颗投入湖面的石子。它的涟漪可以波及到模拟、数论、算法优化等多个领域。掌握它不仅仅是解决了一道题更是掌握了一种分析问题、优化求解的思维模式。下次再遇到那种“反复操作直到满足某个条件”的题目时你会自然而然地想到它的本质是什么过程能否加速和哪些经典算法有关联这才是刷题带给我们的真正价值。