1345. Jump Game IV (H)

Jump Game IV (H)

题目

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.

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't need to jump.

Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Example 4:

Input: arr = [6,1,9]
Output: 2

Example 5:

Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

Constraints:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

题意

给定一个数组，对应其中一个下标i，下一步可以到达的下标为i-1、i+1、所有满足arr[i]==arr[j]的j。要求能从0到达最后一个下标的最小步数。

思路

按照提示，将数组重构成一张表，结点的值是数组中的下标，且与前后两个下标对应的结点、所有与该结点在数组中对应的值相等的结点相连。用BFS找最短距离。

代码实现

Java

class Solution {
    public int minJumps(int[] arr) {
        if (arr.length == 1) {
            return 0;
        }

        Map<Integer, List<Integer>> inverse = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            inverse.putIfAbsent(arr[i], new ArrayList<>());
            inverse.get(arr[i]).add(i);
        }


        int steps = 0;
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[arr.length];
        visited[0] = true;
        q.offer(0);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                for (int j = inverse.get(arr[cur]).size() - 1; j >= 0; j--) {
                    int next = inverse.get(arr[cur]).get(j);
                    if (next != cur && !visited[next]) {
                        if (next == arr.length - 1) return steps + 1;
                        q.offer(next);
                        visited[next] = true;
                    }
                }
                if (cur > 0 && !visited[cur - 1]) {
                    q.offer(cur - 1);
                    visited[cur - 1] = true;
                }
                if (cur < arr.length - 1 && !visited[cur + 1]) {
                    if (cur + 1 == arr.length - 1) return steps + 1;
                    q.offer(cur + 1);
                    visited[cur + 1] = true;
                }

            }
            steps++;
        }

        return -1;
    }
}