LeetCode 403. 青蛙过河

2022-09-20 HGNULB 约 9 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 403. 青蛙过河

题意分析

河面上有一串石头，位置由升序数组 stones 给出，青蛙从第一块（位置 $0$）出发，只能落在石头上，问能否到达最后一块。

规则的核心是跳跃距离受上一跳约束：如果上一次跳了 $k$ 个单位，这一次只能跳 $k-1$、$k$ 或 $k+1$ 个单位，而且只能向前跳。第一次跳跃必须恰好是 $1$ 个单位。

这条规则给出的最重要信号是：光知道青蛙站在哪块石头上还不够，还必须知道它是以多大的步长跳上来的——同一块石头，用不同步长抵达，后续能去的地方完全不同。也就是说状态天然是二元的。

边界需要注意几点。石头位置的间隔可以很大（题目允许位置到 $2^{31}-1$），所以不能按坐标开数组，只能按石头本身建索引。步长不能为 $0$ 或负数，也就是青蛙不能原地不动或往回跳。石头数量只有一块时（只有位置 $0$）青蛙已经在终点，答案为真。如果第二块石头不在位置 $1$，青蛙第一跳就迈不出去，必然失败。

解法：哈希表 + 逐步扩展

核心思路

先想暴力：从起点出发做深度优先搜索，每一步枚举三种步长，走到哪算哪。问题在于同一个「石头 + 步长」的组合会被反复到达，搜索树规模呈指数增长。

瓶颈的根源是没有记忆化，而要做记忆化就必须先把状态定准。关键观察就是上面说的那条：青蛙的处境完全由「当前所在石头」和「刚才跳的步长」这一对信息决定，与它之前经过哪些石头无关。这是一个标准的无后效性结构。

于是把状态定义为布尔量：$reach[p][k]$ 表示青蛙能够以步长 $k$ 恰好落在位置 $p$ 的石头上。初始状态是 $reach[0][0] = \text{true}$，用步长 $0$ 表示「还没起跳」这个虚拟状态——它的三个后继是 $-1$、$0$、$1$，前两个因非正被过滤，只剩下 $1$，恰好自动满足了「第一跳必须为 $1$」的规则，不需要任何特判。

转移是正向推：若 $reach[p][k]$ 为真，则对 $k' \in {k-1, k, k+1}$ 中所有正数，只要位置 $p + k'$ 上有石头，就把 $reach[p+k'][k']$ 置真。答案是最后一块石头对应的步长集合是否非空。

存储上，由于坐标稀疏，用「位置到步长集合」的哈希表而不是二维数组。同时注意到步长恒为正，转移目标位置严格大于当前位置，所以只要按石头位置升序遍历，处理到某块石头时它的步长集合就已经被之前所有石头填充完毕，一遍扫描即可，无需队列或递归。

解题步骤

先为每块石头在哈希表里建一个空的步长集合。预先建好而不是用到时再建，一来让后面的「目标位置是否有石头」退化成一次 containsKey 查询，二来避免边遍历边插入新键。

把起点的集合初始化为只含 $0$。这个 $0$ 是虚拟起跳步长，作用是让第一跳被自动限制成 $1$ 个单位。

按石头位置从小到大遍历。升序是正确性的前提：转移永远指向更大的位置，因此当扫到某块石头时，所有可能指向它的转移都已经执行完毕，它的步长集合已是最终形态。

对当前石头的每个可达步长 $k$，枚举 $\delta \in {-1, 0, 1}$ 得到候选新步长 $k + \delta$。跳过所有非正的候选，因为青蛙不能原地停留也不能后退。

计算落点 $p + (k+\delta)$，若哈希表中存在这个位置就把新步长加入该位置的集合。集合会自动去重，同一「石头 + 步长」组合只保留一份，这正是记忆化生效的地方。

遍历结束后检查最后一块石头的步长集合是否非空，非空即表示存在某种步长能落到终点。用「集合非空」而非某个具体步长判断，是因为题目只问能否到达，不关心以什么姿势到达。

