1345. 跳跃游戏 IV : 关于首次等值跳后移除元素的正确性证明（含双向 BFS）-阿里云开发者社区

网络异常，图片无法展示

题目描述

这是 LeetCode 上的 1345. 跳跃游戏 IV ，难度为困难。

Tag : 「图论 BFS」、「双向 BFS」

给你一个整数数组 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^41<=arr.length<=5∗104
-10^8 <= arr[i] <= 10^8−108<=arr[i]<=108

单向 BFS

根据跳跃规则，我们能够进行「前后跳」和「等值跳」，问题为到达结尾位置的最少步数，容易想到 BFS。

为了方便进行「等值跳」，我们可以先使用「哈希表」记录某个值有哪些下标。

在进行 BFS 时，假如当前走到的位置为 tt，我们尝试将 t - 1t−1、t + 1t+1 和与 arr[t]arr[t] 等值的位置进行入队，为了防止重复同队，我们可以使用 distdist 数组记录到达某个位置的最小步数（初始化为 INF），只有 dist[ne]dist[ne] 为 INF 时，该点没有被遍历过，可以入队并更新最小步数。

但光使用 distdist 还不能确保复杂度为 O(n)O(n)，因为每次都需要遍历与 arr[t]arr[t] 等值的下标，为确保等值下标的遍历只会发生一次，我们需要在将等值下标添加到队列后，将 arr[t]arr[t] 从哈希表中移除。

容易证明每次将于 arr[t]arr[t] 的等值元素添加到队列后，将 arr[t]arr[t] 从哈希表中移除的正确性：

首次检索到 arr[t]arr[t] 值时，必然是最小步数，记为 stepstep，此时 BFS 做法将其他等值下标距离更新为 step + 1step+1：

若 arr[t]arr[t] 与结尾元素值相等，且 tt 为 n - 1n−1，此时 stepstep 即是答案；
若arr[t]arr[t]与结尾元素值相等，但tt不为n - 1n−1，此时会再跳一步到达结尾位置，即step + 1step+1为答案。那么是否可能存在使用比step + 1step+1更小的步数，也能到达结尾的位置呢？答案是：可能存在，但如果最后是通过「等值跳」到达结尾位置的话，不可能存在比 step + 1step+1 更小的步数。由于我们每次加入等值时都会进行哈希表的移除，因此到达tt的方式不可能是「等值跳」，而只能是「前后跳」。

假设是通过前跳到达位置 tt，即点分布如图，步数满足等于 step + 1step+1：

网络异常，图片无法展示
|

假设是通过后跳到达位置 tt，即点分布如图，步数满足「如果是等值跳到达结尾，步数为 step + 1step+1」：

网络异常，图片无法展示
|

综上，如果 n - 1n−1 是经过「等值跳」加入队列的话，起所能达到的最小步数必然为发起点 tt 的最小步数 +1+1。
也就是说，即使首次等值跳，加入队列后会将其从哈希表中进行移除，正确性也是可以保证的。

基于此，我们可以额外增加一个 trick，就是在构建哈希表的时候，使用「倒序」的形式构建等值下标列表，这样可以确保如果最后位置是通过「等值跳」而来是，能够优先出队。

代码（感谢 @Benhao 和 @🍭可乐可乐吗同学提供的其他语言版本）：

class Solution {
    int INF = 0x3f3f3f3f;
    public int minJumps(int[] arr) {
        int n = arr.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        // 倒序插入 list，相当于给 deque 增加一个同层「下标越大，优先出队」的作用
        for (int i = n - 1; i >= 0; i--) { 
            List<Integer> list = map.getOrDefault(arr[i], new ArrayList<>());
            list.add(i);
            map.put(arr[i], list);
        }
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(0);
        dist[0] = 0;
        while (!d.isEmpty()) {
            int t = d.pollFirst(), step = dist[t];
            if (t == n - 1) return step;
            if (t + 1 < n && dist[t + 1] == INF) {
                d.addLast(t + 1);
                dist[t + 1] = step + 1;
            }
            if (t - 1 >= 0 && dist[t - 1] == INF) {
                d.addLast(t - 1);
                dist[t - 1] = step + 1;
            }
            List<Integer> list = map.getOrDefault(arr[t], new ArrayList<>());
            for (int ne : list) {
                if (dist[ne] == INF) {
                    d.addLast(ne);
                    dist[ne] = step + 1;
                }
            }
            map.remove(arr[t]);
        }
        return -1; // never
    }
}
复制代码

