LeetCode 1654. 到家的最少跳跃次数

2022-08-12 HGNULB 约 10 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 1654. 到家的最少跳跃次数

题意分析

一只跳蚤站在数轴的 0 点，只有两种动作可选：向右固定跳 a 格，或者向左固定跳 b 格。要求它落到位置 x 上，问最少需要几次动作，永远落不到就返回 -1。

约束里给了两条硬规则。第一条是禁跳位置一个都不能踩，无论向左还是向右落到它上面都算违规；第二条是不能连着两次向左跳，中间必须夹一次向右跳。第二条规则意味着「当前站在哪」并不足以决定接下来能做什么，还得知道上一步是往哪个方向跳的。

坐标不允许变成负数，但允许先冲过 x 再退回来，所以可行的落点范围比 x 本身要宽，必须给出一个足够大的搜索上界。另一个容易漏的边界是起点本身：如果目标就是 0，一次都不用跳。

题目保证 x 不在禁跳列表里，禁跳位置和 a、b 都不超过 2000，规模很小，允许把每个合法落点都摸一遍。

解法：带方向状态的 BFS

核心思路

最朴素的想法是枚举所有跳跃序列：每一步二选一，递归下去直到踩中 x。问题是序列长度没有天然上限，同一个位置会被成千上万条不同路径重复展开，代价是指数级的，连样例都跑不完。

瓶颈在于「路径」这个维度是多余的。两条路径如果最终停在同一个位置、并且上一步的方向也相同，那么它们之后能做的动作完全一致，区别只在于已经花了多少步。既然只关心最少步数，就只需要保留最先到达的那一条。

于是把状态压缩成二元组 $(pos, back)$：$pos$ 是当前坐标，$back$ 取 0 表示上一步是向右跳（或者还没跳过），取 1 表示上一步是向左跳。$back = 1$ 时禁止再向左，这就把「不能连续后跳」这条规则完全吸收进了状态里。

每次跳跃的代价都是 1，边权均等，因此按层扩展时首次弹出某个状态的层号就是到达它的最少步数。这里的不变量是：队列里同一层的所有状态，其最短步数都等于当前层号；而 visited[pos][back] 一旦被置为真，就说明这个状态的最短步数已经被锁定，后来的任何路径都不可能更短。

最后还缺一个位置上界，否则向右跳可以无限延伸。取 $limit = \max(x, maxForbidden) + a + b$：超过这条线以后右侧再没有任何障碍，多往右一格只会让「最终必须退回 x」这段路更长，不可能比留在界内的走法更优，因此把界外的点全部剪掉不会丢解。

解题步骤

把 forbidden 里的位置塞进哈希集合，同时顺手记下其中的最大值。用集合是为了让后面每次落点检查都是 $O(1)$；记最大值是因为搜索上界必须覆盖所有障碍，否则障碍右边那段安全区就被误剪了。

计算 $limit = \max(x, maxForbidden) + a + b$，开二维数组 visited[limit + 1][2]。第二维就是上一步的方向，少了这一维就会把两种后续选择不同的情形混为一谈。

把 $(0, 0)$ 入队并标记，steps 置 0。起点还没跳过，等价于「上一步不是向左跳」，所以第二维填 0。

按层循环：每轮先记下当前队列长度 size，只处理这么多个元素，处理完再让 steps 自增 1。这样保证同一批出队的状态确实属于同一层。

出队时先判断 pos == x 就返回 steps。判断放在出队而不是入队，是为了让起点等于目标这种情形也能被正确覆盖。

尝试向右跳到 pos + a：只有不越上界、不是禁跳位置、并且 visited[pos + a][0] 还没被标记时才入队，入队的同时立刻打标记。入队即标记而不是出队才标记，可以避免同一状态在同一层被多个前驱重复塞进队列。

只有当 jumpedBack == 0 时才尝试向左跳到 pos - b，并额外检查 pos - b >= 0，入队时第二维填 1。这一条把规则限制落到了实处：负坐标非法，连续左跳非法。

队列彻底耗尽仍没碰到 x，说明合法状态已经穷举完毕，返回 -1。

