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

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

image.png

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

展开讨论

T4 题解

题目描述 给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。

每一步,你可以从下标 i 跳到下标:

  • i + 1 满足:i + 1 < arr.length
  • i - 1 满足:i - 1 >= 0
  • j 满足:arr[i] == arr[j]i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数

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

分析 最短路问题,考虑BFS做法。写出最基本的BFS方法,伪代码如下:

q.push(u), vis[u] = 1, dis[u] = 0;
while (!q.empty()) {
  int u = q.front();
  q.pop();
  for (int v in {u+1, u-1}) {
    // 左右跳跃
    if (v >= 0 && v < n && !vis[v]) {
      vis[v] = 1, q.push(v), dis[v] = dis[u]+1;
    }
    // 同值跳跃
    for (int v = 0; v < n; v++) {
      if (u != v && a[v] == a[u] && !vis[v]) {
        vis[v] = 1, q.push(v), dis[v] = dis[u]+1;
      }
    }
  }
}

但是这个代码复杂度为 O(n2)O(n^2) ,选择同值的跳跃方法太耗时,遍历需要O(n)O(n)

这里使用倒排加速,即开一个哈希表k->v记录所有使得a[k]=v的k:

unordered_map<int, vector<int>> m;
for (int i = 0; i < n; i++) m[a[i]] = i;

但是即使这样,选择同值进行跳跃的复杂度仍然是O(n)O(n)。BFS的特点是每个点只进入队列一次,且进入队列的点的距离严格单调不递减。而同值跳跃的特点是,一旦一个值被访问了(除了开始的点),同值的所有点全部都被访问。所以,一旦发生了同值跳跃,任何同值的都不会再被跳跃。那么当我们跳跃过一个值之后,就可以记录下来,不再跳跃该值。修改之前的代码,得到:

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
      
        vector<int> dis(n, INT_MAX); // 距离
        vector<int> vis(n, 0); // 访问标记
        unordered_map<int, vector<int>> m; // 倒排加速(m既起到了倒排加速作用,又起到了记录值是否被访问的作用,如果有一个值被访问过了,删除该值对应的键)
        for (int i = 0; i < n-1; i++) 
            m[arr[i]].push_back(i);
      
        dis[n-1] = 0; // 最后一个点入队
        queue<int> q;
        q.push(n-1);
      
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (u-1 >= 0 && !vis[u-1] && m.find(arr[u-1]) != m.end()) { // 左跳(其中m判断了该值是否被访问过)
                dis[u-1] = min(dis[u-1], dis[u]+1);
                vis[u-1] = 1;
                q.push(u-1);
            }
            if (u+1 < n && !vis[u+1] && m.find(arr[u+1]) != m.end()) { // 右跳
                dis[u+1] = min(dis[u+1], dis[u]+1);
                vis[u+1] = 1;
                q.push(u+1);
            }
            if (m.find(arr[u]) != m.end()) {
                for (int v: m[arr[u]]) {
                    if (!vis[v]) {
                        vis[v] = 1;
                        dis[v] = min(dis[u]+1, dis[v]);
                        q.push(v);
                    }
                }
                m.erase(arr[u]); // 访问过的值直接清理掉
            }
        }
        return dis[0];
    }
};

时间复杂度分析 O(n)O(n) 每个元素入队出队均只有一次,倒排哈希表的加入和删除都只有一次。

展开全部 14 讨论