LeetCode 题解工作台
得到 0 的操作数
给你两个 非负 整数 num1 和 num2 。 每一步 操作 中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1 。 例如， num1 = 5 且 num2 = 4 ，应该用 num1 减 num2 ，因此，得到 num1 = 1 和 …
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数学·结合·模拟
答案摘要
我们可以直接模拟这个过程，循环执行以下操作： - 如果 $\textit{num1} \ge \textit{num2}$，则 $\textit{num1} = \textit{num1} - \textit{num2}$；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·结合·模拟 题型思路
题目描述
给你两个 非负 整数 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 <= 105
解题思路
方法一：模拟
我们可以直接模拟这个过程，循环执行以下操作：
- 如果 ，则 ；
- 否则，。
- 每执行一次操作，操作数加一。
当 或 有一个为 时，停止循环，返回操作数。
时间复杂度 ，其中 为 和 的最大值。空间复杂度 。
class Solution:
def countOperations(self, num1: int, num2: int) -> int:
ans = 0
while num1 and num2:
if num1 >= num2:
num1 -= num2
else:
num2 -= num1
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity can vary depending on the approach, but a direct simulation results in linear time proportional to the values of num1 and num2. Optimized approaches might reduce this to logarithmic time in some cases, especially when division is used to jump over multiple steps. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests understanding of basic simulation techniques.
- question_mark
Evaluates efficiency considerations in problem-solving.
- question_mark
Looks for correct handling of edge cases and optimized solutions.
常见陷阱
外企场景- error
Failing to consider edge cases, such as when either num1 or num2 is already zero.
- error
Overcomplicating the solution when a simple simulation is sufficient.
- error
Not optimizing the process for larger values of num1 and num2.
进阶变体
外企场景- arrow_right_alt
Consider handling larger inputs efficiently using mathematical shortcuts.
- arrow_right_alt
Modify the problem to count operations to reach a specific value other than zero.
- arrow_right_alt
Introduce a constraint that only allows subtraction in certain conditions, altering the simulation.