1345. Jump Game IV

 Version #1 BFS

一开始写了bug就是每次一通过iterate hashmap找与当前点相同value的点，然后用visited数组check是否visited过，这样当所有点的value都是一样的时候worst case会到达O(N^2)

改进方法是每次visited过的点就从hashmap里面去掉，这样不会重复check

看答案的做法是先build graph再iterate就不会有这种问题

Time O(N)

Space O(N)

Runtime: 122 ms, faster than 55.89% of Java online submissions for Jump Game IV.

Memory Usage: 72.3 MB, less than 74.66% of Java online submissions for Jump Game IV.

class Solution {

    public int minJumps(int[] arr) {

        if (arr == null || arr.length == 0) {

            return 0;

        }

        // key-array value, value-list of indexes that having this value

        Map<Integer, Set<Integer>> indexes = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {

            int val = arr[i];

            indexes.putIfAbsent(val, new HashSet<>());

            indexes.get(val).add(i);

        }

        Queue<Integer> que = new ArrayDeque<>();

        que.offer(0);

        indexes.get(arr[0]).remove(0);

        int step = 0;

        while (!que.isEmpty()) {

            int size = que.size();

            while (size-- > 0) {

                int curr = que.poll();

                if (curr == arr.length - 1) {

                    return step;

                }

                if (curr - 1 >= 0 && indexes.get(arr[curr - 1]).contains(curr - 1)) {

                    indexes.get(arr[curr - 1]).remove(curr - 1);

                    que.offer(curr - 1);

                }

                if (curr + 1 < arr.length && indexes.get(arr[curr + 1]).contains(curr + 1)) {

                    indexes.get(arr[curr + 1]).remove(curr  + 1);

                    que.offer(curr + 1);

                }

                for (Integer next : indexes.get(arr[curr])) {

                    que.offer(next);

                }

                indexes.get(arr[curr]).clear();

                // O(N) in the worst case - will cause TLE

                // for (Integer next : indexes.get(arr[curr])) {

                //     if (visited[next]) {

                //         continue;

                //     }

                //     visited[next] = true;

                //     que.offer(next);

                // }

            }

            step++;

        }

        return 0;

    }

}