LeetCode 题解工作台
跳跃游戏 IV
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。 每一步，你可以从下标 i 跳到下标 i + 1 、 i - 1 或者 j ： i + 1 需满足： i + 1 i - 1 需满足： i - 1 >= 0 j 需满足： arr[i] == arr[j] 且 i != j 请你…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
class Solution: def minJumps(self, arr: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
i + 1需满足：i + 1 < arr.lengthi - 1需满足：i - 1 >= 0j需满足：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
解题思路
方法一
class Solution:
def minJumps(self, arr: List[int]) -> int:
g = defaultdict(list)
for i, x in enumerate(arr):
g[x].append(i)
q = deque([0])
vis = {0}
ans = 0
while 1:
for _ in range(len(q)):
i = q.popleft()
if i == len(arr) - 1:
return ans
for j in (i + 1, i - 1, *g.pop(arr[i], [])):
if 0 <= j < len(arr) and j not in vis:
q.append(j)
vis.add(j)
ans += 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) since each index is visited at most once in BFS. Space complexity is O(N) to store the hash table mapping values to indices and the BFS queue. |
| 空间 | \mathcal{O}(N) |
面试官常问的追问
外企场景- question_mark
Candidate immediately considers BFS with value-based jumps.
- question_mark
Candidate correctly prunes visited value groups to prevent repeated traversals.
- question_mark
Candidate discusses time and space trade-offs related to large arrays with duplicates.
常见陷阱
外企场景- error
Failing to clear processed value lists leading to repeated jumps.
- error
Ignoring boundary conditions for i-1 and i+1 jumps at edges of the array.
- error
Attempting DFS instead of BFS, causing inefficient exploration and wrong minimal steps.
进阶变体
外企场景- arrow_right_alt
Allow jumps to multiples of the current value instead of equality, modifying the value map approach.
- arrow_right_alt
Restrict jumps to only equal values, removing i+1 and i-1, emphasizing hash lookup efficiency.
- arrow_right_alt
Count all possible minimal jump sequences instead of only one, extending BFS to track multiple paths.