LeetCode 403. 青蛙过河
题目描述
题意分析
石头位置严格递增，青蛙从位置 0 出发，第一跳必须为 1。若上一跳长度为
k，下一跳只能为k - 1、k或k + 1，并且必须向前落在石头上，判断能否到达最后一块石头。
解法：哈希表 + 逐步扩展
核心思路
[!blue]
只知道某块石头可达还不够：用不同步长到达这里，会得到不同的下一跳选择。状态必须同时记录「当前石头位置」和「上一跳长度」，而相同的这两个量对应完全相同的后续选择，可以合并去重。
用
reach[position]保存能够到达该石头的所有步长。只为实际存在的石头建立集合，既能判断落点是否在水面上，也不用按可能很大的坐标范围开数组。初始只向reach[0]加入虚拟步长 0；枚举下一步并过滤非正数后，只剩长度 1，正好满足首跳要求。对每个可达状态
(position, k)，尝试k - 1、k、k + 1。只有步长为正且position + nextStep确实有石头时，才把nextStep加入目标石头的集合。这些条件保证新增状态都对应合法的一跳；反过来，任何合法跳跃也一定是这三种选择之一，因此不会遗漏路径。所有转移都指向更大的位置，按石头升序处理时，当前集合已经收到全部可能的前驱状态，之后也不会再被补充。它的转移只会修改未来石头的集合，不会修改正在遍历的集合。处理完后，只要最后一块石头的集合非空，就存在一条到达它的路径。
解题步骤
- 为每块石头建立空集合，并向起点集合加入 0。
- 按石头位置升序，枚举它的每个可达步长；空集合表示目前不可达，无需扩展。
- 枚举三种下一跳长度，跳过非正长度和不存在的落点，将合法步长加入目标集合。
- 返回最后一块石头的集合是否非空，不要求必须经过中间的每块石头。
代码实现
// 从起点 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)$。每跳最多增加 1，且向前最多经过
n - 1次跳跃，因此步长只有 $O(n)$ 种；每块石头的每个步长只做三次哈希操作。- 空间复杂度：$O(n^2)$，保存位置与步长状态。
关键点总结
[!green]
- 位置与上一跳长度共同决定后续选择，不能只按位置去重。
- 正步长让转移只写未来石头，保证升序处理的正确性，也避免修改当前集合。
- 存在性只看末石能否以任意步长到达。
易错点总结
[!yellow]
- 只记录位置，丢失后续跳跃限制。
- 起点步长设为 1 会让统一转移允许首次跳 2；应使用虚拟步长 0。
- 为水面创建新位置，改变了只能落石头的规则。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！