以 [0,1,3,5,6,8,12,17] 走一遍：初始化后 $reach[0] = {0}$，其余石头集合为空。处理位置 $0$：唯一步长 $0$，候选新步长为 $-1$、$0$、$1$，前两个被过滤，落点 $0+1=1$ 是石头，得 $reach[1] = {1}$。处理位置 $1$：步长 $1$ 的候选是 $0$（过滤）、$1$（落点 $2$，不是石头）、$2$（落点 $3$，是石头），得 $reach[3] = {2}$。处理位置 $3$：步长 $2$ 的候选是 $1$（落点 $4$，不是石头）、$2$（落点 $5$，是石头）、$3$（落点 $6$，是石头），得 $reach[5] = {2}$、$reach[6] = {3}$。处理位置 $5$：步长 $2$ 的候选是 $1$（落点 $6$，是石头，$reach[6]$ 扩充为 ${3,1}$）、$2$（落点 $7$，不是石头）、$3$（落点 $8$，是石头，得 $reach[8] = {3}$）。处理位置 $6$：步长 $3$ 的候选是 $2$（落点 $8$，$reach[8]$ 扩充为 ${3,2}$）、$3$（落点 $9$，无）、$4$（落点 $10$，无）；步长 $1$ 的候选是 $0$（过滤）、$1$（落点 $7$，无）、$2$（落点 $8$，已在集合中）。处理位置 $8$：步长 $3$ 的候选是 $2$（落点 $10$，无）、$3$（落点 $11$，无）、$4$（落点 $12$，是石头，得 $reach[12] = {4}$）；步长 $2$ 的候选是 $1$、$2$、$3$，落点分别是 $9$、$10$、$11$，都不是石头。处理位置 $12$：步长 $4$ 的候选是 $3$（落点 $15$，无）、$4$（落点 $16$，无）、$5$（落点 $17$，是石头，得 $reach[17] = {5}$）。处理位置 $17$：三个候选落点都超出所有石头。最终 $reach[17] = {5}$ 非空，返回 true。对应的路径是 $0 \to 1 \to 3 \to 5 \to 8 \to 12 \to 17$，步长依次为 $1, 2, 2, 3, 4, 5$，每一步与上一步之差都在允许范围内。

代码实现

// 从起点 0 出发，初始步长为 0。
class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> reach = new HashMap<>();
        for (int stone : stones) {
            reach.put(stone, new HashSet<>());
        }

        reach.get(0).add(0);

        for (int stone : stones) {
            Set<Integer> steps = reach.get(stone);
            for (int k : steps) {
                for (int delta = -1; delta <= 1; delta++) {
                    int nextStep = k + delta;
                    if (nextStep <= 0) {
                        continue;
                    }

                    int nextPos = stone + nextStep;
                    if (reach.containsKey(nextPos)) {
                        reach.get(nextPos).add(nextStep);
                    }
                }
            }
        }

        return !reach.get(stones[stones.length - 1]).isEmpty();
    }
}

// 从起点 0 出发，初始步长为 0。
func canCross(stones []int) bool {
    reach := make(map[int]map[int]bool, len(stones))
    for _, stone := range stones {
        reach[stone] = make(map[int]bool)
    }

    reach[0][0] = true

    for _, stone := range stones {
        for step := range reach[stone] {
            for delta := -1; delta <= 1; delta++ {
                nextStep := step + delta
                if nextStep <= 0 {
                    continue
                }

                nextPos := stone + nextStep
                if _, ok := reach[nextPos]; ok {
                    reach[nextPos][nextStep] = true
                }
            }
        }
    }

    return len(reach[stones[len(stones)-1]]) > 0
}

复杂度分析

时间复杂度：$O(n^2)$，$n$ 为石头数量。落在第 $i$ 块石头上的步长必然不超过 $i$（每跳最多让步长加一，且跳跃次数不超过已经过的石头数），因此每块石头的步长集合大小是 $O(n)$，全部状态数为 $O(n^2)$；每个状态只向外扩展常数条边，哈希查询按均摊 $O(1)$ 计。

空间复杂度：$O(n^2)$，哈希表为每块石头维护一个步长集合，所有集合的元素总数与状态数同阶。

