当前位置：首页 > news >正文

LeetCode 1345. 跳跃游戏 IV（困难）

news 2025/5/23 4:58:25

题目描述

给你一个整数数组 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 * 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
第3步：处理下标2、3和5
- 处理下标2：
  - 当前值：arr[2] = -23
  - 相同值的其他下标：无（已清空）
  - 向左跳：下标1，已访问，跳过
  - 向右跳：下标3，已访问，跳过
- 处理下标3：
  - 当前值：arr[3] = 404
  - 相同值的其他下标：9（终点）
  - 向左跳：下标2，已访问，跳过
  - 向右跳：下标4，已访问，跳过
  - 跳到相同值：下标9（终点），找到目标！
  - 返回步数：3

到此，我们已经找到了从起点到终点的最短路径，步数为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;// BFSint 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;// BFSint 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，因为已经在终点了。

查看全文

http://www.xdnf.cn/news/545563.html