题目大意：
跳跃游戏 IV
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标：
i + 1满足：i + 1 < arr.lengthi - 1满足：i - 1 >= 0j满足：arr[i] == arr[j]且i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
示例 1：
输入：arr = [100,-23,-23,404,100,23,23,23,3,404] 输出：3 解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
示例 2：
输入：arr = [7] 输出：0 解释：一开始就在最后一个元素处，所以你不需要跳跃。
示例 3：
输入：arr = [7,6,9,6,9,6,9,7] 输出：1 解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
示例 4：
输入：arr = [6,1,9] 输出：2
示例 5：
输入：arr = [11,22,7,7,7,7,7,7,7,22,13] 输出：3
提示：
1 <= arr.length <= 5 * 10^4-10^8 <= arr[i] <= 10^8
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1345
解题思路分析：
本题是跳跃游戏系列的又一续集，之前讲过的文章可以参考以下链接：
本题的跳跃条件与上几道题又发生了变化，首先题目给出了起点和终点，分别是数组的头部和尾部，另外，每次跳跃我们可以跳向相邻的左右2点以及与当前数值相同的所有点。描述到这里，题目的图形结构已经非常清晰，这实际上是一道，在已知起点和终点的情况下，求图中最短路径的问题。如果你经常看我的博客，你会马上想到，求最短路径的首选应该是bfs，某些情况下dfs也是可行的。
接下来看解题步骤，既然是图型题，我们需要先将图构建出来，比较重要的部分应该是数组中值相同的部分，我们定义一个Map，key是数值，value是具有该数值的数组下标集合。另外这里有一处可以优化的地方，比如数组中有一连串的相同数字：
arr = [11,22,7,7,7,7,7,7,7,22,13]
对于数组中连续的数字7，实际上起作用的只有首尾两个，其他7无论如何跳都不会优于两边的两个7的。因此，当遇上连续相同数字时，我们只在map中保存首尾2个即可。图形结构构建好之后，就是标准的bfs解题逻辑，这里不再详述，具体可参照代码中注释。
实现代码：
public int minJumps(int[] arr) {
// 记录数组中所有相同数字出现过的位置
Map<Integer, List<Integer>> map = new HashMap<>();
// 循环每一个数字
for(int i=0;i<arr.length;i++){
// 当前数字
int num=arr[i];
// 如果当前数字与前数字相同，并与后数字相同，不用记录。
// 原因参照上文
if(i>0&&i+1<arr.length&&arr[i-1]==num&&arr[i+1]==num){
continue;
}
// 取出当前数字存在的位置集合
List<Integer> list=map.getOrDefault(num,new ArrayList<>());
// 将当前位置加入集合
list.add(i);
// 将集合保存至map
map.put(num,list);
}
// 访问数组，避免同一节点重复访问
boolean[] visited = new boolean[arr.length];
// 首节点为起点，默认已经访问过
visited[0]=true;
// bfs用的Queue
Queue<Integer> q = new LinkedList<>();
// 将起点下标加入queue
q.offer(0);
// 返回结果
int res=0;
// 开始bfs
while(q.size()>0){
int size=q.size();
// 逐层bfs
while(size>0){
// 从Queue中取出一个下标
int index = q.poll();
// 如果该下标为终点，返回res
if(index==arr.length-1) return res;
// 当前层节点数减一
size--;
// 如果当前下标在数组中存在左侧元素，并且左侧位置未访问过
if(index-1>0 && !visited[index-1]){
// 左侧位置设置为已访问
visited[index-1]=true;
// 将左侧位置加入Queue
q.offer(index-1);
}
// 如果当前下标在数组中存在右侧元素，并且右侧位置未访问过
if(index+1<arr.length && !visited[index+1]){
// 右侧位置设置为已访问
visited[index+1]=true;
// 将右侧位置加入Queue
q.offer(index+1);
}
// 取出与当前下标元素相同的其他下标集合
List<Integer> list=map.get(arr[index]);
// 循环每一个下标
for(int i : list){
// 如果该下标不是当前下标，并且没有访问过
if(i!=index && !visited[i]){
// 将该下标设置为已访问
visited[i]=true;
// 将该下标存入Queue
q.offer(i);
}
}
} // 当前层bfs结束
// bfs步数加一（距离加一）
res++;
}
return res;
}本题解法执行时间为40ms。
Runtime: 40 ms, faster than 82.03% of Java online submissions for Jump Game IV.
Memory Usage: 54.1 MB, less than 100.00% of Java online submissions for Jump Game IV.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1345-jump-game-iv-解题思路分析/
《LEETCODE 1345. Jump Game IV 解题思路分析》有2条回应