LEETCODE 1306. Jump Game III 解题思路分析

题目大意：

跳跃游戏 III

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i – arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任意 下标处。

注意，不管是什么情况下，你都无法跳到数组之外。

示例 1：

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
 到达值为 0 的下标 3 有以下可能方案： 
 下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
 下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 

示例 2：

输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true 
解释：
 到达值为 0 的下标 3 有以下可能方案： 
 下标 0 -> 下标 4 -> 下标 1 -> 下标 3 

示例 3：

输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：无法到达值为 0 的下标 1 处。 

提示：

• 1 <= arr.length <= 5 * 10^4
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1306

解题思路分析：

本题是 LEETCODE 55. Jump Game 解题思路分析 的续集，但解题方式完全不同。

这道题目类似一个二叉树，数组中的每一个数字可以看做是一个节点，该节点能够连接的下一层节点下标可以是当前下标加上当前值，以及当前下标减去当前值。如果下一个节点的下标没有越界，我们就可以继续向下走，直到找到某个节点的值为0即可返回true。如果所有线路走完都没有找到值为0的节点，返回false。

遍历二叉树找特定值的问题，最直观的方法即是bfs广度优先搜索，本题使用bfs解题没有什么特殊的地方，属于标准bfs模板型题目。bfs的起点是给出的起始下标，将该下标存入Queue中，bfs时，取出Queue中的一个节点，查看其是否为0，如果是0，直接返回true。反之，将该节点能够连接的其他节点放入Queue中，直到 Queue 的大小为0仍不能找到值为0的节点，返回false。

实现代码：

public boolean canReach(int[] arr, int start) {
    // bfs用的Queue
    Queue<Integer> q = new LinkedList<>();
    // 将起点加入Queue
    q.offer(start);
    // 访问数组。记录访问过的节点。避免重复访问
    boolean[] visited = new boolean[arr.length];
    // 设置起点已被访问过
    visited[start]=true;
    // 开始bfs
    while(q.size()>0){
        // 取出一个index
        int index = q.poll();
        // 当前下标的值为0，返回true
        if(arr[index]==0) return true;
        // 当前点能连接到的其他节点
        int next1=index-arr[index];
        // 如果该节点不越界，并且没被访问过
        if(next1>=0 && !visited[next1]){
            // 设置该节点已被访问
            visited[next1]=true;
            // 将该节点存入Queue
            q.offer(next1);
        }
        // 同理
        int next2=index+arr[index];
        if(next2<arr.length && !visited[next2]){
            visited[next2]=true;
            q.offer(next2);
        }
    }
    return false;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Jump Game III.

Memory Usage: 48.1 MB, less than 100.00% of Java online submissions for Jump Game III.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1306-jump-game-iii-解题思路分析/