関小君刷题记

题目大意：

跳跃游戏 IV

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标：

• i + 1 满足：i + 1 < arr.length
• i - 1 满足：i - 1 >= 0
• j 满足：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

解题思路分析：

本题是跳跃游戏系列的又一续集，之前讲过的文章可以参考以下链接：

• LEETCODE 55. Jump Game 解题思路分析
• LEETCODE 1306. Jump Game III 解题思路分析
• LEETCODE 1340. Jump Game V 解题思路分析

本题的跳跃条件与上几道题又发生了变化，首先题目给出了起点和终点，分别是数组的头部和尾部，另外，每次跳跃我们可以跳向相邻的左右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-解题思路分析/