题目

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标：

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

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

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

来源：力扣（LeetCode）

解答

遍历时，有三个方向，一个是向左，一个是向右，一个是跳向等值的数。

从头开始进行BFS即可，同时利用哈希表来遍历等值的元素。

具体代码及思路如下：

class Solution {
public:
    int minJumps(vector<int> &arr) {
        int n = arr.size();
        unordered_map<int, vector<int>> mp; // 记录相同值所包含的下标都有几个
        vector<int> all(n, -1); // 记录每一个位置最小步数
        queue<int> q; // 记录遍历内容

        // 将arr所有值对应下标记录到哈希表中，通过倒序记录，保证map先访问的是同值的最后一个元素
        for (int i = n - 1; i >= 0; --i) {
            mp[arr[i]].push_back(i);
        }

        all[0] = 0;   // 起止点在0，所以第一个值步数为0
        q.push(0); // 从第0个下标开始遍历，将其放入队列

        // 队列不空，表示未遍历完或未达到最后一个值
        while (!q.empty()) {
            // 元素出队，表示当前遍历到的元素
            auto cur = q.front(); // 当前遍历下标
            q.pop();

            if (cur == n - 1) {
                return all[cur];
            }

            // 检查右侧元素
            // == -1 表示未到达过
            if (cur + 1 < n && all[cur + 1] == -1) {
                q.push(cur + 1);
                all[cur + 1] = all[cur] + 1;
            }

            // 左侧元素
            if (cur - 1 >= 0 && all[cur - 1] == -1) {
                q.push(cur - 1);
                all[cur - 1] = all[cur] + 1;
            }

            // 等值元素
            auto same = mp[arr[cur]];
            for (auto tmp: same) {
                if (all[tmp] == -1) {
                    q.push(tmp);
                    all[tmp] = all[cur] + 1;
                }
            }

            // 将等值元素都删除，因为已经更新过步数了，
            // 如果后续还遇到该值，更新步数一定大于当前更新值（这样做是错误的）
            // 所以直接从哈希表中去除
            mp.erase(arr[cur]);
        }
        return -1;
    }
};