2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

1345. 跳跃游戏 IV

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

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

• 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 处，也就是数组的最后一个元素处。

示例 4：

输入：arr = [6,1,9]
输出：2

示例 5：

输入：arr = [11,22,7,7,7,7,7,7,7,22,13]
输出：3

提示：

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

哈希加速bfs

乍一看是很简单的bfs。但是实际上正常来做的话会超时。

大量test case里包含了很多重复的数值，导致会做很多无用的bfs。

bfs的方向很简单,i + 1 或者 i - 1，或者和arr[i]相等的位置j，三种情况。

我们可以用哈希表来储存同一个数字出现的所有坐标

unordered_map<int, vector<int>> m;
int n = arr.size();
for (int i = 0; i < n; i++) {
    m[arr[i]].push_back(i);
}

对于每个坐标我们有以下判断，首先从哈希表里找到所有和该坐标数值相等的坐标。

vector<int>& nextPoint = m[arr[idx]]; 

这里取引用的原因是，对于每个重复的点，其实我们只需要把他们放进queue里一次，就可以cover住我们所有的可能的状态，并且把他们放进queue里。剩下的就不必在考虑了。需要的点推进queue里之后，我们可以

nextPoint.clear();  

来清除哈希表里所有与当前数字值相等的坐标，避免重复讨论导致的TLE。

别忘了坐标还可以左右横跳，这个很简单，只要判断idx够不够我们+1 - 1即可。

if (idx > 0)  nextPoint.push_back(idx - 1);
if (idx < n - 1) nextPoint.push_back(idx + 1); 

之后遍历nextPoint数组，记得clear即可。

完整代码

class Solution {
public:
    int minJumps(vector<int>& arr) {
        unordered_map<int,vector<int>> m;
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            m[arr[i]].push_back(i);
        }
        vector<bool>visited (n, false);
        visited[0] = true;
        queue<pair<int, int>> q; 
        q.emplace(0, 0);
        while (!q.empty()) {
            auto [idx, step] = q.front();  q.pop();
            if (idx == n - 1) return step;
            vector<int>& nextPoint = m[arr[idx]];
            if (idx > 0) nextPoint.push_back(idx - 1);
            if (idx < n - 1)  nextPoint.push_back(idx + 1); 
            for (int i = 0; i < nextPoint.size(); i++) {
                if (visited[nextPoint[i]]) continue;
                q.emplace(nextPoint[i], step + 1);
                visited[nextPoint[i]] = true;
            }
            nextPoint.clear(); 
        }
        return -1;
    }
};