LeetCode 1306. 跳跃游戏 III

Categories:

题目描述
思路分析
1. 解法一：BFS/DFS 可达性（推荐）
相似题目

题目描述

✅ 1306. 跳跃游戏 III

思路分析

解法一：BFS/DFS 可达性（推荐）

核心思路：

从 start 出发，能跳到 i + arr[i] 或 i - arr[i]。

用队列或递归遍历所有可达位置，遇到 arr[i] == 0 即成功。

用 visited 避免重复访问。

复杂度分析：

时间复杂度：O(n)，每个位置最多访问一次。

空间复杂度：O(n)。

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int idx = queue.poll();
            if (arr[idx] == 0) {
                return true;
            }
            int next1 = idx + arr[idx];
            int next2 = idx - arr[idx];
            if (next1 >= 0 && next1 < n && !visited[next1]) {
                visited[next1] = true;
                queue.offer(next1);
            }
            if (next2 >= 0 && next2 < n && !visited[next2]) {
                visited[next2] = true;
                queue.offer(next2);
            }
        }
        return false;
    }
}

func canReach(arr []int, start int) bool {
    n := len(arr)
    visited := make([]bool, n)
    queue := make([]int, 0)
    queue = append(queue, start)
    visited[start] = true

    for head := 0; head < len(queue); head++ {
        idx := queue[head]
        if arr[idx] == 0 {
            return true
        }
        next1 := idx + arr[idx]
        next2 := idx - arr[idx]
        if next1 >= 0 && next1 < n && !visited[next1] {
            visited[next1] = true
            queue = append(queue, next1)
        }
        if next2 >= 0 && next2 < n && !visited[next2] {
            visited[next2] = true
            queue = append(queue, next2)
        }
    }
    return false
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	BFS/DFS
695. 岛屿的最大面积	中等	BFS/DFS
934. 最短的桥	中等	BFS
733. 图像渲染	简单	BFS/DFS
841. 钥匙和房间	中等	图遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/69954704