0403. Frog Jump =============== 题目信息 -------- :题号: 0403 :难度: Hard :主题: 石头位置、跳跃状态、上次距离、可达性 :原题: `LeetCode 0403 `_ :重点: 起点为 0、第一跳必须为 1、后续只能跳 ``k-1``/``k``/``k+1``、每次必须落在石头上 题目重述 -------- 河中的石头位置由严格递增数组 ``stones`` 给出。青蛙站在第一块石头 ``stones[0] = 0`` 上,第一次跳跃必须恰好前进 1 个单位。 若青蛙上一次跳了 ``k`` 个单位,下一次只能向前跳 ``k-1``、``k`` 或 ``k+1`` 个单位,并且实际跳跃距离必须为正。每次跳跃都必须落在数组中的某块石头上。判断青蛙能否最终到达最后一块石头。 ``stones`` 的长度位于 ``[2, 2000]``,位置值位于 ``[0, 2^31-1]``,且互不相同并严格递增。青蛙不能向后跳,也不能停留在原地。 自建示例 -------- 跳跃距离逐步增大: .. code-block:: text 输入:stones = [0, 1, 2, 4, 7, 11] 输出:true 解释:可以依次跳 1、1、2、3、4 个单位,落点依次为 1、2、4、7、11。 下一块石头超出可选距离: .. code-block:: text 输入:stones = [0, 1, 2, 3, 7] 输出:false 解释:到达位置 3 时,任何可行路径的上次跳跃距离都不足以让下一跳直接到达 7。 状态是“石头位置 + 上一次跳距” -------------------------------- 到达同一块石头时,上一次跳跃距离不同,下一步可选的距离也不同,不能只记录石头是否访问过。为每块石头保存能够到达它的跳距集合;从状态 ``(i, k)`` 出发,尝试 ``k-1``、``k``、``k+1`` 中的正数,并把确实存在的下一块石头加入对应集合。 第一跳是特殊约束,只有位置 1 存在时才可能开始。之后所有转移都向前查找,位置映射让“落在石头上”的判断不必扫描整个数组;若最后一块石头收到任意跳距即可成功。 C++ 实现 -------- .. code-block:: cpp class Solution { public: bool canCross(std::vector& stones) { int n = static_cast(stones.size()); if (n == 2) return stones[1] == 1; std::unordered_map index; for (int i = 0; i < n; ++i) index[stones[i]] = i; if (index.count(1) == 0) return false; std::vector> jumps(n); jumps[index[1]].insert(1); for (int i = 1; i < n; ++i) { for (int last : jumps[i]) { for (int delta = -1; delta <= 1; ++delta) { int step = last + delta; if (step <= 0) continue; long long nextPosition = static_cast(stones[i]) + step; if (nextPosition > INT_MAX) continue; auto it = index.find( static_cast(nextPosition)); if (it == index.end()) continue; if (it->second == n - 1) return true; jumps[it->second].insert(step); } } } return false; } }; 代码分析 -------- 集合中的每个跳距都代表一条真实可达路径的状态;转移只使用上一次跳距,因此不会把不同路径错误合并。位置哈希表只接受实际存在的落点,第一跳单独初始化也避免把 ``k=0`` 当作普通状态。最坏状态数为 ``O(n^2)``,时间复杂度为 ``O(n^2)``,额外空间为 ``O(n^2)``。