1306. 跳跃游戏 III
1. 题目
见1306. 跳跃游戏 III
2. 解题思路
这题和跳跃游戏1不太一样,这题不是看能不能达到尾部,而是看能不能达到指定的位置。
我们分析下来就是从一个位置出发,有没有达到某一个目标的路径。
那其实就可以符合DFS的解法,求可达性。
3. 代码
class Solution {public boolean canReach(int[] arr, int start) {if(arr.length==0){return false;}boolean[] visited=new boolean[arr.length];return dfs(arr, start, visited);}public static boolean dfs(int[] arr, int idx, boolean[] visited){if(idx < 0 || idx >= arr.length || visited[idx]){return false;}if(arr[idx] == 0){return true;}//沉岛visited[idx] = true;int step = arr[idx];//向前走boolean res1 = dfs(arr, idx + step, visited);//向后走boolean res2 = dfs(arr, idx - step, visited);return res1||res2;}
}