java-跳跃游戏

LeetCode 1345.跳跃游戏IV

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

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

i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

求”最少次数“，很容易想到BFS方法，我们将每一步的三种选择，作为当前这一步的三个子节点，然后进行BFS，如果走到结尾，返回当前层次即可。

class Solution {
    public int minJumps(int[] arr) {
        HashMap<Integer,ArrayList<Integer>>map = new HashMap<>();
        // 将相等的元素放入hashmap中
        for(int i=0;i<arr.length;i++){
            if(map.get(arr[i]) == null){
                map.put(arr[i],new ArrayList<>());
            }
            map.get(arr[i]).add(i);
        }
        // int [] 存索引和步数
        Queue<int []> queue = new LinkedList<>();
        queue.add(new int[]{0,0});
        // 用于记录当前位置是否访问过
        boolean []visit = new boolean[arr.length];
        visit[0] = true;
        // while循环
        while(!queue.isEmpty()){
            // 出队
            int [] temp = queue.poll();
            int index = temp[0],step = temp[1];
            // 判断是否已经走到最后一个位置 ，如果是直接返回
            if(index == arr.length-1)
                return step;
            // 向右走
            step++;
            if (index + 1 < arr.length && visit[index + 1] == false) {
                visit[index+1] =true;
                queue.offer(new int[]{index + 1, step});
            }
            // 向左走
            if (index - 1 >= 0 && visit[index - 1] == false) {
                visit[index-1] = true;
                queue.offer(new int[]{index - 1, step});
            }
            // 跳步
            if (map.get(arr[index]) != null) {
                for (int i : map.get(arr[index])) {
                    if (visit[i] == false) {
                        if(i == arr.length-1)
                            return step;
                        visit[i]=true;
                        queue.offer(new int[]{i, step});
                    }
                }
                map.remove(arr[index]);
            }
        }
        return -1;
    }
}