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^5

解题思路

这道题可以通过模拟过程来解决，也可以通过优化的数学方法来解决。

方法一：直接模拟 按照题目要求，每次比较两个数的大小，从较大的数中减去较小的数，直到其中一个数变为 0。这种方法直观但效率较低，当数字很大时可能需要很多次操作。

方法二：优化的除法模拟（推荐） 我们可以观察到，连续多次从较大数中减去较小数，实际上等价于求较大数除以较小数的商。例如，如果 num1 = 10, num2 = 3，那么连续减法 10-3-3-3=1 等价于 10 % 3 = 1，操作次数为 10 / 3 = 3次。

这样我们可以用除法和取模运算来快速计算操作次数，避免逐步减法的低效率。每次计算较大数除以较小数的商作为操作次数的一部分，然后用较小数和余数继续下一轮计算，直到其中一个数变为 0。

方法三：欧几里得算法思想 仔细观察可以发现，这个过程实际上就是求两个数的最大公约数（GCD）的欧几里得算法过程，我们只需要记录操作次数即可。

代码实现

class Solution {
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;
    }
};

class Solution:
    def countOperations(self, 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

public class Solution {
    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;
    }
}

var countOperations = function(num1, num2) {
    let count = 0;
    while (num1 > 0 && num2 > 0) {
        if (num1 >= num2) {
            count += Math.floor(num1 / num2);
            num1 %= num2;
        } else {
            count += Math.floor(num2 / num1);
            num2 %= num1;
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型直接模拟优化解法
时间复杂度O(max(num1, num2))O(log(min(num1, num2)))
空间复杂度O(1)O(1)

相关题目