leader小我6岁，叫哥实在叫不出口，又怕因此产生嫌隙，该怎么称呼？

这年头，刷题刷得我连梦里都在跳格子。

最近在做 LeetCode 的时候，又被一道经典老题绕住了——青蛙过河。别看题目听着挺童话，实际代码一写，那青蛙跳得比我年会抽奖还玄乎。

题目意思其实不难理解，给你一个升序数组 stones[]，表示石头在河里的位置，青蛙一开始站在 stones[0] 上，也就是 0 号石头。第一跳必须跳 1 格，然后从第二跳开始，假设上一次跳了 k，那么接下来可以跳 k-1、k 或 k+1。当然，跳距离不能为 0，也不能跳到没有石头的地方，问你青蛙能不能跳到最后一个石头上。

讲真，这题最初我想用暴力递归干它，写了几层 if 后我人都麻了。果然暴力是青春的火焰，烧得 CPU 都冒烟。

但后来看了看这题的数据规模，石头数量大概最多 2000 个，还是得上效率。于是我换成了 DFS + 记忆化 + 哈希表记录状态，关键点是不能重复跳，得记住当前位置和上一次跳的距离。

我上代码：

publicclassFrogCrossRiver {
publicbooleancanCross(int[] stones) {
        Map<Integer, Set<Integer>> map = newHashMap<>();
for (int stone : stones) {
            map.put(stone, newHashSet<>());
        }
        map.get(0).add(0); // 起点的跳跃距离是0

for (int stone : stones) {
for (int k : map.get(stone)) {
for (intstep= k - 1; step <= k + 1; step++) {
if (step > 0 && map.containsKey(stone + step)) {
                        map.get(stone + step).add(step);
                    }
                }
            }
        }

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

这个写法其实挺精巧的，核心思路是用 Map 来记录每个石头位置当前能通过哪些步长到达，然后一步一步去更新后面的石头。到了最后一个石头，只要有能跳过去的步长，就说明青蛙过得去。

我个人觉得这题最坑的一点是，不能跳距离为 0，一不留神就容易陷入死循环，还得小心 k-1 跳成了 0，然后 Debug 一小时最后发现青蛙原地打转。

不过写完这题我有点感慨，青蛙跳河不就是程序员找工作跳槽嘛？你得先有一个“靠谱的起点”，然后每次跳要不是跟上次差不多，要不是略高点，不能一下跳太远也不能跳到不存在的“offer”上，现实比这题还狠，一跳错就是火坑。

而且每个石头能不能到达都跟你前面的“跳法”密切相关，做题就像做人，选对第一跳很关键，跳错了可能就被卡死在中间格子里——比如跳到了 996 岗或者是天天开会没时间写代码的产品运营岗。

当然，这题也不是不能用递归写，只是递归+记忆化的时候记忆的 key 要注意用一个二维的状态：当前位置和步长。有些同学写 Set<String> 来记忆 (position, jump) 结果也行，只不过 Java 的字符串拼接那点性能我是真的服。

最后多嘴一句，这题也能拿来考状态压缩，不过我觉得不到必要不要折腾自己。日常面试要么是让你写个版本，要么就是看你思路，搞那么复杂面试官都得扒你源码才知道你在干嘛。

总之这道题我觉得还是蛮能考察思维逻辑的，模拟+状态更新+边界判断都要考虑清楚。青蛙能不能过河不重要，关键是你写代码的时候有没有跳进坑里再跳不出来。

写完这题我现在看到青蛙都想问一句：“兄弟你下次要去哪家公司？”