青蛙过河 图解题解

这道题到底在问什么

输入

stones=[0,1,3,5,6,8,12,17]

输出

true(存在一条可达路径)

输入

stones=[0,1,2,3,4,8,9,11]

输出

false(中间缺口过大)

最优解：一步一步想明白

1. 3记住「jumps[x] 记到 x 的步长、每步尝试 k−1/k/k+1、落在石子就记下、碰到终点即 true」,下面逐石子套它。
2. 4初始化:jumps[0]={0}。这个「0」是技巧:它让第一跳的步长 nk=0+1=1 恰好满足「首跳为 1」的规则。
3. 5处理石子 0(紫):它的步长集合是 {0}。对每个 k,试着往前跳 k−1、k、k+1。
4. 6从 0 用步长 1 跳到石子 1(绿)。把步长 1 记进 jumps[1],以后从 1 还能继续往前。
5. 7处理石子 1(紫):它的步长集合是 {1}。对每个 k,试着往前跳 k−1、k、k+1。
6. 8从 1 用步长 1 会落到 2,但那里没有石子,这一跳不行。
7. 9从 1 用步长 2 跳到石子 3(绿)。把步长 2 记进 jumps[3],以后从 3 还能继续往前。
8. 10处理石子 3(紫):它的步长集合是 {2}。对每个 k,试着往前跳 k−1、k、k+1。
9. 11从 3 用步长 1 会落到 4,但那里没有石子,这一跳不行。
10. 12从 3 用步长 2 跳到石子 5(绿)。把步长 2 记进 jumps[5],以后从 5 还能继续往前。
11. 13从 3 用步长 3 跳到石子 6(绿)。把步长 3 记进 jumps[6],以后从 6 还能继续往前。
12. 14处理石子 5(紫):它的步长集合是 {2}。对每个 k,试着往前跳 k−1、k、k+1。
13. 15从 5 用步长 1 跳到石子 6(绿)。把步长 1 记进 jumps[6],以后从 6 还能继续往前。
14. 16从 5 用步长 2 会落到 7,但那里没有石子,这一跳不行。
15. 17从 5 用步长 3 跳到石子 8(绿)。把步长 3 记进 jumps[8],以后从 8 还能继续往前。
16. 18处理石子 6(紫):它的步长集合是 {1, 3}。对每个 k,试着往前跳 k−1、k、k+1。
17. 19从 6 用步长 1 会落到 7,但那里没有石子,这一跳不行。
18. 20从 6 用步长 2 跳到石子 8(绿)。把步长 2 记进 jumps[8],以后从 8 还能继续往前。
19. 21从 6 用步长 2 跳到石子 8(绿)。它的集合里已有 2。
20. 22从 6 用步长 3 会落到 9,但那里没有石子,这一跳不行。
21. 23从 6 用步长 4 会落到 10,但那里没有石子,这一跳不行。
22. 24处理石子 8(紫):它的步长集合是 {2, 3}。对每个 k,试着往前跳 k−1、k、k+1。
23. 25从 8 用步长 1 会落到 9,但那里没有石子,这一跳不行。
24. 26从 8 用步长 2 会落到 10,但那里没有石子,这一跳不行。
25. 27从 8 用步长 3 会落到 11,但那里没有石子,这一跳不行。
26. 28从 8 用步长 2 会落到 10,但那里没有石子,这一跳不行。
27. 29从 8 用步长 3 会落到 11,但那里没有石子,这一跳不行。
28. 30从 8 用步长 4 跳到石子 12(绿)。把步长 4 记进 jumps[12],以后从 12 还能继续往前。
29. 31处理石子 12(紫):它的步长集合是 {4}。对每个 k,试着往前跳 k−1、k、k+1。
30. 32从 12 用步长 3 会落到 15,但那里没有石子,这一跳不行。
31. 33从 12 用步长 4 会落到 16,但那里没有石子,这一跳不行。
32. 34从 12 用步长 5 正好跳到终点 17!青蛙过河成功,直接返回 true。
33. 35回放一条可行路径:0→1→3→5→8→12→17,每一跳的步长都满足「上一跳 ±1」的规则,最终落在终点 17。答案 true。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import defaultdict
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        stone_set = set(stones)
        jumps = defaultdict(set)
        jumps[0].add(0)
        last = stones[-1]
        for x in stones:
            for k in list(jumps[x]):
                for nk in (k - 1, k, k + 1):
                    if nk > 0 and x + nk in stone_set:
                        if x + nk == last:
                            return True
                        jumps[x + nk].add(nk)
        return last == 0

#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_set<int> pos(stones.begin(), stones.end());
        unordered_map<int, unordered_set<int>> jumps;
        jumps[0].insert(0);
        int last = stones.back();
        for (int x : stones) {
            auto cur = jumps[x];
            for (int k : cur) for (int nk : {k - 1, k, k + 1}) if (nk > 0 && pos.count(x + nk)) {
                if (x + nk == last) return true;
                jumps[x + nk].insert(nk);
            }
        }
        return false;
    }
};

import java.util.*;
class Solution {
    public boolean canCross(int[] stones) {
        Set<Integer> pos = new HashSet<>();
        for (int x : stones) pos.add(x);
        Map<Integer, Set<Integer>> jumps = new HashMap<>();
        jumps.computeIfAbsent(0, k -> new HashSet<>()).add(0);
        int last = stones[stones.length - 1];
        for (int x : stones) {
            for (int k : new HashSet<>(jumps.getOrDefault(x, Collections.emptySet()))) {
                for (int nk = k - 1; nk <= k + 1; nk++) if (nk > 0 && pos.contains(x + nk)) {
                    if (x + nk == last) return true;
                    jumps.computeIfAbsent(x + nk, t -> new HashSet<>()).add(nk);
                }
            }
        }
        return false;
    }
}

复杂度

面试官可能追问