X

LEETCODE 1345. Jump Game IV 解题思路分析

题目大意:

跳跃游戏 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

解题思路分析:

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

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

View Comments (2)