Hard

题目描述

一只青蛙想要过河。 河流被分为若干个单元格，每个单元格内可能有一块石头，也可能没有。青蛙可以跳到石头上，但是不能跳到水中。

给你石头的位置列表 stones（用单元格序号 升序 表示），请判定青蛙能否成功过河（即能否在最后一步跳到最后一块石头上）。开始时，青蛙默认已站在第一块石头上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。另外，青蛙只能向前方向跳跃。

示例 1：

输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，跳跃路径为：1 → 2 → 2 → 3 → 4 → 5 单位。

示例 2：

输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：没有办法跳到最后一块石头，因为第 5 和第 6 个石头之间的间距太大了。

提示：

  • 2 <= stones.length <= 2000
  • 0 <= stones[i] <= 2^31 - 1
  • stones[0] == 0
  • stones 按严格升序排列

解题思路

这是一道经典的动态规划问题。我们需要考虑青蛙在每个石头上时，可能的跳跃距离状态。

核心思路：

  1. 状态定义：用哈希表记录每个石头位置可能的跳跃步数集合
  2. 状态转移：从当前石头位置，尝试跳跃 k-1、k、k+1 步，如果目标位置有石头，就更新目标位置的可能步数
  3. 边界条件：第一块石头（位置0）只能跳1步到位置1

算法流程：

  • 首先建立位置到索引的映射，便于快速查找石头是否存在
  • 初始化：位置0可以跳1步
  • 对每个石头位置，遍历其所有可能的跳跃步数，计算下一个可达位置
  • 如果下一个位置存在石头，就将对应的跳跃步数加入该位置的集合
  • 最后检查最后一块石头是否有任何可达的跳跃步数

这种方法避免了递归的重复计算，时间复杂度相对较优。当到达最后一块石头时，只要其步数集合非空，说明青蛙可以成功过河。

代码实现

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> dp;
        unordered_set<int> stoneSet;
        
        for (int stone : stones) {
            stoneSet.insert(stone);
            dp[stone] = unordered_set<int>();
        }
        
        dp[0].insert(1);
        
        for (int stone : stones) {
            for (int step : dp[stone]) {
                int nextPos = stone + step;
                if (stoneSet.count(nextPos)) {
                    if (step - 1 > 0) dp[nextPos].insert(step - 1);
                    dp[nextPos].insert(step);
                    dp[nextPos].insert(step + 1);
                }
            }
        }
        
        return !dp[stones.back()].empty();
    }
};

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        stone_set = set(stones)
        dp = {stone: set() for stone in stones}
        dp[0].add(1)
        
        for stone in stones:
            for step in dp[stone]:
                next_pos = stone + step
                if next_pos in stone_set:
                    if step - 1 > 0:
                        dp[next_pos].add(step - 1)
                    dp[next_pos].add(step)
                    dp[next_pos].add(step + 1)
        
        return len(dp[stones[-1]]) > 0

public class Solution {
    public bool CanCross(int[] stones) {
        var stoneSet = new HashSet<int>(stones);
        var dp = new Dictionary<int, HashSet<int>>();
        
        foreach (int stone in stones) {
            dp[stone] = new HashSet<int>();
        }
        
        dp[0].Add(1);
        
        foreach (int stone in stones) {
            foreach (int step in dp[stone]) {
                int nextPos = stone + step;
                if (stoneSet.Contains(nextPos)) {
                    if (step - 1 > 0) dp[nextPos].Add(step - 1);
                    dp[nextPos].Add(step);
                    dp[nextPos].Add(step + 1);
                }
            }
        }
        
        return dp[stones[stones.Length - 1]].Count > 0;
    }
}

var canCross = function(stones) {
    const stoneSet = new Set(stones);
    const dp = new Map();
    
    for (const stone of stones) {
        dp.set(stone, new Set());
    }
    
    dp.get(0).add(1);
    
    for (const stone of stones) {
        for (const step of dp.get(stone)) {
            const nextPos = stone + step;
            if (stoneSet.has(nextPos)) {
                if (step - 1 > 0) dp.get(nextPos).add(step - 1);
                dp.get(nextPos).add(step);
                dp.get(nextPos).add(step + 1);
            }
        }
    }
    
    return dp.get(stones[stones.length - 1]).size > 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
最优解法O(n²)O(n²)

说明：

  • 时间复杂度：O(n²)，其中n是石头数量。每个石头最多有O(n)种跳跃步数，总共需要处理O(n²)个状态
  • 空间复杂度：O(n²)，存储每个石头位置对应的所有可能跳跃步数集合

相关题目