2022/01/15 - 1345. Jump Game IV

1345. Jump Game IV - Hard

Description

1345. Jump Game IV

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

• i + 1 where: i + 1 < arr.length.
• i - 1 where: i - 1 >= 0.
• j where: arr[i] == arr[j] and i != j. Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

大概意思就是在 i 这个位置能跳到 i + 1 和 i - 1的位置，以及与 arr[i] 值相等但是索引不同的位置。计算最少需要多少步能够跳到最后一个索引位置上。

Solutions

看到这样的题，首先能想到的解决方法是 BFS，因为需要搜索每个位置能够跳到的索引。拿 [100,-23,-23,404,100,23,23,23,3,404]来举例，首先从第一个元素100开始，我们需要存储每个数字都在哪些位置上，所以需要一个Map来存储对应的数据例如：{100, [0, 4]}，将每个元素都像这样加入Map中。

因为我们是从第一个元素开始，所以优先将第一个元素索引0放入队列中，并标记该位置已经被访问过了（如果不记录以访问的位置，那么一定会出现死循环）。搜索的第一次循环，弹出队首元素，然后遍历这个元素所在数组位置中的值对应的索引，如果没有被访问过就将这个索引加入队列，并判断当前这个索引+1和-1的位置有没有被访问，没有被访问的索引也都加入到队列中（参考题目上能够跳到的位置）。

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) return 0;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.computeIfAbsent(arr[i], v -> new LinkedList<>()).add(i);
        }
        Deque<Integer> q = new LinkedList<>();
        q.offer(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int idx = q.poll();
                if (idx == n - 1) return step;
                for (int child : graph.get(arr[idx])) {
                    if (!visited[child]) {
                        visited[child] = true;
                        q.offer(child);
                    }
                }
                graph.get(arr[idx]).clear();
                if (idx - 1 >= 0 && !visited[idx - 1]) {
                    visited[idx - 1] = true;
                    q.offer(idx - 1);
                }
                if (idx + 1 < n && !visited[idx + 1]) {
                    visited[idx + 1] = true;
                    q.offer(idx + 1);
                }
            }
            step++;
        }
        return -1;
    }
}

评论