AcWing秋招每日一题——week3

1、跳跃游戏

题目

给你一个整数数组 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
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

class Solution {
public:
    queue<pair<int,int> > q;//队列存放下标和对应的下标距离
    unordered_set<int> vis;//已经访问过的下标

    void visit(int id,int step){
        if(!vis.count(id)){
            vis.insert(id);
            q.push({id,step});
        }
    }
    
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int,vector<int>> hash;//用来存放对应索引的下标
        for(int i = 0;i<n;i++){
            hash[arr[i]].push_back(i);
        }
        q.push({0,0});//起点放入队列中
        vis.insert(0);//将该下标放入队列中
        while(!q.empty()){
            auto [id,step] = q.front();//队列中的第一个元素信息拿出来
            q.pop();
            if(id==n-1){return step;}//当到达最后一个时，退出
            step++;//进入下一步，步数加一
            //以下三种方式跳转
            //1、跳到下一个相同的值处
            if(hash.count(arr[id]))
            for(auto k : hash[arr[id]]){visit(k,step);}//去访问每一个与当前id相同或的索引
            hash.erase(arr[id]);
　　　　　　//2、跳到左边
            if(id-1>=0) visit(id-1,step);

　　　　　　//3、跳到右边

　　　　　　　if(id+1<n) visit(id+1,step); } 

return 0; } };

 理解

每一步能跳转的有三种情况

1、跳到相同值

2、向左跳

3、向右跳

所以可以初始化一个队列q，将点放进去，然后将这个点能到的点依次放进去，之后可以实现每一次进入循环的step都是有序的，每进入一次训循环，step+1；

最后返回step是第一次到达最后一个点的情况，由前可知，此必为最小的步数；

另外hash.erase(arr[id]); 用来删除已经遍历过所有相同id。原因：如果不删除，在下一次碰到相同的id，其步数必定比之前大，那么就相当于其中的步数是浪费的，所以直接删去，可以节省时间。