以 forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9 走一遍：集合是 ${14,4,18,1,15}$，最大障碍 18，于是 $limit = \max(9, 18) + 3 + 15 = 36$。初始队列 $[(0,0)]$，steps = 0。第 0 层弹出 $(0,0)$，$0 \ne 9$；向右到 3，3 未被禁且未访问，入队并标记 visited[3][0]；向左到 $0 - 15 = -15 < 0$，放弃。steps 变成 1。第 1 层弹出 $(3,0)$，$3 \ne 9$；向右到 6，合法，入队标记 visited[6][0]；向左到 $3 - 15 = -12 < 0$，放弃。steps 变成 2。第 2 层弹出 $(6,0)$，$6 \ne 9$；向右到 9，9 不在禁跳集合里，入队标记 visited[9][0]；向左到 $6 - 15 = -9 < 0$，放弃。steps 变成 3。第 3 层弹出 $(9,0)$，此时 $pos = x$，返回 3。整条路径是 $0 \to 3 \to 6 \to 9$，一次向左跳都没用上，正是因为 $b = 15$ 比 $a = 3$ 大得多，向左只会倒退。

代码实现

class Solution {
    // 同一个位置在 "上一步是否向后跳" 两种状态下后续选择不同，访问标记必须区分这两类状态。
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> blocked = new HashSet<>();
        int maxForbidden = 0;
        for (int pos : forbidden) {
            blocked.add(pos);
            maxForbidden = Math.max(maxForbidden, pos);
        }

        int limit = Math.max(x, maxForbidden) + a + b;
        boolean[][] visited = new boolean[limit + 1][2];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {0, 0});
        visited[0][0] = true;

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int pos = cur[0];
                int jumpedBack = cur[1];

                if (pos == x) {
                    return steps;
                }

                int forward = pos + a;
                if (forward <= limit && !blocked.contains(forward) && !visited[forward][0]) {
                    visited[forward][0] = true;
                    queue.offer(new int[] {forward, 0});
                }

                if (jumpedBack == 0) {
                    int backward = pos - b;
                    if (backward >= 0 && !blocked.contains(backward) && !visited[backward][1]) {
                        visited[backward][1] = true;
                        queue.offer(new int[] {backward, 1});
                    }
                }
            }
            steps++;
        }

        return -1;
    }
}

func minimumJumps(forbidden []int, a int, b int, x int) int {
    // 同一个位置在 "上一步是否向后跳" 两种状态下后续选择不同，访问标记必须区分这两类状态。
    blocked := make(map[int]struct{})
    maxForbidden := 0
    for _, pos := range forbidden {
        blocked[pos] = struct{}{}
        if pos > maxForbidden {
            maxForbidden = pos
        }
    }

    limit := maxInt(x, maxForbidden) + a + b
    visited := make([][2]bool, limit+1)
    queue := make([][2]int, 0)
    queue = append(queue, [2]int{0, 0})
    visited[0][0] = true

    steps := 0
    for head := 0; head < len(queue); {
        size := len(queue) - head
        for i := 0; i < size; i++ {
            cur := queue[head]
            head++
            pos := cur[0]
            jumpedBack := cur[1]

            if pos == x {
                return steps
            }

            forward := pos + a
            if forward <= limit && !contains(blocked, forward) && !visited[forward][0] {
                visited[forward][0] = true
                queue = append(queue, [2]int{forward, 0})
            }

            if jumpedBack == 0 {
                backward := pos - b
                if backward >= 0 && !contains(blocked, backward) && !visited[backward][1] {
                    visited[backward][1] = true
                    queue = append(queue, [2]int{backward, 1})
                }
            }
        }
        steps++
    }

    return -1
}

