题目
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
i + 1 需满足：i + 1 < arr.length
i - 1 需满足：i - 1 >= 0
j 需满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
示例 1：
输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
示例 2：
输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。
示例 3：
输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
提示：
1 <= arr.length <= 5 * 104
-108 <= arr[i] <= 108
思路
- 拿到题的第一反应 是使用动态规划的方式进行接替
即dp[i]表示第i个位置到达数组最后一个元素需要操作最少的步骤
dp[i] = min(dp[i - 1] + 1, dp[i + 1] + 1, dp[j] + 1)，其中arr[i] == arr[j] && i != j
尝试了好久有一个用例一直无法通过，后来思考了一下 发现dp[i]的结果依赖于dp[i + 1]，而dp[i + 1]的结果也依赖dp[i]，在这种情况下无法使用动态规划解题（想到这点的时候还没意识到）。后来看了题解里大佬论证dp不可行的原因才意识到。
- 采用BFS + 剪枝，看代码吧。
- 一开始确实是用了map进行剪枝，但是剪枝后没remove掉导致有个用例超时，这里记录一下吸取教训。
代码
public int minJumps(int[] arr) {
if (arr.length == 1) {
return 0;
}
Map<Integer, List<Integer>> firstMap = new HashMap<>();
for (int i = 0; i < arr.length; ++i) {
int val = arr[i];
if (!firstMap.containsKey(val)) {
firstMap.put(val, new ArrayList<>());
}
firstMap.get(val).add(i);
}
Queue<Integer> idxQueue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
idxQueue.offer(0);
visited.add(0);
int step = 0;
while (!idxQueue.isEmpty()) {
int size = idxQueue.size();
for (int k = 0; k < size; ++k) {
int idx = idxQueue.poll();
if (idx == arr.length - 1) {
return step;
}
if(idx - 1 >= 0 && !visited.contains(idx - 1)) {
idxQueue.offer(idx - 1);
visited.add(idx - 1);
}
if(idx + 1 < arr.length && !visited.contains(idx + 1)) {
idxQueue.offer(idx + 1);
visited.add(idx + 1);
}
if (firstMap.containsKey(arr[idx])) {
for (int i : firstMap.get(arr[idx])) {
if (arr[i] == arr[idx] && i != idx && !visited.contains(i)) {
idxQueue.offer(i);
visited.add(i);
}
}
firstMap.remove(arr[idx]);
}
}
++step;
}
return step;
}
