1345. 跳跃游戏 IV

Difficulty
Hard
Tags
BFS
URL
https://leetcode-cn.com/problems/jump-game-iv/
Star
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标：
  • i + 1 满足：i + 1 < arr.length
  • i - 1 满足：i - 1 >= 0
  • j 满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
示例 1：
输出：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^4
  • 10^8 <= arr[i] <= 10^8
通过次数11,001提交次数26,144

法 1 BFS

思路
看作有向无权图的搜索问题。
每一步将当前节点的邻居节点添加到队列中。
因为是最少操作次数，所以很自然的想到 BFS
题解
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        hash_map = collections.defaultdict(list)
        # 将相同元素存进来
        for i in range(0, len(arr)):
            hash_map[arr[i]].append(i)

        # 当前 索引 和 下标
        queue = deque()
        queue.append((0, 0))
        
        # 记录是否遍历过
        visited = [False] * len(arr)
        visited[0] = True

        while queue:
            index, step = queue.popleft()
            if index == len(arr) - 1:
                return step

            # 向前走
            if index + 1 < len(arr) and visited[index+1] == False:
                queue.append((index + 1, step + 1))
                visited[index + 1] = True

            # 向 后走
            if index - 1 >= 0 and visited[index-1] == False:
                queue.append((index - 1, step + 1))
                visited[index - 1] = True

            # 走相同的元素
            for i in hash_map[arr[index]]:
                if visited[i] == False:
                    queue.append((i, step+1))
                    visited[i] = True
						# 记得要将 这个移除掉！！
            hash_map.pop(arr[index])

        return -1