LeetCode 1345. 跳跃游戏 IV (bfs+哈希表)

题目描述

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标：
i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的最少操作次数 。
注意：任何时候你都不能跳到数组外面。

输入格式

首先输入数组arr的长度n，
然后输入n个整数，以空格分隔。
1 <= n <= 5 * $10^4$
-$10^8$ <= arr[i] <= $10^8$

输出格式

输出一个整数，表示到达数组最后一个元素的下标处所需的最少操作次数

输入样例

10
100 -23 -23 404 100 23 23 23 3 404
1
2

输出样例

3
1

解释：需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

分析

我们需要使用一个哈希表将所有的相同数的下标记录在同一个数组v[i]中。
之后使用bfs，将起点0入队，之后每一次将所有值相同的坐标入队列并及时清空v[i]，直到找到终点为止。

C++ 代码

#include 
#include
#include 
#include
#include
#include
#include
#include
using namespace std;
const int N = 210;
class Solution {
public:
    //哈希表，映射一个数和其在数组v中对应的下标
    unordered_map mp;
    int minJumps(vector& arr) {
        int len=arr.size(),idx=1;
        bool st[len];
        memset(st,0,sizeof st);
        vector > v; //用来记录相同的数的下标
        for(int i=0;i temp;
                temp.push_back(i);
                v.push_back(temp);
            }
            else{
                //由于我们初始idx为1，所以这里需要-1偏移一个下标
                v[mp[arr[i]]-1].push_back(i);
            }
        }
        
        int time=0;
        queue q;
        //起点入队
        q.push(0);
        st[0]=1;
        while(q.size())
        {
            //第time轮一共有le个下标可以参与搜索
            int le=q.size();
            while(le--)
            {
                auto t=q.front(); q.pop();
                st[t]=1;
                if(t==len-1) return time;
                //将所有两个点加入到队列q
                if(t-1>=0 && t-1=0 && t+1>n;
    
    vector  g;
    for(int i=0;i>x;
        g.push_back(x);
    }
    cin>>m;
    cout<