T1345.跳跃游戏 IV

bfs, hash table, https://leetcode.cn/problems/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，可以使用 广度优先搜索 (BFS) 来找到从起点（下标 0）到终点（下标 n-1）的最少操作次数。

解题思路

构建邻接信息：为了快速找到所有与当前元素值相同的下标，需要预先遍历数组，用一个哈希表（字典）存储每个数值对应的所有下标。例如：pos = {100: [0, 4], -23: [1, 2], ...}。
BFS 过程：
- 使用队列 queue 存储 (当前下标, 当前步数)。
- 使用一个集合 visited 记录已经访问过的下标，防止重复访问导致死循环。
- 在每一轮 BFS 中，从当前下标 i 可以跳向三个方向：
  - i + 1
  - i - 1
  - 所有 j 使得 arr[j] == arr[i] 且 j != i。
性能优化（关键）：
- 同值跳跃优化：当我们第一次通过数值 arr[i] 跳跃到其他相同数值的下标后，必须从哈希表中移除该数值对应的下标列表。
- 原因：如果以后再次遇到相同数值的元素，已经知道通过这个数值能到达的所有位置都已经被加入队列或者访问过了，如果不移除，程序会反复遍历相同的下标列表，导致时间复杂度退化到 $O (N^{2})$ 。

Python 代码实现

python

from collections import deque, defaultdict

class Solution:
    def minJumps(self, arr: list[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0
        
        # 1. 记录每个值对应的所有下标
        pos = defaultdict(list)
        for i, val in enumerate(arr):
            pos[val].append(i)
            
        # 2. BFS 初始化
        # queue 存储 (当前下标, 步数)
        queue = deque([(0, 0)])
        visited = {0}
        
        target = n - 1
        
        while queue:
            idx, step = queue.popleft()
            
            # 如果到达终点，直接返回步数
            if idx == target:
                return step
            
            v = arr[idx]
            step += 1
            
            # 情况 1: 跳到相同值的其他下标
            if v in pos:
                for j in pos[v]:
                    if j not in visited:
                        if j == target: return step
                        visited.add(j)
                        queue.append((j, step))
                # 优化：处理完该值后，从字典中删除，防止重复遍历
                del pos[v]
            
            # 情况 2: 向后跳一步 (i + 1)
            if idx + 1 < n and (idx + 1) not in visited:
                if idx + 1 == target: return step
                visited.add(idx + 1)
                queue.append((idx + 1, step))
                
            # 情况 3: 向前跳一步 (i - 1)
            if idx - 1 >= 0 and (idx - 1) not in visited:
                visited.add(idx - 1)
                queue.append((idx - 1, step))
                
        return -1

复杂度分析

时间复杂度： $O (N)$ 。
- 建立哈希表需要 $O (N)$ 。
- 在 BFS 中，每个下标最多入队一次。
- 由于我们处理完一个数值后就将其从 pos 中删除，因此 pos[v] 中的每个元素也只会被遍历一次。
空间复杂度： $O (N)$ 。
- 用于存储哈希表、队列和已访问集合。

为什么这个优化很重要？

考虑数组 [7, 7, 7, 7, ..., 7] (5万个7)。如果不执行 del pos[v]，当你处理第一个 7 时，你会检查后面 49999 个位置；当你处理第二个 7 时，你又会检查后面 49999 个位置... 最终会导致超时。执行删除操作后，每个位置和每条“同值边”只被访问常数次。

T1345.跳跃游戏 IV ​

T1345.跳跃游戏 IV