1345. 跳跃游戏 IV

题目链接

如果没有从i跳到j，则根据i可以跳掉i+1,或者i-1，能够利用

但是现在有3种方式，可以从当前位置跳到i+1, i-1, j(arr[i] = arr[j])，我可以理解为一种搜索的方式吗，在每一步搜索过程中统计当从下标0跳到数组最后一个元素的时候，维护最少跳动次数。

例如数组arr = [100, -23, -23, 404, 100, 23, 23, 23, 3, 404]，一共最少需要3次跳动，从下标0到4到3到9。

我们可以理解为一个图，目的是求图的最短路，可以用BFS来解决。

首先将数组中每个下标视为节点，边的构建则是按照题意得三种操作方式，

• i -> i + 1
• i -> i - 1
• i -> j (arr[i] = arr[j])

然后求节点0到节点n-1的最短路径。使用BFS可以天然保证第一次到达终点时，经过的层数最少。之所以不用DFS是因为DFS找到的是一条路径，需要遍历所有可能才能比较最小值，效率低。
BFS是按层扩展，第一次抵达终点时就是最少跳数，不需要继续搜索。

步骤：

• 维护一个队列用于BFS搜索，存入下标0的元素
• 为了方便找到相同元素值得下标，通过Map维护
• 使用dist数组维护最短距离，dist[i] 存储从起点 0 到下标 i 的最少跳数。BFS 按层扩展的特性保证，第一次给某个节点赋值时，它就已经是最短距离了，不需要后续更新。
  • 同时dist还充当了已访问标记，if (dist[nb] == -1)表示还没访问过，所以初始化dist为-1。一旦某个节点被加入队列，立刻赋值 dist[nb] = nextDist，后续再遇到这个节点时条件不成立，自然跳过。
• 同时确保每个节点最多入队一次，

classSolution{publicintminJumps(int[]arr){// 处理边界intn=arr.length;if(n==1)return0;// 建立相同元素值的Map下标Map<Integer,List<Integer>>map=newHashMap<>();for(inti=0;i<n;i++){// // 如果不存在键则创建// if (!map.containsKey(arr[i])) {// map.put(arr[i], new ArrayList<>());// }// // 存在直接存入// map.get(arr[i]).add(i);map.computeIfAbsent(arr[i],k->newArrayList<>()).add(i);}// 统计距离数组int[]dist=newint[n];// 初始化Arrays.fill(dist,-1);// 从下标0开始出发，dist[0]=0;// 定义队列Queue<Integer>queue=newArrayDeque<>();// 放入下标0queue.offer(0);// BFS遍历while(!queue.isEmpty()){// 获取队头元素intcur=queue.poll();intnextDist=dist[cur]+1;// 即下一个更新的操作部署// 三类邻居List<Integer>neighbors=newArrayList<>();// 判断左右位置是否合适if(cur-1>=0)neighbors.add(cur-1);if(cur+1<n)neighbors.add(cur+1);// 找到相同元素值得下标if(map.containsKey(arr[cur])){neighbors.addAll(map.get(arr[cur]));// 关键优化：防止重复处理同值节点map.remove(arr[cur]);}// 处理邻居for(intnb:neighbors){if(dist[nb]==-1){// 没有被访问过dist[nb]=nextDist;if(nb==n-1)returnnextDist;// 提前终止queue.offer(nb);}}}return-1;}}