得到 0 的操作数

难度: Easy

给你两个非负整数 num1 和 num2 。

每一步操作中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1 。

例如，num1 = 5 且 num2 = 4 ，应该用 num1 减 num2 ，因此，得到 num1 = 1 和 num2 = 4 。然而，如果 num1 = 4且 num2 = 5 ，一步操作后，得到 num1 = 4 和 num2 = 1 。

返回使 num1 = 0 或 num2 = 0 的 操作数 。

示例 1：

输入：num1 = 2, num2 = 3
输出：3
解释：
- 操作 1 ：num1 = 2 ，num2 = 3 。由于 num1 < num2 ，num2 减 num1 得到 num1 = 2 ，num2 = 3 - 2 = 1 。
- 操作 2 ：num1 = 2 ，num2 = 1 。由于 num1 > num2 ，num1 减 num2 。
- 操作 3 ：num1 = 1 ，num2 = 1 。由于 num1 == num2 ，num1 减 num2 。
此时 num1 = 0 ，num2 = 1 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 3 。

示例 2：

输入：num1 = 10, num2 = 10
输出：1
解释：
- 操作 1 ：num1 = 10 ，num2 = 10 。由于 num1 == num2 ，num1 减 num2 得到 num1 = 10 - 10 = 0 。
此时 num1 = 0 ，num2 = 10 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 1 。

提示：

0 <= num1, num2 <= 10⁵

Submission

运行时间: 24 ms

内存: 16.0 MB

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        count = 0
        while num1 and num2:
            count += num1//num2
            num1 %= num2
            num1, num2 = num2, num1
        return count

Explain

这个题解采用了类似于欧几里得算法求最大公约数的方法。在每一步操作中，我们使用较大数减去较小数。如果 num1 >= num2，则 num1 减去 num2，否则 num2 减去 num1。这实际上是在计算两个数的最大公约数的过程中的步骤计数。通过交换 num1 和 num2 并取模（num1 % num2），我们逐步减小 num1 和 num2 的值，直到其中一个变为0。count 变量用于记录操作的次数。

时间复杂度: O(log(min(num1, num2)))

空间复杂度: O(1)

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        count = 0  # 初始化操作计数器
        while num1 and num2:  # 只要 num1 和 num2 都不为0，继续操作
            count += num1 // num2  # 增加由 num1 // num2 得到的操作次数
            num1 %= num2  # 更新 num1 为 num1 对 num2 的模
            num1, num2 = num2, num1  # 交换 num1 和 num2
        return count  # 返回总的操作次数

Explore

考虑两个数num1和num2，其中num1 >= num2。在执行num1 %= num2操作后，num1将更新为num1和num2的余数。若num1 >= 2*num2，则在取模后的结果num1将至少减少到少于num2的值，即至少减半。例如，如果num1是100，num2是30，那么取模后num1更新为10，显著减小。这是因为num1 - k*num2（其中k是整数，k = num1 // num2）会使num1减少到小于num2的值。当num1小于2*num2时，取模操作至少将num1减少到小于num2，因此至少减半的情况出现在num1远大于num2时。

这组操作确保了算法总是向前推进的。首先，`num1 % num2`操作会将其中一个数减小到小于另一个数的值，这意味着问题规模在每一步都在减小。然后，通过`num1, num2 = num2, num1`操作，我们将较小的数放在num1位置，保证在下一次迭代中再次应用取模操作。这种交替减小和重新排序确保两个数中至少有一个在接下来的操作中减小，从而避免无限循环。

在处理非常接近的两个数时，例如num1=1000000和num2=999999，算法的效率较低。在此特定示例中，num1 % num2将得到1（num1 - num2），然后数值交换后num2变为1，再进行一次计算就结束。这种情况下，算法需要多次操作来达到结束条件，尤其是当两数非常接近但都很大时。因此，尽管算法最终会完成，但在这种极端情况下效率并不高。

题解中通过在循环条件中检查`while num1 and num2`确保了当num1或num2任一为0时，循环停止，从而处理了边界情况。如果num1或num2的初始值为0，那么循环将不会开始，直接返回操作计数器当前的值，即0。这样有效避免了除以零的错误或无效的取模操作。