X

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-解题思路分析/
Categories: leetcode
kwantong:

View Comments (0)