本文共 1988 字，大约阅读时间需要 6 分钟。

为了判断是否存在一条满足条件的路径，我们可以使用动态规划的方法，记录每个石头点可达的跳跃距离集合。以下是优化后的解决方案：

方法思路

这种方法确保了每次跳跃的距离都是唯一的，并且能够高效地判断路径的存在性。

代码实现

class Solution:    def canCross(self, stones: List[int]) -> bool:        if not stones:            return False  # 如果没有石头，返回False                reachable = {}  # 记录每个石头点可达的位置集合        used = set()  # 记录已经使用的跳跃距离                # 初始化第一个位置，距离为0        reachable[stones[0]] = {0}        used.add(0)                current = stones[0]        for i in range(1, len(stones)):            # 计算可能的跳跃距离            possible_dists = []            for d in used:                next_pos = current + d                if next_pos in stones:                    # 检查是否已经被访问过                    if stones.index(next_pos) == i:                        continue  # skip自己                    if next_pos not in reachable:                        possible_dists.append(d)                        if not possible_dists:                return False  # 无法继续跳跃                        # 更新used            used.update(possible_dists)                        # 找到下一个可达的石头            next_pos = None            for pos in stones:                if pos > current and pos in reachable and (pos in reachable[current]):                    next_pos = pos                    break                        if next_pos is None:                return False                        # 标记为已访问，并更新current            reachable[current] = reachable[current] | possible_dists  # 新方式可能更好            current = next_pos                return True

代码解释

这种方法确保了每次跳跃的距离都是唯一的，并且能够高效地判断路径的存在性。

转载地址：http://hbsl.baihongyu.com/