1345：跳跃游戏 IV（1809 分）

Ian

2020-02-08 约 470 字预计阅读 1 分钟次阅读

力扣第 19 场双周赛第 4 题

题目

给你一个整数数组 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 * 10⁴
-10⁸ <= arr[i] <= 10⁸

相似问题：

分析

bfs 即可，注意一个值访问过就将列表清空

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        d = defaultdict(list)
        for i,x in enumerate(arr):
            d[x].append(i)
        Q, vis = deque([(0,0)]), {0}
        while Q:
            w,u = Q.popleft()
            if u==n-1:
                return w
            for v in chain(d[arr[u]], [u-1,u+1]):
                if 0<=v<n and v not in vis:
                    Q.append((w+1,v))
                    vis.add(v)
            d[arr[u]].clear()

367 ms

目录

1345：跳跃游戏 IV（1809 分）

题目

分析

解答