leetcode-1345. 跳跃游戏 IV

本文主要是介绍leetcode-1345. 跳跃游戏 IV，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给你一个整数数组 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^4
-10^8 <= arr[i] <= 10^8

解题思路

可以把这道题看作是无向图中求最短路径的问题，用BFS，每次在队列中加入从当前节点能跳到的其他节点，及跳跃次数。第一个跳到结尾的，就是跳跃次数最短的方案。

The time complexity of bfs is $o (V + E)$ , and in this condition, the $V = n$ , $E=n^2$ because in the worst case where all the nodes are the same, then there will be a path between every two points. So the bfs will spend a lot of time exploring the subgraph.

In order to avoid such problems, after we first deal with the sub-graph, we could delete it, so next time when we encounter other points in that subgraph, we only iterate the left and right neighbor of the point, instead of all the other points in the sub-graph.

代码

class Solution:def minJumps(self, arr: List[int]) -> int:value_index = {}for index, value in enumerate(arr):if value not in value_index:value_index[value] = []value_index[value].append(index)queue = collections.deque([(0, 0)]) # [(index, step), ...]visited_nodes = set()while queue:node, step = queue.popleft()if node == len(arr) - 1:return stepif node in visited_nodes:continuevisited_nodes.add(node)neighbor_nodes = value_index.get(arr[node], [])if node - 1 >= 0 and node - 1 not in neighbor_nodes:queue.append((node - 1, step + 1))if node + 1 < len(arr) and node + 1 not in neighbor_nodes:queue.append((node + 1, step + 1))for each_neighbor in neighbor_nodes:queue.append((each_neighbor, step + 1))value_index.pop(arr[node], None)