LeetCode.LCP.09最小跳跃次数

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

示例 1：
输入：jump = [2, 5, 1, 1, 1, 1]
输出：3
解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。

限制：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-tiao-yue-ci-shu

两种解决思路，第一种DP，第二种BFS，这里描述第二种：

因为数据范围的原因，使用一个队列不做优化肯定会超时（添加向左可走的位置时，有重复），所以可以使用两个队列，一个q维护要访问的小标，一个index存放待访问的下标(向左时用到)：

流程：

• 队列q不空，就访问队列q中存放的所有下标，对每个下标，判断向右走的那一步是否可以弹出机器(即是否>=jump.size())，若不行，添加那一步到达的位置，接着添加向左可达的位置，要求是index.front()必须小于当前下标(即在当前下标左边)且未访问过
• step++
• 循环第一步，这样每次遍历队列q中的元素都是上一步中拓展到的位置，体现出了BFS一步一步向外层拓展的特性，这样当所有下标都访问过之后(每个下标都只会走一遍)，没有弹出机器就返回-1即可

code:

class Solution {
public:
    int minJump(vector<int>& jump) {
        //BFS
        int n = jump.size();
        vector<bool> st(n+1,false);  //记录当前位置是否已经走过
        queue<int> index;   //记录下标(向左走的时候用到)
        queue<int> q;
        for(int i = 0; i<n; i++) index.push(i);  
        
        q.push(0);
        st[0] = true;
        int ans = 0;
        while(q.size()){
            int cnt = q.size();
            for(int j = 0; j<cnt; j++){  
                int t = q.front();
                q.pop();

                //记录向右走的那一次
                if(t+jump[t]<n){
                    if(!st[t+jump[t]]){
                        q.push(t+jump[t]);
                        st[t+jump[t]] = true;
                    }
                }
                else return ans +1;

                //记录当前位置左边可到的位置
                while(!index.empty() && index.front()<t){  //条件1：在当前位置左边
                    int l = index.front();
                    index.pop();
                    if(!st[l]){   //条件2：未访问过
                        q.push(l);
                        st[l] = true;
                    }
                }
            }  
            ans++;
        }
        return -1;
    }
};