跳跃游戏 IV

标签: 广度优先搜索 数组 哈希表

难度: Hard

给你一个整数数组 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 * 104
  • -108 <= arr[i] <= 108

Submission

运行时间: 122 ms

内存: 33.1 MB

class Solution:
    def minJumps(self, arr: List[int]) -> int:

        n = len(arr)
        d = defaultdict(list)

        for i, num in enumerate(arr):
            d[num].append(i)
        
        cur = [0]
        step = 0
        dp = [0] + [-1] * (n - 1)
        visited_num = set()
        while cur:
            step += 1
            next = []
            #print(cur)
            for idx in cur:

                l = idx - 1
                r = idx + 1

                if l >= 0 and dp[l] == -1:
                    next.append(l)
                    dp[l] = step
                
                if r < n and dp[r] == -1:
                    next.append(r)
                    dp[r] = step
                
                if arr[idx] not in visited_num:
                    visited_num.add(arr[idx])
                    for pos in d[arr[idx]]:
                        if dp[pos] == -1:
                            next.append(pos)
                            dp[pos] = step
            
            if n - 1 in next:
                break
            
            cur = next
            #print(cur)
            # break
        
        #print(dp)
        return dp[n-1]

Explain

这个问题可以通过使用宽度优先搜索（BFS）来解决。首先，我们使用一个字典 `d` 来存储数组中每个元素的所有下标。接着，我们从数组的第一个元素开始，使用一个队列 `cur` 来保存当前可以访问的下标。每次从队列中取出一个下标，我们都会尝试向左跳（i-1）、向右跳（i+1），以及跳到所有值相同的位置（通过查找字典 `d`）。使用一个数组 `dp` 来记录到达每个下标的最少操作次数，初始时，除了第一个元素设为0以外，其余都设为-1表示未访问。此外，我们使用一个集合 `visited_num` 来记录已经使用过的数字，避免重复访问导致的无效操作。算法的核心在于逐层扩展，直到到达数组的最后一个元素。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minJumps(self, arr: List[int]) -> int:

        n = len(arr)
        d = defaultdict(list) # 存储每个值对应的所有下标

        for i, num in enumerate(arr):
            d[num].append(i)
        
        cur = [0] # BFS的当前层
        step = 0 # 当前步数
        dp = [0] + [-1] * (n - 1) # 存储到每个下标的最少步数
        visited_num = set() # 记录已经访问过的数字，避免重复访问
        while cur:
            step += 1
            next = [] # 下一层节点
            for idx in cur:

                l = idx - 1
                r = idx + 1

                if l >= 0 and dp[l] == -1:
                    next.append(l)
                    dp[l] = step
                
                if r < n and dp[r] == -1:
                    next.append(r)
                    dp[r] = step
                
                if arr[idx] not in visited_num:
                    visited_num.add(arr[idx])
                    for pos in d[arr[idx]]:
                        if dp[pos] == -1:
                            next.append(pos)
                            dp[pos] = step
            
            if n - 1 in next:
                break
            
            cur = next # 更新当前层
        
        return dp[n-1] # 返回到达最后一个元素的最少步数

Explore

在BFS中使用dp数组的主要原因是，它可以帮助在算法执行过程中多次访问同一个下标时，确保我们只记录该下标的最小步数。尽管队列的层数可以表示从起始点到当前层的步数，但是在题目中可能存在多种方式达到同一个位置，步数可能不同。使用dp数组可以存储到达每个位置的最短路径，避免重复和不必要的计算，同时也便于更新和查询每个位置的最短步数。

visited_num集合用来记录已经访问过的数字的目的是为了减少不必要的重复访问和计算，特别是当数组中存在多个相同的元素时。例如，如果一个数字在数组中出现多次，那么在第一次处理这个数字时，我们会探索所有相同值的下标；而后续再次遇到相同的数字时，已经没有必要再次探索，因为这些位置已在第一次被完整考虑过。通常情况下，重复访问相同数字值是不必要的，因为第一次访问已经处理了所有相关的下标，除非这些下标的访问条件在后续操作中发生变化，这在大多数BFS应用场景中是不会发生的。

在宽度优先搜索中，当我们第一次到达目标位置n-1时，我们可以确信找到的是最短路径。这是因为BFS是按层次进行扩展的，确保每次扩展的都是当前步数最少的节点。因此，当我们到达n-1时，根据BFS的性质，那一定是从起点到终点的最短路径。所以，提前终止搜索不会遗漏其他可能的最短路径。

选择在访问过数字后再将其添加到visited_num集合的原因是为了确保在当前层中，所有包含该数字的位置都能被正确处理。如果我们在取出数字时就将其添加到visited_num集合，那么在当前层的后续操作中，如果再次遇到相同的数字，我们将无法访问到该数字的其他下标。这可能会导致错过某些必要的步骤，进而影响到达某些位置的最优解。通过在处理完所有当前层的相同值之后再添加，我们可以确保每个数字在每层中只被处理一次，同时不漏掉任何可能的跳跃。