LeetCode 1345. 跳跃游戏 IV

题目描述

给定一个整数数组 arr，你最初位于数组的第一个位置（下标为 0）。

在每一步中，你可以从当前位置 i 跳跃到：

1. i + 1 位置，前提是 i + 1 < arr.length。
2. i - 1 位置，前提是 i - 1 >= 0。
3. 任何一个满足 arr[j] == arr[i] 的位置 j，即可以跳到所有值相等的其他位置。

你的目标是到达数组的最后一个位置（下标为 arr.length - 1），并返回需要的最少跳跃次数。

示例 1：
输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：从下标 0 开始，依次跳转到下标 4 (arr[0] == arr[4])，然后跳转到下标 3 (arr[4] == arr[3])，最后跳转到下标 9 (arr[3] == arr[9])，到达末尾。总共 3 步。

示例 2：
输入：arr = [7]
输出：0
解释：一开始就在最后一个位置，所以不需要跳跃。

解题过程循序渐进讲解

这个问题的核心在于，每次跳跃有三种选择，特别是第三种“跳到所有等值位置”的规则，使得简单的动态规划或贪心策略难以适用。我们需要一种能够高效探索所有可能路径的方法。广度优先搜索（BFS） 是解决此类“最少步数”问题的利器，因为BFS的特性保证了第一次到达目标节点时，所用的步数就是最短的。

步骤 1：分析问题与确定算法框架

1. 状态定义：在这个问题中，我们的“状态”就是当前所在数组的下标 index。我们从状态 0（起始下标）出发，目标是到达状态 arr.length - 1（末尾下标）。
2. 状态转移：从任何一个状态 i，我们可以通过三种方式转移到新状态：
   • i + 1
   • i - 1
   • 所有满足 arr[j] == arr[i] 的 j。
3. 算法选择：由于每次跳跃的代价都是 1（即一步），我们要求的是最少步数。BFS 会像水波纹一样，从起点开始，一层一层地向外扩展。当我们第一次到达终点时，当前的层数（即BFS的深度）就是最少步数。

步骤 2：构建图模型与处理关键点

虽然数组不是一张显式的图，但我们可以将其建模为一张无向图：

• 节点：每个数组下标就是一个节点。
• 边：如果从节点 i 可以一步跳到节点 j（通过上述三种规则之一），那么节点 i 和 j 之间就存在一条边。

这里有一个巨大的优化点：第三种规则（跳到所有等值位置）会创建大量的边。如果我们对于每个节点，都去遍历整个数组寻找等值节点，时间复杂度会非常高（O(n²)），对于大数据量会超时。

关键优化：预处理等值节点索引
我们可以在BFS开始前，用一个哈希表（字典）来记录每个数值对应的所有下标列表。
例如，对于 arr = [100, -23, -23, 404, 100, ...]，我们构建的哈希表类似：

{
  100: [0, 4],
  -23: [1, 2],
  404: [3, 9],
  ...
}

这样，当我们在BFS过程中访问到值为 100 的节点时，我们可以立刻从哈希表中拿到所有值为 100 的节点索引列表。

另一个关键点：避免重复访问
BFS必须记录已经访问过的节点，否则会陷入无限循环（例如在相邻两个节点来回跳）。我们使用一个集合 visited 来记录已经访问过的下标。

步骤 3：详细BFS流程

1. 初始化：

   • 如果数组长度 n 为 1，直接返回 0，因为起点就是终点。
   • 创建一个队列 queue，将起点下标 0 加入队列。
   • 创建一个集合 visited，将 0 加入已访问集合。
   • 创建一个变量 steps 来记录当前的跳跃次数，初始为 0。
   • 构建上述的哈希表 value_to_indices，记录每个数值对应的索引列表。

2. 开始BFS循环：当队列不为空时，继续循环。

   • 记录当前队列的大小 size（当前层的节点数量）。
   • 对于当前层的每一个节点 current_index：
     • 如果 current_index 等于 n-1，说明到达终点，立即返回 steps。
     • 否则，探索从 current_index 可以跳到的所有未被访问过的邻居节点：
       a. 向右跳：next_index = current_index + 1。如果 next_index 在数组范围内且未被访问，则将其加入队列和 visited。
       b. 向左跳：next_index = current_index - 1。如果 next_index 大于等于 0 且未被访问，则将其加入队列和 visited。
       c. 等值跳：根据 arr[current_index] 从哈希表 value_to_indices 中获取所有等值索引列表。遍历这个列表，将其中所有未被访问的索引加入队列和 visited。
     • 极其重要的优化：在完成一次等值跳之后，我们必须将 value_to_indices 中 arr[current_index] 对应的整个列表清空。为什么？
       • 因为BFS是按层扩展的。假设我们在第 k 层第一次访问到某个值为 X 的节点，那么我们会把所有值为 X 的节点都加入到第 k+1 层（如果它们未被访问过）。这意味着，对于数值 X，我们只需要在第一次遇到它时进行等值跳扩展。之后如果再遇到值为 X 的节点，再进行等值跳只会得到已经访问过或即将访问的节点，是冗余操作。清空列表可以避免这种重复的、大规模的无效遍历。这是将时间复杂度从O(n²)降低到O(n)的关键。

3. 处理完一层：当处理完当前层的所有 size 个节点后，将 steps 加 1，表示我们完成了一层（一步）的扩展。

步骤 4：代码实现思路（伪代码）

def minJumps(arr):
    n = len(arr)
    if n == 1:
        return 0

    # 1. 构建等值索引哈希表
    from collections import defaultdict, deque
    value_to_indices = defaultdict(list)
    for i, value in enumerate(arr):
        value_to_indices[value].append(i)

    queue = deque([0])
    visited = set([0])
    steps = 0

    while queue:
        # 处理当前层的所有节点
        size = len(queue)
        for _ in range(size):
            current_index = queue.popleft()

            # 检查是否到达终点
            if current_index == n - 1:
                return steps

            current_value = arr[current_index]

            # 探索邻居：向右
            next_index = current_index + 1
            if 0 <= next_index < n and next_index not in visited:
                visited.add(next_index)
                queue.append(next_index)

            # 探索邻居：向左
            next_index = current_index - 1
            if 0 <= next_index < n and next_index not in visited:
                visited.add(next_index)
                queue.append(next_index)

            # 探索邻居：等值跳
            for neighbor_index in value_to_indices[current_value]:
                if neighbor_index not in visited:
                    visited.add(neighbor_index)
                    queue.append(neighbor_index)

            # 关键优化：清空当前值的索引列表，避免后续重复遍历
            value_to_indices[current_value].clear()

        # 当前层处理完毕，步数+1
        steps += 1

    return -1 # 理论上根据题目总能到达，但代码完整性考虑

总结

这道题的精髓在于将数组跳跃问题转化为图的最短路径问题，并巧妙地使用BFS求解。其核心挑战和优化点在于高效处理“等值跳”规则：

1. 预处理：使用哈希表预先记录等值索引，避免在BFS中O(n)查找。
2. 剪枝：在第一次通过等值跳访问某个数值的所有节点后，清空该数值在哈希表中的记录，防止后续无效的重复遍历。这个优化是算法高效的关键。

通过这种结合了BFS和哈希表预处理的策略，我们可以在O(n)的时间复杂度内解决这个问题。