2022-01-21 跳跃游戏 IV

广度优先搜索

队列里记录的永远是某个点可以最少到达的步数，一旦遍历过就不可以再次造访，这样就能保证到达终点的步数是最小的

/*
@可爱抱抱呀
执行用时：46 ms, 在所有 Java 提交中击败了63.21%的用户
内存消耗：51.6 MB, 在所有 Java 提交中击败了69.43%的用户
2022年1月20日 12:58
*/
class Solution {
    public int minJumps(int[] arr) {
        if(arr.length==1){return 0;}
        boolean cameBefore[]=new boolean[arr.length];
        Map<Integer,List<Integer>> map=new HashMap<>();
        for(int i=0;i<arr.length;i++){
            if(!map.containsKey(arr[i])){map.put(arr[i],new ArrayList<>());}
            map.get(arr[i]).add(i);
        }
        Queue<int[]> q=new LinkedList<>();//{坐标，步数}
        cameBefore[0]=true;
        q.add(new int[]{0,0});
        while(q.size()>0){
            int a[]=q.poll();//每个点拿出后，检查所有同值的点，以及前后的点
            if(a[0]+1==arr.length-1){return a[1]+1;}
            if(!cameBefore[a[0]+1]){
                cameBefore[a[0]+1]=true;
                q.add(new int[]{a[0]+1,a[1]+1});
            }
            if(a[0]>1&&!cameBefore[a[0]-1]){
                cameBefore[a[0]-1]=true;
                q.add(new int[]{a[0]-1,a[1]+1});
            }
            if(map.containsKey(arr[a[0]])){
                List<Integer> list=map.get(arr[a[0]]);
                for(int i=0;i<list.size();i++){
                    if(list.get(i)-a[0]!=0&&!cameBefore[list.get(i)]){
                        if(list.get(i)-arr.length+1==0){return a[1]+1;}
                        cameBefore[list.get(i)]=true;
                        q.add(new int[]{list.get(i),a[1]+1});
                    }
                }
                map.remove(arr[a[0]]);//过河拆桥
            }
        }
        return -1;
    }
}

class Solution {
    public int minJumps(int[] arr) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (i > 0 && i < arr.length - 1 && arr[i - 1] == arr[i] && arr[i + 1] == arr[i]) continue;
            if (i > 1 && i < arr.length - 2 && arr[i - 2] == arr[i] && arr[i + 2] == arr[i] && arr[i - 1] == arr[i + 1]) continue;
            map.putIfAbsent(arr[i], new ArrayList<>());
            map.get(arr[i]).add(i);
        }
        boolean[] visited = new boolean[arr.length];
        int step = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int idx = queue.poll();
                if (idx == arr.length - 1) return step;
                // 向后走
                if (idx + 1 < arr.length && !visited[idx + 1]) {
                    if (idx + 1 == arr.length - 1) return step + 1;
                    queue.offer(idx + 1);
                    visited[idx + 1] = true;
                }
                // 向前走
                if (idx - 1 >= 0 && !visited[idx - 1]) {
                    queue.offer(idx - 1);
                    visited[idx - 1] = true;
                }
                // 向相同的元素走
                if (map.containsKey(arr[idx])) {
                    for (int j : map.get(arr[idx])) {
                        if (!visited[j]) {
                            if (j == arr.length - 1) return step + 1;
                            queue.offer(j);
                            visited[j] = true;
                        }
                    }
                    map.remove(arr[idx]);//过河拆桥
                }
            }
            step++;
        }
        return step;
    }
}