LeetCode 题解工作台
到家的最少跳跃次数
有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。 跳蚤跳跃的规则如下： 它可以 往前 跳恰好 a 个位置（即往右跳）。 它可以 往后 跳恰好 b 个位置（即往左跳）。 它不能 连续 往后跳 2 次。 它不能跳到任何 forbidden 数组中的位置。 跳蚤可以往前跳 超…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们可以将跳蚤的位置和跳跃方向作为状态，使用 BFS 搜索最短路径。本题比较关键的地方在于确定右边界，即跳蚤最远能跳到哪里。 如果 $a \geq b$，即往前跳的距离大于往后跳的距离，那么如果跳蚤在位置大于 的地方，它就不能再往前跳了，因为跳蚤不能连续往后跳两次，如果继续往前跳，那么永远无法跳到 的位置。因此，如果 $a \geq b$，那么右边界可以是 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。
跳蚤跳跃的规则如下：
- 它可以 往前 跳恰好
a个位置（即往右跳）。 - 它可以 往后 跳恰好
b个位置（即往左跳）。 - 它不能 连续 往后跳
2次。 - 它不能跳到任何
forbidden数组中的位置。
跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。
给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。
示例 1：
输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9 输出：3 解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。
示例 2：
输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11 输出：-1
示例 3：
输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7 输出：2 解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。
提示：
1 <= forbidden.length <= 10001 <= a, b, forbidden[i] <= 20000 <= x <= 2000forbidden中所有位置互不相同。- 位置
x不在forbidden中。
解题思路
方法一：BFS
我们可以将跳蚤的位置和跳跃方向作为状态，使用 BFS 搜索最短路径。本题比较关键的地方在于确定右边界，即跳蚤最远能跳到哪里。
如果 ，即往前跳的距离大于往后跳的距离，那么如果跳蚤在位置大于 的地方，它就不能再往前跳了，因为跳蚤不能连续往后跳两次，如果继续往前跳，那么永远无法跳到 的位置。因此，如果 ，那么右边界可以是 。
如果 ，即往前跳的距离小于往后跳的距离，那么如果跳蚤所在的位置减去 超过 ，此时选择往后跳，否则往前跳。因此，如果 ，那么右边界不超过 。
综上，我们可以将右边界设置为 。
接下来，我们使用 BFS 搜索最短路径。我们使用一个队列，初始时将跳蚤的位置和跳跃方向作为状态加入队列。每次从队列中取出一个状态，如果该状态的位置等于 ，那么我们就找到了一条从初始状态到达目标状态的路径，返回当前的步数即可。否则，我们将当前状态的下一个状态加入队列，下一个状态有两种情况：
- 往前跳，跳跃方向为 ；
- 当前跳跃方向为 时，往后跳，跳跃方向为 。
注意，我们需要判断下一个状态是否合法，即下一个状态的位置不超过右边界，且不在禁止的位置中，且未被访问过。
如果队列为空，说明无法到达目标位置，返回 。
时间复杂度 ，空间复杂度 。其中 是右边界，本题中 。
class Solution:
def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
s = set(forbidden)
q = deque([(0, 1)])
vis = {(0, 1)}
ans = 0
while q:
for _ in range(len(q)):
i, k = q.popleft()
if i == x:
return ans
nxt = [(i + a, 1)]
if k & 1:
nxt.append((i - b, 0))
for j, k in nxt:
if 0 <= j < 6000 and j not in s and (j, k) not in vis:
q.append((j, k))
vis.add((j, k))
ans += 1
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate an understanding of BFS and dynamic programming.
- question_mark
Look for the ability to efficiently handle state transitions without revisiting forbidden positions.
- question_mark
Candidates should be comfortable thinking of the problem as a graph traversal challenge.
常见陷阱
外企场景- error
Failing to properly mark forbidden positions, leading to unnecessary loops in the BFS.
- error
Misunderstanding the jump constraints, especially the ability to jump past the target.
- error
Not considering the backward jumps in the BFS search, which could lead to missing a solution.
进阶变体
外企场景- arrow_right_alt
Change the jumping lengths a and b to test scalability.
- arrow_right_alt
Introduce more complex forbidden position patterns.
- arrow_right_alt
Increase the target position x for larger-scale problems.