讨论/题目交流/🐱 第 19 场夜喵双周赛/
🐱 第 19 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 将数字变成 0 的操作次数
4 分 - 大小为 K 且平均值大于等于阈值的子数组数目
5 分 - 时钟指针的夹角
6 分 - 跳跃游戏 IV

展开讨论

跳跃游戏 IV

给你一个序列,初始位于位置 00

当位于位置 xx 的时候可以:

  • 跳到 x+1x + 1, 满足 x+1<nx + 1 < n
  • 跳到 x1x - 1, 满足 x10x - 1 \geq 0
  • 跳到 jj, 满足 arr[x]=arr[j]arr[x] = arr[j]

问到达位置 n1n - 1 的最少步数。

分析

十分明显的 BFS,暴力做法为按照题目中的三种走法建边跑 BFS。

但是这样复杂度在最坏情况下将会退化成 O(n2)O(n^2) 的,如果一个数组内有 nn 个数字且每个数字都相同,BFS 的过程中,对于第三种操作,nn 数字都将检查 n1n-1 次,导致超时。

但是,我们可以发现第三种操作没有必要连续使用,比如跳跃路径 23->23->23,那么何不从一开始的 23 跳到最后一个第三个 23 呢?为了防止第三种操作连续使用,我们在 BFS 同时维护一个 Flag 数组,如果一个数字是通过第三种操作到达的,就给 Flag 相应位置置 11,否则置 00。这样如果一个数字对应的 Flag 为 11,那么就不适用第三种操作,否则才可以使用。

至于,第三种操作中,检查一个数字可以去哪些位置,可以使用 map<int, vector<int>> 来暴力维护之。

时间复杂度:O(nlogn+n)=O(nlogn)O(nlogn + n) = O(nlogn)

const int MAXN = 5e4 + 50;

int dist[MAXN], flag[MAXN];
map<int, vector<int>> edge;
queue<int> que;
class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        
        for (int i = 0; i <= n; i++) dist[i] = -1, flag[i] = 0;
        edge.clear();
        while(!que.empty()) que.pop();
        
        for (int i = 0; i < n; i++) edge[arr[i]].push_back(i);
        
        que.push(0);
        dist[0] = 0;
        flag[0] = 0;
        
        while(!que.empty()){
            int x = que.front(); que.pop();
            
            if (x + 1 < n && dist[x + 1] == -1){
                que.push(x + 1);
                dist[x + 1] = dist[x] + 1;
                flag[x + 1] = 0;
            }
            
            if (x - 1 >= 0 && dist[x - 1] == -1){
                que.push(x - 1);
                dist[x - 1] = dist[x] + 1;
                flag[x - 1] = 0;
            }
            
            if (flag[x] == 0){
                for (auto v: edge[arr[x]]){
                    if (dist[v] == -1){
                        que.push(v);
                        dist[v] = dist[x] + 1;
                        flag[v] = 1;
                    }
                }
            }
        }
        
        // for(int i = 0; i < n; i++) printf("%d ", dist[i]); printf("\n");
        return dist[n - 1];
    }
};
2
展开全部 14 讨论