# 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
## 思路
求最少的题目，考虑动态规划，贪心 和 BFS。
这道题没有想到贪心的做法，于是考虑到了动态规划。不过由于**arr\[i] == arr\[j] 且 i != j**也可以转移，因此这里涉及到了一个**连通性变更**的问题，代码会比较难写。
于是继续考虑 BFS。BFS 解题需要考虑三点：
* 初始点。 这里是 0
* 终点。这里是 n - 1，其中 n 为数组长度。
* 节点状态转移。这里是题目列举的三种情况。前两个非常简单，最后一个只需要建立一个 hashtable，将相同值的索引合并到一个 list 即可。具体请看代码。
这里我直接使用 BFS 的模板提交了，结果超时了。用例卡在了 \[7,7,7,7,7,7............] 无数个 7 上。
如果使用标准模板的 BFS，那么每一个 7 都会遍历到其他的所有 7，算法在这种情况下时间复杂度会退化到 $O(N^2)$。其实这里有一个上面讲的**连通性**的问题。如果 7 的 steps 求出来是 x，那么所有的 7 都是 x（不会比 7 大，也不会比 7 小），没有必要继续找了。因此一个剪枝就是遍历到 7 之后就将同值从 hashtable 中都清空。这个剪枝可将时间复杂度直接从 $N^2$ 降低到 $O(N)$。
## 代码
代码支持： Python3
```py
class Solution:
def minJumps(self, A: List[int]) -> int:
dic = collections.defaultdict(list)
n = len(A)
for i, a in enumerate(A):
dic[a].append(i)
visited = set([0])
q = collections.deque([0])
steps = 0
while q:
for _ in range(len(q)):
i = q.popleft()
visited.add(i)
if i == n - 1: return steps
for neibor in dic[A[i]] + [i - 1, i + 1]:
if 0 <= neibor < n and neibor not in visited:
q.append(neibor)
# 剪枝
dic[A[i]] = []
steps += 1
return -1
```
**复杂度分析**
* 时间复杂度：$O(N)$，其中 N 为数组长度。
* 空间复杂度：$O(N)$，其中 N 为数组长度。
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1435.jump-game-iv.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.