leet1345.jump-game-iv

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

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

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

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

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

示例 1：

**输入：**arr = [100,-23,-23,404,100,23,23,23,3,404] **输出：**3 **解释：**那你需要跳跃 3 次，下标依次为 0 ⇒ 4 ⇒ 3 ⇒ 9 。下标 9 为数组的最后一个元素的下标。

示例 2：

**输入：**arr = [7] **输出：**0 **解释：**一开始就在最后一个元素处，所以你不需要跳跃。

示例 3：

**输入：**arr = [7,6,9,6,9,6,9,7] **输出：**1 **解释：**你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。

提示：

• 1 <= arr.length <= 5 * 10^4
• -10^8 <= arr[i] <= 10^8

---

思路

1. 仔细阅读题目，其实是一个图的问题。数组每个节点，代表图的 n 个顶点。每个节点和其前后节点都有边。此外，如果节点上的数值相同，也认为两者之间有一条边。所有边的权重都为 1. 要求从节点 1 到节点 n 的最短路径。
2. 感觉可以用广度优先搜索（BFS），对每个结点，遍历所有可达的节点，记录到达这个节点时权重之和。最先到达节点 n 时的权重之和，就是答案。
3. 用一个 hash 数组记录节点值相同时，对应的索引列表。
4. 队列天然适合层次遍历的场景（BFS，树的层次遍历等）
5. 也可用双队列（参考题解：灵茶山艾府 - BFS）

Code

class Solution {
public:
/*
参考题解
https://leetcode.cn/problems/jump-game-iv/solutions/3963775/bfspythonjavacgo-by-endlesscheng-hyzz
*/
    int minJumps(vector<int>& arr) {
        unordered_map<int, vector<int>> val2idx;
        for (int i = 0; i < arr.size(); ++i) {
            val2idx[arr[i]].push_back(i);
        }
 
        vector<int8_t> visited(arr.size(), 0);
        queue<pair<int, int>> q; // <index, step>
        q.push({0, 0});
        visited[0] = 1;
        while (!q.empty()) {
            auto [idx, step] = q.front();
            q.pop();
            if (idx == arr.size() - 1) return step;
            // 向前跳跃
            if (idx - 1 >= 0 && !visited[idx-1]) {
                q.push({idx - 1, step + 1});
                visited[idx-1] = 1;
            }
            // 向后跳跃
            if (idx + 1 < arr.size() && !visited[idx+1]) {
                q.push({idx + 1, step + 1});
                visited[idx+1] = 1;
            }
            // 等值跳跃
            for (auto next_idx : val2idx[arr[idx]]) {
                if (!visited[next_idx]) {
                    q.push({next_idx, step + 1});
                    visited[next_idx] = 1;
                }
            }
            // add this to avoid TLE.
            val2idx.erase(arr[idx]);
        }
        return -1;
    }
};