到家的最少跳跃次数

难度: Medium

有一只跳蚤的家在数轴上的位置 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 <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
forbidden 中所有位置互不相同。
位置 x 不在 forbidden 中。

Submission

运行时间: 35 ms

内存: 16.5 MB

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        # bfs用队列
        q, visited = collections.deque([[0, 1, 0]]), set([0])
        lower, upper = 0, max(max(forbidden) + a, x) + b
        forbiddenSet = set(forbidden)
        while q:
            position, direction, step = q.popleft()
            if position == x:
                return step
            nextPosition = position + a
            nextDirection = 1
            if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:
                # 继续往前
                visited.add(nextPosition * nextDirection)
                q.append([nextPosition, nextDirection, step + 1])
            if direction == 1:
                nextPosition = position - b
                nextDirection = -1
                if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:
                    visited.add(nextPosition * nextDirection)
                    q.append([nextPosition, nextDirection, step + 1])
        return -1

Explain

这个题解使用了宽度优先搜索（BFS）算法来解决最少跳跃次数的问题。首先定义一个队列来存储每一步的位置、跳跃方向和步数。使用一个集合来记录已访问的位置防止重复处理。算法从位置0开始，尝试每次往前跳a个位置或往后跳b个位置，同时确保跳跃后的位置不是禁止位置并且在有效的范围内。为了避免连续两次往后跳，算法使用方向标志来控制。如果到达目标位置x，则返回所需的最小步数。如果所有可能的位置都被探索过后还没有找到到达x的路径，则返回-1。

时间复杂度: O(n)

空间复杂度: O(n)

# 定义Solution类
class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        # 初始化队列和访问集合
        q, visited = collections.deque([[0, 1, 0]]), set([0])
        # 定义有效范围
        lower, upper = 0, max(max(forbidden) + a, x) + b
        forbiddenSet = set(forbidden)
        # 开始BFS
        while q:
            position, direction, step = q.popleft()
            # 检查是否到达目的地
            if position == x:
                return step
            # 尝试向前跳
            nextPosition = position + a
            nextDirection = 1
            if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:
                visited.add(nextPosition * nextDirection)
                q.append([nextPosition, nextDirection, step + 1])
            # 如果之前是向前跳，尝试向后跳
            if direction == 1:
                nextPosition = position - b
                nextDirection = -1
                if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:
                    visited.add(nextPosition * nextDirection)
                    q.append([nextPosition, nextDirection, step + 1])
        # 所有可能都试过仍无法到达目的地
        return -1

Explore

在BFS过程中使用方向标志主要是为了控制跳蚤的跳跃方向，确保跳蚤不会连续两次向后跳跃。这个方向标志有助于记录每一次跳跃后跳蚤的状态（向前或向后），从而在下一次跳跃决策中使用这个信息防止连续向后跳。在算法实现中，如果方向标志为正（即之前是向前跳），则跳蚤可以选择继续向前跳或改变方向向后跳；如果方向标志为负（即之前是向后跳），则跳蚤只能选择向前跳。这种控制确保了跳蚤的移动符合题目要求的规则。

题解中确保跳蚤不会在禁止位置上落地的方法是通过在每次跳跃前检查目标位置是否在禁止集合（forbiddenSet）中。在BFS算法的每一步中，当计算出下一个可能的位置（无论是向前还是向后跳）后，算法会首先检查这个位置是否存在于forbiddenSet中。如果位置在禁止集合内，则这次跳跃不会被执行，即这个位置不会被加入到队列中进行进一步的探索。这样可以确保所有进行探索的位置都不是禁止位置。

在题解的BFS算法中，实现跳蚤无法连续两次往后跳的规则是通过在队列中保存跳蚤的当前方向（direction变量）来控制的。当跳蚤向前跳时（direction为1），它可以选择继续向前跳或改变方向向后跳。一旦跳蚤向后跳了（此时direction为-1），在下一个循环中，算法会检查当前的方向，并只允许跳蚤向前跳。这是通过在处理队列元素时对direction进行判断并决定下一步的可行动作来实现的。具体来说，只有当direction为1时，跳蚤才有可能执行向后跳的动作。

在题解的BFS算法中，处理已访问位置的方法是通过一个访问集合（visited set）来记录所有已经被访问的位置。每次计算出一个新的可能位置时，算法会检查这个位置是否已经存在于visited集合中。如果已经访问过，那么这个位置将不会被再次加入到队列中用于进一步的探索。这样做可以避免重复处理相同的位置，从而优化算法的效率并防止无限循环的发生。