func contains(blocked map[int]struct{}, pos int) bool {
    _, ok := blocked[pos]
    return ok
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：$O(U)$，其中 $U = \max(x, maxForbidden) + a + b$。状态总数是 $2U$ 级别，每个状态只在首次访问时入队一次，出队后只做两次 $O(1)$ 的落点检查，所以总工作量与状态数同阶；建集合的 $O(m)$ 被它吸收。

空间复杂度：$O(U)$，visited 是 $2 \times (U + 1)$ 的布尔表，队列最坏也要装下同阶数量的状态，禁跳集合额外占 $O(m)$。

关键点总结

状态设计的准绳是「影响后续决策的全部信息」。这题只记位置不够，必须补上「上一步方向」这一维，否则两种可行动作不同的情形会被错误地合并。

边权全为 1 是按层推最短的前提。一旦向左向右代价不同，层序就失效，得换成带优先队列的最短路。

状态空间无限时，必须先论证一个上界再开搜。$\max(x, maxForbidden) + a + b$ 之外没有障碍，右移只会增加回退距离，这个剪枝是有证明的而不是拍脑袋定的常数。

入队即标记是队列去重的标准写法，出队才标记会让同一状态被重复塞入，队列规模退化。

面试视角：这题真正的考点不是会不会写队列，而是能不能把「不能连续后跳」这条自然语言规则翻译成状态的一个维度，以及能不能说清上界为什么安全。面试官几乎必追问后者，准备好那两句论证比写完代码更加分。

易错点总结

错误写法：visited 只开一维、仅按位置去重：把「刚向左跳到 p」和「向右跳到 p」当成同一件事 → 先到的那个若恰好是左跳状态，它禁止继续左跳，后来那条允许左跳的合法分支被永久拦下，有解的用例可能被判成 -1。

错误写法：搜索上界直接取 x，认为不需要越过目标：forbidden = [10], a = 7, b = 6, x = 1 → 向右跳到 7 被上界拒绝，队列立刻耗尽返回 -1，而正确答案是 2（$0 \to 7 \to 1$）。

错误写法：上界只写 x + a + b，忽略最大禁跳位置：障碍集中在 x 右侧很远处时，障碍右边那段本可通行的安全区被整体剪掉，最短路径被迫绕远或直接判无解。

错误写法：向左跳时忘记检查 pos - b >= 0 → 直接用负数索引 visited，Java 抛 ArrayIndexOutOfBoundsException，Go 触发 panic。

错误写法：只对向右跳检查禁跳集合，向左跳不查 → 跳蚤落在被禁位置上，返回的步数比真实答案小，甚至把 -1 的用例算出有限值。

错误写法：向左跳入队时第二维仍填 0 → 下一步还能继续向左，等价于放开了「不能连续后跳」的限制，输出偏小的非法解。

错误写法：steps++ 写在内层的 for i 里面 → 同一层的每个节点都让步数自增一次，返回值变成出队序号而不是层号，结果整体偏大。

错误写法：只在入队新状态时判断是否等于 x，出队时不判 → 起点就是目标（$x = 0$）的情形谁也没检查，返回 -1 而不是 0。

错误写法：出队时才写 visited → 同一个状态可以被同层多个前驱同时入队，队列长度成倍膨胀，大用例上超时。

相似题目

题目	难度	考察点
127. 单词接龙	困难	隐式建图：邻接关系由字符串差一位定义
433. 最小基因变化	中等	字符集只有四种，邻居靠枚举替换字符生成
542. 01 矩阵	中等	多源同时入队，一趟求出全图距离场
752. 打开转盘锁	中等	死亡数字当作障碍预先塞进 visited
773. 滑动谜题	困难	整个棋盘序列化成字符串充当状态键
854. 相似度为 K 的字符串	困难	只交换首个失配位，靠贪心裁掉无效分支
909. 蛇梯棋	中等	编号与行列的蛇形互转，梯子造成跳转边
994. 腐烂的橘子	中等	层号即分钟数，还要额外校验是否有残留
1091. 二进制矩阵中的最短路径	中等	八连通网格，起点终点自身也可能被堵
1129. 颜色交替的最短路径	中等	同样把「上一条边的属性」并入状态
1162. 地图分析	中等	求的是距离场的最大值，答案在最后一层
1293. 网格中的最短路径	困难	剩余消除次数作为状态第三维
1298. 你能从盒子里获得的最大糖果数	困难	钥匙与盒子互相解锁，需要反复回收待处理集合
1345. 跳跃游戏 IV	困难	同值下标建超级边，用后即清空避免重复展开
LCP 09. 最小跳跃次数	困难	弹簧右跳可越界，需配合已处理前缀指针剪枝
LCR 107. 01 矩阵	中等	距离数组本身兼作访问标记，省掉 visited
LCR 108. 单词接龙	困难	与 127 同源，返回的是序列长度而非跳跃步数
LCR 109. 打开转盘锁	中等	状态空间固定一万，适合双向 BFS 对撞