关键点总结

判断状态是否完备的方法是问「知道这些信息，接下来能做什么就完全确定了吗」。这题只记位置会漏掉步长约束，只记步长会漏掉落点，两者缺一不可，这是全题的核心考点。

坐标稀疏而状态稠密时，用哈希表按实际出现的键索引，比按坐标范围开数组更合适。这里位置上界高达 $2^{31}-1$，开数组直接不可行。

用一个「虚拟初始步长 $0$」代替对首跳的特判，是很值得学的技巧。它让初始状态和普通状态共用同一套转移代码，减少了分支也减少了出错面。

转移方向单调（步长恒为正，落点严格向前）时，正向递推按序遍历一遍即可，不需要队列、递归或拓扑排序。识别出这种单调性能显著简化实现。

面试视角：面试官最想看到的是你从「只记位置」的错误状态定义中自己走出来。可以主动举一个反例——同一块石头用步长 $2$ 和步长 $4$ 抵达，后续可达集合完全不同——来说明为什么必须加维。

面试视角：常见追问是「递归加记忆化怎么写」以及「状态数上界为什么是 $O(n^2)$」。前者要说清记忆化的键是「位置 + 步长」二元组，后者要说清步长受跳跃次数限制。

易错点总结

错误写法：状态只记录位置、用一个布尔数组表示「这块石头能不能到」 → 抵达同一块石头的步长可能有好几种，后续可选范围完全不同，只记位置等于默许青蛙从任意步长继续，会把 [0,1,2,3,4,8,9,11] 这类真正过不去的输入判成可达。

错误写法：过滤条件写成 nextStep < 0 从而放行步长 $0$ → 落点等于当前位置，Java 侧在遍历该石头的步长集合时向同一个集合插入元素，直接抛并发修改异常；即使换成安全容器，也白白多出一批无意义状态。

错误写法：不检查落点是否为石头就直接写入哈希表 → 会凭空为水面位置创建集合，青蛙相当于能落水前进，[0,2] 这类必然失败的输入也会返回 true。

错误写法：不按位置升序遍历石头，或用无序容器承载遍历顺序 → 处理某块石头时它的步长集合可能还没被填满，转移丢失，[0,1,3,5,6,8,12,17] 会被错判为 false。

错误写法：起点初始化为 $reach[0] = {1}$ 并额外特判首跳 → 相当于允许第一跳后的第二跳用步长 $0$ 到 $2$，对 [0,2] 会误判为可达；正确做法是初始步长填 $0$，让过滤规则自然生效。

错误写法：起点用 reach.get(0).add(1) 之类写法却没先建好该键 → 哈希表里位置 $0$ 的集合尚不存在，get 返回空引用后调用 add 直接崩溃；预先为所有石头建空集合能一次性消除这类问题。

错误写法：用位置数组下标当哈希键 → 转移时算出的是绝对坐标，需要再做一次坐标到下标的映射，漏掉这层转换会让 containsKey 恒为真或恒为假。

错误写法：最终判断写成「最后一块石头的集合中包含某个特定步长」 → 题目只问能否到达，任何步长落到终点都算成功，限定具体步长会漏解。

错误写法：只有一块石头时不做处理直接返回集合非空 → 起点集合含虚拟步长 $0$ 恰好非空，本例返回 true 是对的，但若把初始集合改成空集则会错判为 false，两处实现必须保持一致。

错误写法：用回溯搜索且不加记忆化 → 对 $2000$ 块石头的稠密数据，同一「位置 + 步长」组合被重复展开，运行时间指数增长直接超时。

相似题目

题目	难度	考察点
1306. 跳跃游戏 III	中等	步长由数组值给定且可双向跳，状态只需位置，用广度优先即可
55. 跳跃游戏	中等	步长上界固定，可用贪心维护最远可达位置，无需二维状态
45. 跳跃游戏 II	中等	求最少跳数，按层扩展的贪心把复杂度压到线性
139. 单词拆分	中等	同为可达性递推，转移来源是字典而非受约束的步长
322. 零钱兑换	中等	转移集合固定不随历史变化，因此状态退化为一维