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

LeetCode 1345 跳跃游戏 IV

ds 2025/8/29 17:13:15

LeetCode 1345 跳跃游戏 IV 问题解析

问题概述

LeetCode 1345 是一个关于数组跳跃的图论问题，要求从数组第一个元素跳到最后一个元素，每次跳跃可以：

向左或向右跳任意步
跳到与当前元素值相同的任意位置
目标是求最少跳跃次数。

解题思路

这道题适合用广度优先搜索 (BFS) 解决，核心思路如下：
首先用哈希表记录每个值对应的所有位置
从起点开始 BFS，记录已访问位置避免重复
每次跳跃时，有三种选择：

跳到相同值的所有位置
跳到左边相邻位置
跳到右边相邻位置
找到终点时返回跳跃次数下面是基于上述思路的C++代码实现：

#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;int minJumps(vector<int>& arr) {int n = arr.size();if (n <= 1) return 0;// 预处理相同值的下标集合unordered_map<int, vector<int>> idxSameValue;for (int i = 0; i < n; i++) {idxSameValue[arr[i]].push_back(i);}vector<bool> visited(n, false);queue<int> q;q.push(0);visited[0] = true;int steps = 0;while (!q.empty()) {int size = q.size();// 处理当前层的所有节点for (int i = 0; i < size; i++) {int current = q.front();q.pop();// 到达终点if (current == n - 1) return steps;// 处理相邻节点if (current - 1 >= 0 && !visited[current - 1]) {visited[current - 1] = true;q.push(current - 1);}if (current + 1 < n && !visited[current + 1]) {visited[current + 1] = true;q.push(current + 1);}// 处理相同值的节点int value = arr[current];auto it = idxSameValue.find(value);if (it != idxSameValue.end()) {for (int idx : it->second) {if (!visited[idx]) {visited[idx] = true;q.push(idx);}}// 关键优化：处理完后删除该值的映射idxSameValue.erase(it);}}steps++;}return -1; // 题目保证有解，理论上不会执行到这里
}

代码解释：

预处理阶段：
- 使用unordered_map<int, vector<int>>存储每个值对应的所有下标
BFS初始化：
- 初始化访问标记数组visited
- 队列q初始加入起点0
- 步数计数器steps初始化为0
BFS主循环：
- 按层遍历队列中的节点
- 处理当前节点的相邻节点（前一个和后一个位置）
- 处理当前节点值对应的所有下标：
  - 将未访问的下标加入队列并标记为已访问
  - 处理完后从哈希表中删除该值的映射，避免重复处理
终止条件：
- 当到达终点时直接返回当前步数