这里有一个非负整数数组 arr,你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时,你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意,不管是什么情况下,你都无法跳到数组之外。 这一题是跟着数组下标跳跃进行目标点,最终到达0点,根据规则 在每个点上 可以跳到 i + arr[i] 或者 i - arr[i]。 使用广搜进行判断,进入第一个节点,然后根据规则 i + arr[i] 或者 i - arr[i]。拿到新的节点,如果值为0,则返回ture.如果没有访问过则设-1,入栈当前节点 我们初始时将 start 加入队列。在每一次的搜索过程中,我们取出队首的节点 u,它可以到达的位置为 u + arr[u] 和 u - arr[u]。如果某个位置落在数组的下标范围 [0, len(arr)) 内,并且没有被搜索过,则将该位置加入队尾。
public boolean canReach(int[] arr, int start) { Queue<Integer> queue=new LinkedList<>(); queue.offer(start); while (!queue.isEmpty()) { int index=queue.remove(); //可以访问的位置 i + arr[i] 或者 i - arr[i]。 int one=0; if (index+arr[index]>arr.length-1){ if(index-arr[index]<0){ //return false; break; }else{ one=index-arr[index];//去掉长的部分 } }else {//当两个方向都可以走 one=index+arr[index]; } if (arr[one]==-1){ return false; }else{ if (arr[one]==0){ return true; } arr[one]=-1; queue.offer(one);} } return false;}但是这个方法不能跑完全部的答案,只能跑完47/54个 换做选择深度搜索进行搜索
public boolean canReach(int[] arr, int start) { if (start >= arr.length || start < 0) return false; //超出数组 if (arr[start] < 0) return false; if (arr[start] == 0){ // System.out.println("找到了"); return true;} int l = arr[start] + start; int r = start - arr[start]; arr[start]=-1; return canReach(arr,l)||canReach(arr,r); }完成全部测试