leetcode1345. 跳跃游戏 IV(hard)

leetcode1345. 跳跃游戏 IV(hard)

跳跃游戏 IV

解题思路

代码复杂度
力扣链接

解题思路

官方题解
大佬题解

广度优先搜索 代码

class Solution {
    public int minJumps(int[] arr) {
        //key是元素值,value是相同元素值的索引集合
        Map> map = new HashMap<>();
        
        int n = arr.length;
        //遍历数组,先需要找出所有的值相同的子图，用一个哈希表 map 保存。
        for (int i = 0; i < n; ++i) {
            map.putIfAbsent(arr[i], new ArrayList<>());
            map.get(arr[i]).add(i);
        }

        //在第一次访问到这个子图中的某个节点时，即会将这个子图的所有其他未在队列中的节点都放入队列。在第二次访问到这个子图中的节点时，就不需要去考虑这个子图中的其他节点了，因为所有其他节点都已经在队列中或者已经被访问过了。
        Queue q = new linkedList<>();
        //记录某个节点是否被访问过,存放索引即可
        Set visited = new HashSet<>();
        //将当起点添加visited集合中
        visited.add(0);
        //将起点添加到队列中,第一个0为当前位置的索引,第二个0是移动的步数
        q.offer(new int[]{0, 0});

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int i = poll[0];
            int step = poll[1];
            //如果d出的节点的索引是n - 1,说明找到了步数最少的值,直接返回步数
            if (i == n - 1) {
                return step;
            }

            //步数+1
            ++step;
            int v = arr[i];
            if (map.containsKey(v)) {
                //将当前点的相同值的索引集合添加到队列中,即下一步可以移动到的位置
                for (int index : map.get(v)) {
                    //如果成功添加到集合中,说明当前点未被访问过,将其添加到队列中
                    if (visited.add(index)) {
                        q.offer(new int[]{index, step});
                    }
                    //在第一次把这个子图的所有节点放入队列后，把该子图清空，就不会重复访问该子图的其他边了。
                    map.remove(v);
                }
            }
            

            //将前一个点添加到队列中
            if (i + 1 < n && visited.add(i + 1)) {
                q.offer(new int[]{i + 1, step});
            }

            //将后一个点添加到队列中
            if (i - 1 >= 0 && visited.add(i - 1)) {
                q.offer(new int[]{i - 1, step});
            }
        }
        return 666;
    }

}

复杂度