题目大意：
跳跃游戏 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-解题思路分析/
View Comments (0)