[LeetCode] 1345. Jump Game IV #1345

grandyang · 2019-05-30T16:34:59Z

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

i + 1 where: i + 1 < arr.length.
i - 1 where: i - 1 >= 0.
j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You do not need to jump.

Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Constraints:

1 <= arr.length <= 5 * 104
-108 <= arr[i] <= 108

这道题是跳跃游戏 Jump Game 系列的第四道题，这个系列目前至少已经有八道题了，每道题都有些许不同，基本都是跳跃的方式不同，这道题说是每次可以跳到左右相邻的两个位置，以及所有和当前位置上的数字相同的位置。这道题独特的地方就是这个可以跳到和当前位置上数字相同的任意位置，相当于开了一个虫洞，可以连接任意两个点，这也是本题的难点所在。这里求的是到达数组末尾位置的最少跳跃步数，如果把每个位置都当作一个结点，能到达的下一个位置当作与之相连的结点，则左右两个位置，以及相同数字的位置都是相邻的结点，这样看的话数组就变成了一个无向图，则最小步数就是起始结点和目标结点间的最短距离了。

想通了这种转换，就可以通过图的遍历来求最短距离了，这里使用广度优先遍历 BFS 是比较合适的。由于需要遍历每个结点的所有相邻结点，就需要快速知道相同数字的位置都有哪些，这里使用一个 HashMap 来建立每个数字跟所有出现该数字位置的集合之间的映射，只需要遍历一遍原数组，就可以建立好这个 HashMap。之后就是 BFS 的实现了，使用队列 queue 来辅助遍历，队列里放数组坐标，初始化把位置0放进去。BFS 遍历需要避免重复，即需要知道哪些结点已经访问过了，博主最开始想的是用一个布尔型的 visited 数组来记录每个位置是否访问过，但是这种方法最终超时了 Time Limit Exceed，这里需要利用之前建立的 HashMap 来优化一下 BFS。使用一个 while 循环开始 BFS 遍历，因为要求最短距离，这里用一个 for 循环进行层序遍历，一次要处理完每一层的结点。

在 for 循环中，取出队首结点，然后判断是否是末尾位置，是的话就返回结果 res。否则就要将其所有相邻的结点加入队列，先来找左右相邻的结点，左结点存在的条件是当前坐标位置大于0，同时没有被访问过，如何确定没有被访问过呢，就看该位置上的数字是否在 HashMap 中存在（因为最开始时建立了数组中所有数字的映射），存在的话就将左位置排入队列。同理，对右结点进行相同的操作。接下来就是处理相同数字位置了，根据之前建立 HashMap 找到所有相同数字的位置，并进行遍历，将不是当前位置的所有位置排入队列。最后在 HashMap 中将当前数字移除，因为当前数字已经访问完了，这样 HashMap 帮助我们进行去重复操作了。for 循环结束后，结果 res 自增1即可，参见代码如下：

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int res = 0, n = arr.size();
        unordered_map<int, vector<int>> m;
        queue<int> q{{0}};
        for (int i = 0; i < n; ++i) {
            m[arr[i]].push_back(i);
        }
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int t = q.front(); q.pop();
                if (t == n - 1) return res;
                if (t > 0 && m.count(arr[t - 1])) {
                    q.push(t - 1);
                }
                if (t < n - 1 && m.count(arr[t + 1])) {
                    q.push(t + 1);
                }
                if (m.count(arr[t])) {
                    for (int idx : m[arr[t]]) {
                        if (idx != t) {
                            q.push(idx);
                        }
                    }
                }
                m.erase(arr[t]);
            }
            ++res;
        }
        return res;
    }
};

Github 同步地址:

类似题目：

Jump Game VI

Jump Game VII

Jump Game VIII

参考资料：

https://leetcode.com/problems/jump-game-iv/