1345.跳跃游戏IV

链接：1345.跳跃游戏IV
难度：Hard
标签：广度优先搜索、数组、哈希表
简介：请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

题解 1 - cpp

• 编辑时间：2022-01-21
• 执行用时：248ms
• 内存消耗：95.7MB
• 编程语言：cpp
• 解法介绍：bfs。

class Solution {
   public:
    struct node {
        int idx, step;
    };
    int minJumps(vector<int>& arr) {
        unordered_map<int, vector<int>> m;
        unordered_set<int> s;
        s.insert(0);
        queue<node> q;
        q.push((node){0, 0});
        int n = arr.size();
        for (int i = 0; i < n; i++) m[arr[i]].push_back(i);
        while (q.size()) {
            node v = q.front();
            if (v.idx == n - 1) return v.step;
            q.pop();
            if (v.idx > 0 && !s.count(v.idx - 1)) {
                q.push((node){v.idx - 1, v.step + 1});
                s.insert(v.idx - 1);
            }
            if (v.idx < n - 1 && !s.count(v.idx + 1)) {
                q.push((node){v.idx + 1, v.step + 1});
                s.insert(v.idx + 1);
            }
            if (!m.count(arr[v.idx])) continue;
            for (auto& next_idx : m[arr[v.idx]]) {
                if (next_idx == v.idx || s.count(next_idx)) continue;
                q.push((node){next_idx, v.step + 1});
                s.insert(next_idx);
            }
            m.erase(arr[v.idx]);
        }
        return 0;
    }
};