leetcode 1345. Jump Game IV | 1345. 跳跃游戏 IV（BFS）

题目

https://leetcode.com/problems/jump-game-iv/

题解

好久没做 hard 了，今天时间多，挑战一下。用 lqy 同学的话说，这题叫做 “苦难题”，哈哈哈。

暴力解其实不难，就是个带 seen 数组的 BFS，看草稿吧~

class Solution {
    public int minJumps(int[] arr) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            Set<Integer> set = map.getOrDefault(arr[i], new HashSet<>());
            set.add(i);
            map.put(arr[i], set);
        }

        Set<Integer> seen = new HashSet<>();
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(0);
        int jump = 0;
        
        while (true) {
            LinkedList<Integer> nextQueue = new LinkedList<>();
            
            while (!queue.isEmpty()) {
                Integer index = queue.poll();
                seen.add(index);
                if (index == arr.length - 1) return jump;

                if (index - 1 >= 0) {
                    if (!seen.contains(index - 1)) nextQueue.add(index - 1);
                    else map.get(arr[index]).remove(index - 1);
                }
                if (index + 1 < arr.length && !seen.contains(index + 1)) {
                    if (!seen.contains(index + 1)) nextQueue.add(index + 1);
                    else map.get(arr[index]).remove(index + 1);
                }
                for (Integer i : map.get(arr[index])) {
                    if (!seen.contains(i)) nextQueue.add(i);
//                    else map.get(arr[i]).remove(i);
                }
                map.get(arr[index]).clear();
            }
            queue = nextQueue;
            jump++;
        }
    }
}