class Solution {
public:
    int minJumps(vector<int>& arr) {
        const int inf = 0x3f3f3f3f;
        int n = arr.size();
        unordered_map<int, vector<int>> map;
        for(int i = n - 1; ~i; i--) {
            map[arr[i]].push_back(i);
        }
        vector<int> dist(n, inf);
        queue<int> q;
        q.push(0);
        dist[0] = 0;
        while(q.size()) {
            auto t = q.front(), step = dist[t];
            q.pop();
            if(t == n - 1) return step;
            if(t + 1 < n and dist[t + 1] == inf) {
                q.push(t + 1);
                dist[t + 1] = step + 1;
            }
            if(t - 1 >= 0 and dist[t - 1] == inf) {
                q.push(t - 1);
                dist[t - 1] = step + 1;
            }
            const auto& list = map[arr[t]];
            for(auto ne :list) {
                if(dist[ne] == inf) {
                    q.push(ne);
                    dist[ne] = step + 1;
                }
            }
            map[arr[t]].clear(); //or map.erase(arr[t]);
        }
        return -1;
    }
};
复制代码

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        mp = defaultdict(list)
        for i, num in enumerate(arr):
            mp[num].append(i)
        dist = [inf] * n
        d = deque([0])
        dist[0] = 0
        while len(d) > 0:
            t = d.popleft()
            step = dist[t]
            if t == n - 1:
                return step
            for ne in mp[arr[t]]:
                if dist[ne] == inf:
                    d.append(ne)
                    dist[ne] = step + 1
            mp.pop(arr[t])
            if dist[t + 1] == inf:
                d.append(t + 1)
                dist[t + 1] = step + 1
            if t and dist[t - 1] == inf:
                d.append(t - 1)
                dist[t - 1] = step + 1
        return -1
复制代码

const INF int = 0x3f3f3f3f
func minJumps(arr []int) int {
    n := len(arr)
    mp := map[int][]int{}
    dist := make([]int, len(arr))
    for i := 0; i < n; i++{
        list := mp[arr[i]]
        list = append(list, i)
        mp[arr[i]] = list
        dist[i] = INF
    }
    d := []int{0}
    dist[0] = 0
    for len(d) > 0{
        t := d[0]
        step := dist[t]
        if t == n - 1{
            return step
        }
        d = d[1:]
        list := mp[arr[t]]
        delete(mp, arr[t])
        list = append(list, t + 1)
        if t > 0 {
            list = append(list, t - 1)
        }
        for _, ne := range list {
            if dist[ne] == INF {
                dist[ne] = step + 1
                d = append(d, ne)
            }
        }
    }
    return -1
}
复制代码

时间复杂度：预处理出 map 的复杂度为 O(n)O(n)；跑一遍 BFS 得到答案复杂度为 O(n)O(n)。整体复杂度为 O(n)O(n)
空间复杂度：O(n)O(n)

双向 BFS

自然也能够使用「双向 BFS」进行求解。

不了解「双向 BFS」的同学，可以先看前置🧀：【图论搜索专题】如何使用「双向 BFS」解决搜索空间爆炸问题 & 【图论搜索专题】双向 BFS 模板题。

双向 BFS 能够有效解决搜索空间爆炸问题，本题使用双向 BFS 的话，可以不进行哈希表的 remove 操作。

代码：

class Solution {
    int[] arr;
    int INF = 0x3f3f3f3f;
    int n;
    Map<Integer, List<Integer>> map = new HashMap<>();
    public int minJumps(int[] _arr) {
        arr = _arr;
        n = arr.length;
        if (n == 1) return 0;
        for (int i = n - 1; i >= 0; i--) {
            List<Integer> list = map.getOrDefault(arr[i], new ArrayList<>());
            list.add(i);
            map.put(arr[i], list);
        }
        Deque<Integer> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
        int[] dist1 = new int[n], dist2 = new int[n];
        Arrays.fill(dist1, INF);
        Arrays.fill(dist2, INF);
        d1.addLast(0);
        dist1[0] = 0;
        d2.addLast(n - 1);
        dist2[n - 1] = 0;
        while (!d1.isEmpty() && !d2.isEmpty()) {
            int t = -1;
            if (d1.size() < d2.size()) t = update(d1, d2, dist1, dist2);
            else t = update(d2, d1, dist2, dist1);
            if (t != -1) return t;
        }
        return -1; // never
    }
    int update(Deque<Integer> d1, Deque<Integer> d2, int[] dist1, int[] dist2) {
        int m = d1.size();
        while (m-- > 0) {
            int t = d1.pollFirst(), step = dist1[t];
            if (t + 1 < n) {
                if (dist2[t + 1] != INF) return step + 1 + dist2[t + 1];
                if (dist1[t + 1] == INF) {
                    d1.addLast(t + 1);
                    dist1[t + 1] = step + 1;
                }
            }
            if (t - 1 >= 0) {
                if (dist2[t - 1] != INF) return step + 1 + dist2[t - 1];
                if (dist1[t - 1] == INF) {
                    d1.addLast(t - 1);
                    dist1[t - 1] = step + 1;
                }
            }
            List<Integer> list = map.getOrDefault(arr[t], new ArrayList<>());
            for (int ne : list) {
                if (dist2[ne] != INF) return step + 1 + dist2[ne];
                if (dist1[ne] == INF) {
                    d1.addLast(ne);
                    dist1[ne] = step + 1;
                }
            }
            map.remove(arr[t]);
        }
        return -1;
    }
}
复制代码

时间复杂度：O(n)O(n)
空间复杂度：O(n)O(n)

其他「图论搜索 / 模拟」内容

题太简单？不如来学习热乎的简单图论搜索题 🍭🍭🍭

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1345 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

1345. 跳跃游戏 IV : 关于首次等值跳后移除元素的正确性证明（含双向 BFS）

题目描述

单向 BFS

双向 BFS

其他「图论搜索 / 模拟」内容

最后

热门文章

最新文章

相关电子书

相关实验场景