题目描述
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
i + 1需满足：i + 1 < arr.lengthi - 1需满足：i - 1 >= 0j需满足：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 * 10^4-10^8 <= arr[i] <= 10^8
问题分析
这道题是跳跃游戏系列的第四题，较前三题有了更多的变化和难度提升。主要特点是：
- 三种跳跃方式：
- 向前跳一步（i + 1）
- 向后跳一步（i - 1）
- 跳到任何一个与当前位置值相同的位置（arr[i] == arr[j]）
- 目标：找到从起点（下标0）到终点（下标arr.length - 1）的最少操作次数。
- 可能无解：在某些情况下，可能无法到达最后一个位置，需要返回-1。
由于我们需要找到最少操作次数，这是一个典型的最短路径问题，最适合使用广度优先搜索（BFS）来解决。
解题思路
广度优先搜索（BFS）
BFS的核心思想是"层级遍历"，每一层代表走的步数，先访问的节点一定是距离起点最近的节点。对于这道题：
- 使用队列保存待访问的节点（下标）
- 使用集合记录已访问的节点，避免重复访问
- 对于每个节点，尝试三种跳跃方式：
- 向右跳一步（i + 1）
- 向左跳一步（i - 1）
- 跳到所有与当前位置值相同的其他位置
- 为了优化性能，我们可以使用哈希表预处理数组，将相同值的下标分组存储，这样可以快速找到所有与当前位置值相同的位置。
- 当我们第一次访问到终点时，当前的步数就是最少操作次数。
优化点
一个关键的优化是：对于值相同的位置，一旦我们访问过其中一个位置后，可以将所有相同值的位置都标记为已访问。这是因为如果我们能从A跳到B，也能从B跳到A，所以没必要重复访问。
算法图解
让我们以示例1为例详细解释BFS的执行过程：
arr = [100,-23,-23,404,100,23,23,23,3,404]- 预处理：构建值到下标的映射
100 -> [0, 4] -23 -> [1, 2] 404 -> [3, 9] 23 -> [5, 6, 7] 3 -> [8]
- 初始化：
- 队列：[0]（起点）
- 已访问：[true, false, false, ..., false]
- 步数：0
- 第1步：处理下标0
- 当前值：arr[0] = 100
- 相同值的其他下标：4
- 向左跳：不可行（已是最左侧）
- 向右跳：下标1，加入队列
- 跳到相同值：下标4，加入队列
- 队列：[1, 4]
- 已访问：[true, true, false, false, true, false, ...]
- 清空100对应的下标列表
- 步数：1
- 第2步：处理下标1和4
- 处理下标1：
- 当前值：arr[1] = -23
- 相同值的其他下标：2
- 向左跳：下标0，已访问，跳过
- 向右跳：下标2，加入队列
- 跳到相同值：下标2，加入队列（重复，实际只加一次）
- 处理下标4：
- 当前值：arr[4] = 100
- 相同值的其他下标：无（已清空）
- 向左跳：下标3，加入队列
- 向右跳：下标5，加入队列
- 队列：[2, 3, 5]
- 已访问：[true, true, true, true, true, true, false, ...]
- 步数：2
- 处理下标1：
- 第3步：处理下标2、3和5
- 处理下标2：
- 当前值：arr[2] = -23
- 相同值的其他下标：无（已清空）
- 向左跳：下标1，已访问，跳过
- 向右跳：下标3，已访问，跳过
- 处理下标3：
- 当前值：arr[3] = 404
- 相同值的其他下标：9（终点）
- 向左跳：下标2，已访问，跳过
- 向右跳：下标4，已访问，跳过
- 跳到相同值：下标9（终点），找到目标！
- 返回步数：3
- 处理下标2：
到此，我们已经找到了从起点到终点的最短路径，步数为3。路径是：0 -> 4 -> 3 -> 9。
详细代码实现
Java 实现
import java.util.*;
class Solution {
public int minJumps(int[] arr) {
int n = arr.length;
if (n == 1) return 0; // 只有一个元素，已在终点
// 构建值到下标的映射（相同值的所有下标）
Map<Integer, List<Integer>> valueToIndices = new HashMap<>();
for (int i = 0; i < n; i++) {
valueToIndices.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
// BFS需要的数据结构
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
// 初始化：将起点加入队列
queue.offer(0);
visited[0] = true;
// BFS
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int current = queue.poll();
// 到达终点
if (current == n - 1) {
return steps;
}
// 获取当前值对应的所有下标
List<Integer> sameValueIndices = valueToIndices.get(arr[current]);
// 尝试向左跳
if (current - 1 >= 0 && !visited[current - 1]) {
queue.offer(current - 1);
visited[current - 1] = true;
}
// 尝试向右跳
if (current + 1 < n && !visited[current + 1]) {
queue.offer(current + 1);
visited[current + 1] = true;
}
// 尝试跳到相同值的位置
for (int idx : sameValueIndices) {
if (idx != current && !visited[idx]) {
queue.offer(idx);
visited[idx] = true;
}
}
// 清空该值对应的下标列表，避免重复访问
sameValueIndices.clear();
}
steps++;
}
return -1; // 无法到达终点
}
}C# 实现
using System;
using System.Collections.Generic;
public class Solution {
public int MinJumps(int[] arr) {
int n = arr.Length;
if (n == 1) return 0; // 只有一个元素，已在终点
// 构建值到下标的映射（相同值的所有下标）
Dictionary<int, List<int>> valueToIndices = new Dictionary<int, List<int>>();
for (int i = 0; i < n; i++) {
if (!valueToIndices.ContainsKey(arr[i])) {
valueToIndices[arr[i]] = new List<int>();
}
valueToIndices[arr[i]].Add(i);
}
// BFS需要的数据结构
Queue<int> queue = new Queue<int>();
bool[] visited = new bool[n];
// 初始化：将起点加入队列
queue.Enqueue(0);
visited[0] = true;
// BFS
int steps = 0;
while (queue.Count > 0) {
int size = queue.Count;
for (int i = 0; i < size; i++) {
int current = queue.Dequeue();
// 到达终点
if (current == n - 1) {
return steps;
}
// 获取当前值对应的所有下标
List<int> sameValueIndices = valueToIndices[arr[current]];
// 尝试向左跳
if (current - 1 >= 0 && !visited[current - 1]) {
queue.Enqueue(current - 1);
visited[current - 1] = true;
}
// 尝试向右跳
if (current + 1 < n && !visited[current + 1]) {
queue.Enqueue(current + 1);
visited[current + 1] = true;
}
// 尝试跳到相同值的位置
foreach (int idx in sameValueIndices) {
if (idx != current && !visited[idx]) {
queue.Enqueue(idx);
visited[idx] = true;
}
}
// 清空该值对应的下标列表，避免重复访问
sameValueIndices.Clear();
}
steps++;
}
return -1; // 无法到达终点
}
}复杂度分析
- 时间复杂度：O(n)，其中n是数组的长度。在最坏情况下，我们需要访问每个位置一次，每个位置的操作（包括向左/右跳和跳到相同值的位置）的时间复杂度是O(1)。虽然构建映射表需要O(n)，但总体时间复杂度仍然是O(n)。
- 空间复杂度：O(n)，主要用于存储队列、已访问标记和值到下标的映射。在最坏情况下，队列可能包含所有位置，映射表也需要存储所有位置。
优化与技巧
- 预处理相同值的下标：通过哈希表提前建立值到下标的映射，可以在O(1)时间内找到所有相同值的位置。
- 清空已访问的值列表：一旦我们访问了某个值，就可以将该值对应的所有下标从映射表中移除，避免重复访问。这个优化非常关键，可以将复杂度从O(n²)降低到O(n)。
- 提前终止：一旦发现终点，立即返回当前步数，无需继续BFS。
- 边界检查：确保向左/右跳不会越界。
- 特殊情况处理：如果数组只有一个元素，可以直接返回0，因为已经在终点了。