LeetCode 题解工作台
使 X 和 Y 相等的最少操作次数
给你两个正整数 x 和 y 。 一次操作中，你可以执行以下四种操作之一： 如果 x 是 11 的倍数，将 x 除以 11 。 如果 x 是 5 的倍数，将 x 除以 5 。 将 x 减 1 。 将 x 加 1 。 请你返回让 x 和 y 相等的 最少 操作次数。 示例 1： 输入： x = 26, …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
class Solution: def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个正整数 x 和 y 。
一次操作中，你可以执行以下四种操作之一：
- 如果
x是11的倍数，将x除以11。 - 如果
x是5的倍数，将x除以5。 - 将
x减1。 - 将
x加1。
请你返回让 x 和 y 相等的 最少 操作次数。
示例 1：
输入：x = 26, y = 1 输出：3 解释：我们可以通过以下操作将 26 变为 1 ： 1. 将 x 减 1 2. 将 x 除以 5 3. 将 x 除以 5 将 26 变为 1 最少需要 3 次操作。
示例 2：
输入：x = 54, y = 2 输出：4 解释：我们可以通过以下操作将 54 变为 2 ： 1. 将 x 加 1 2. 将 x 除以 11 3. 将 x 除以 5 4. 将 x 加 1 将 54 变为 2 最少需要 4 次操作。
示例 3：
输入：x = 25, y = 30 输出：5 解释：我们可以通过以下操作将 25 变为 30 ： 1. 将 x 加 1 2. 将 x 加 1 3. 将 x 加 1 4. 将 x 加 1 5. 将 x 加 1 将 25 变为 30 最少需要 5 次操作。
提示：
1 <= x, y <= 104
解题思路
方法一
class Solution:
def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
@cache
def dfs(x: int) -> int:
if y >= x:
return y - x
ans = x - y
ans = min(ans, x % 5 + 1 + dfs(x // 5))
ans = min(ans, 5 - x % 5 + 1 + dfs(x // 5 + 1))
ans = min(ans, x % 11 + 1 + dfs(x // 11))
ans = min(ans, 11 - x % 11 + 1 + dfs(x // 11 + 1))
return ans
return dfs(x)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the method chosen. BFS explores reachable states with O(max(x, y)) in practice, while DP with memoization reduces repeated computations, making the approach efficient within constraints 1 <= x, y <= 104. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you considering cases where x needs multiple divisions before reaching y?
- question_mark
How does your DP handle memoization to avoid recomputing states?
- question_mark
What is the immediate solution when y is greater than or equal to x?
常见陷阱
外企场景- error
Forgetting that increments are the only way to increase x and directly returning y - x when y >= x.
- error
Not memoizing intermediate states, which leads to redundant computations and timeout.
- error
Applying divisions without checking divisibility by 5 or 11, resulting in invalid state transitions.
进阶变体
外企场景- arrow_right_alt
Compute minimum operations if only increment and decrement are allowed without division.
- arrow_right_alt
Find the minimum operations to make x equal y using a different set of divisors, like 2 and 3.
- arrow_right_alt
Determine operations if division results must be rounded down instead of integer division.