题目
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标：
- 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 处，也就是数组的最后一个元素处。
示例 4：
输入：arr = [6,1,9] 输出：2
示例 5：
输入：arr = [11,22,7,7,7,7,7,7,7,22,13] 输出：3
解题
方法一：BFS
class Solution { public: int minJumps(vector<int>& arr) { unordered_map<int,vector<int>> sameValueMap;//记录值相同的 放入同一个数组中 for(int i=0;i<arr.size();i++){ sameValueMap[arr[i]].push_back(i); } unordered_set<int> visitedIndexSet;//记录每个顶点是否访问过（因为BFS,后访问的step数肯定大于等于先访问的） queue<pair<int,int>> q;//（索引，步数step） q.emplace(0,0);//（初始顶点，初始step=0） visitedIndexSet.insert(0);//（初始顶点已访问） while(!q.empty()){ auto [index,step]=q.front(); q.pop(); if(index==arr.size()-1) return step; int val=arr[index]; step++; if(sameValueMap.count(val)){//值相同的放入queue中 for(int i:sameValueMap[val]){ if(!visitedIndexSet.count(i)){ q.emplace(i,step); visitedIndexSet.insert(i); } } sameValueMap.erase(val); } if(index+1<arr.size()&&!visitedIndexSet.count(index+1)){//index+1放入queue 中 q.emplace(index+1,step); visitedIndexSet.insert(index+1); } if(index-1>=0&&!visitedIndexSet.count(index-1)){//index-1放入queue中 q.emplace(index-1,step); visitedIndexSet.insert(index-1); } } return -1; } };
