LeetCode 题解工作台
转化数字的最小运算数
给你一个下标从 0 开始的整数数组 nums ，该数组由 互不相同 的数字组成。另给你两个整数 start 和 goal 。 整数 x 的值最开始设为 start ，你打算执行一些运算使 x 转化为 goal 。你可以对数字 x 重复执行下述运算： 如果 0 ，那么，对于数组中的任一下标 i （ 0…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
class Solution: def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums ，该数组由 互不相同 的数字组成。另给你两个整数 start 和 goal 。
整数 x 的值最开始设为 start ，你打算执行一些运算使 x 转化为 goal 。你可以对数字 x 重复执行下述运算：
如果 0 <= x <= 1000 ，那么，对于数组中的任一下标 i（0 <= i < nums.length），可以将 x 设为下述任一值：
x + nums[i]x - nums[i]x ^ nums[i]（按位异或 XOR）
注意，你可以按任意顺序使用每个 nums[i] 任意次。使 x 越过 0 <= x <= 1000 范围的运算同样可以生效，但该该运算执行后将不能执行其他运算。
返回将 x = start 转化为 goal 的最小操作数；如果无法完成转化，则返回 -1 。
示例 1：
输入：nums = [2,4,12], start = 2, goal = 12 输出：2 解释： 可以按 2 → 14 → 12 的转化路径进行，只需执行下述 2 次运算： - 2 + 12 = 14 - 14 - 2 = 12
示例 2：
输入：nums = [3,5,7], start = 0, goal = -4 输出：2 解释： 可以按 0 → 3 → -4 的转化路径进行，只需执行下述 2 次运算： - 0 + 3 = 3 - 3 - 7 = -4 注意，最后一步运算使 x 超过范围 0 <= x <= 1000 ，但该运算仍然可以生效。
示例 3：
输入：nums = [2,8,16], start = 0, goal = 1 输出：-1 解释： 无法将 0 转化为 1
提示：
1 <= nums.length <= 1000-109 <= nums[i], goal <= 1090 <= start <= 1000start != goalnums中的所有整数互不相同
解题思路
方法一
class Solution:
def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
op1 = lambda x, y: x + y
op2 = lambda x, y: x - y
op3 = lambda x, y: x ^ y
ops = [op1, op2, op3]
vis = [False] * 1001
q = deque([(start, 0)])
while q:
x, step = q.popleft()
for num in nums:
for op in ops:
nx = op(x, num)
if nx == goal:
return step + 1
if 0 <= nx <= 1000 and not vis[nx]:
q.append((nx, step + 1))
vis[nx] = True
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the BFS traversal over the state space from start to goal, potentially O(n*range) where range is limited to numbers within 0 to 1000 plus immediate out-of-range transitions. Space complexity is O(range) for the visited set and queue. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Does your solution correctly handle numbers that exceed 1000 or go below 0?
- question_mark
Are you efficiently avoiding revisiting states in the BFS queue?
- question_mark
Can you explain why BFS guarantees the minimum number of operations for this problem?
常见陷阱
外企场景- error
Ignoring that numbers outside 0-1000 can only be used once for the final operation.
- error
Failing to track visited numbers, leading to cycles or redundant computation.
- error
Applying operations without checking whether the goal can be reached immediately when leaving the valid range.
进阶变体
外企场景- arrow_right_alt
Minimize operations using only addition and subtraction instead of including XOR.
- arrow_right_alt
Allow repeated elements from nums to be applied multiple times in sequence without BFS tracking.
- arrow_right_alt
Limit the operations so x must always remain within 0 to 1000, disallowing out-of-range moves.