1345. 跳跃游戏 IV


图片说明


即可，对于同值的哈希其下标，访问一次删掉即可。

class Solution {
public:
    int dp[50005];
    int minJumps(vector<int>& a) {
        int n=a.size();
        int IN=0x3f3f3f;
        memset(dp,0x3f3f3f,sizeof dp);
        dp[0]=0;
        unordered_map<int,vector<int> >p;
        for(int i=0;i<n;i++)p[a[i]].push_back(i);
        queue<int>q;
        q.push(0);
        while(!q.empty()){
            int id=q.front();
            q.pop();
            if(id-1>=0){
                if(dp[id-1]>dp[id]+1){
                    dp[id-1]=dp[id]+1;
                    q.push(id-1);
                }
            }
            if(id+1<n){
                if(dp[id+1]>dp[id]+1){
                    dp[id+1]=dp[id]+1;
                    q.push(id+1);
                }
            }
            for(int i:p[a[id]]){
                if(dp[i]>dp[id]+1){
                    dp[i]=dp[id]+1;
                    q.push(i);
                }
            }
        }
        return dp[n-1];
    }
};