原文链接: https://leetcode-cn.com/problems/jump-game-iii

英文原文

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

 

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3 

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

 

Constraints:

• 1 <= arr.length <= 5 * 104
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

中文题目

这里有一个非负整数数组 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

通过代码

高赞题解

最近刷跳跃游戏数题，做个记录

方法1：DFS

• 准备一个函数：dfs(int[] arr, int curPos, boolean[] visited)
  • 其中curPos表示当前访问的位置
  • visited表示当前的curPos位置有无被访问过
• 出口条件：
  • 当前curPos越界了，也就是不在[0,len-1]范围内时，返回false
  • 当前curPos的访问过，返回false
  • 当arr[curPos]==0时，表示找到了，返回true
• 探索左边和右边位置

[]
 public boolean canReach1st(int[] arr, int start) {
    boolean[] visited = new boolean[arr.length];
    return dfs(arr, start, visited);
}

private boolean dfs(int[] arr, int curPos, boolean[] visited) {
    if (curPos < 0 || curPos >= arr.length || visited[curPos]) return false;
    if (arr[curPos] == 0) return true;
    visited[curPos] = true;
    return dfs(arr, curPos - arr[curPos], visited) || dfs(arr, curPos + arr[curPos], visited);
}

[]
class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:

        if not arr: return False
        n = len(arr)
        visited = [0] * n
        def dfs(arr,curPos):
            if curPos < 0 or curPos >= n or visited[curPos]:
                return False
            if arr[curPos] == 0: return True
            visited[curPos] = 1
            return dfs(arr, curPos + arr[curPos]) or dfs(arr, curPos - arr[curPos])

        return dfs(arr,start)

方法2：BFS

• 准备一个bool类型的数组visited表示当前的下标有无被访问过
• 准备一个queue，转这个queue
  • 取到这一轮的总的size大小，进行for loop
  • 弹出当前的curPos,如果arr[curPos]== 0说明找到了，返回true
  • 分别渠道左右两边去找，curPos的位置不越界并且leftPos和rightPos未被访问过
  • 访问后要设置下visited的属性，并且将位置放置于queue中

[]
public boolean canReach2nd(int[] arr, int start) {
        LinkedList<Integer> queue = new LinkedList<>();
        int n = arr.length;
        boolean[] visited = new boolean[n];
        queue.add(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curPos = queue.removeFirst();
                int curValue = arr[curPos];
                if (curValue == 0) return true;
                int leftPos = curPos - curValue;
                if (leftPos >= 0 && !visited[leftPos]) {
                    visited[leftPos] = true;
                    queue.addFirst(leftPos);
                }
                int rightPos = curPos + curValue;
                if (rightPos < n && !visited[rightPos]) {
                    visited[rightPos] = true;
                    queue.addFirst(rightPos);
                }
            }
        }
        return false;
    }

[]
class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        from collections import deque
        
        if not arr: return False
        if arr[start] == 0: return True
        n = len(arr)
        visited = {start}
        queue = deque()
        queue.append(start)
        
        while queue:
            cur = queue.popleft()
            for index in [cur - arr[cur], cur + arr[cur]]:
                if 0<= index < n and index not in visited:
                    if arr[index] == 0: return True
                    visited.add(index)
                    queue.append(index)
        return False

统计信息

通过次数	提交次数	AC比率
18384	31970	57.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言