LeetCode 403. 青蛙过河

Categories:

题目描述
思路分析
1. 解法一：哈希表 + 逐步扩展（推荐）
相似题目

题目描述

✅ 403. 青蛙过河

思路分析

解法一：哈希表 + 逐步扩展（推荐）

核心思路：

用哈希表记录每个石头位置能到达的跳跃步长集合。

从起点 0 出发，初始步长为 0。

对每个石头与其可达步长 k，尝试跳 k-1、k、k+1（大于 0），若目标位置存在则记录。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示石头数量。

空间复杂度：O(n^2)，用于存储跳跃步长集合。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> reach = new HashMap<>();
        for (int stone : stones) {
            reach.put(stone, new HashSet<>());
        }

        reach.get(0).add(0);

        for (int stone : stones) {
            Set<Integer> steps = reach.get(stone);
            for (int k : steps) {
                for (int delta = -1; delta <= 1; delta++) {
                    int nextStep = k + delta;
                    if (nextStep <= 0) {
                        continue;
                    }

                    int nextPos = stone + nextStep;
                    if (reach.containsKey(nextPos)) {
                        reach.get(nextPos).add(nextStep);
                    }
                }
            }
        }

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

func canCross(stones []int) bool {
	reach := make(map[int]map[int]bool, len(stones))
	for _, stone := range stones {
		reach[stone] = make(map[int]bool)
	}

	reach[0][0] = true

	for _, stone := range stones {
		for step := range reach[stone] {
			for delta := -1; delta <= 1; delta++ {
				nextStep := step + delta
				if nextStep <= 0 {
					continue
				}

				nextPos := stone + nextStep
				if _, ok := reach[nextPos]; ok {
					reach[nextPos][nextStep] = true
				}
			}
		}
	}

	return len(reach[stones[len(stones)-1]]) > 0
}

相似题目

题目	难度	考察点
139. 单词拆分	中等	DP + 哈希表
322. 零钱兑换	中等	动态规划
494. 目标和	中等	记忆化搜索
935. 骑士拨号器	中等	图 DP
1345. 跳跃游戏 IV	困难	BFS + 哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/88741267