题目描述

给你一个整数数组 $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

Python 3 代码

from collections import deque 
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        q = deque()
        visite = [False for i  in range(len(arr))]

        # preprocessing
        d = dict()
        for i in range(len(arr)):
            if not arr[i] in d:
                d[arr[i]] = []
            d[arr[i]].append(i)

        q.append((0, 0))
        res = 0
        while len(q) != 0:
            index,depth = q.popleft()
            visite[index] = True

            if index == len(arr) - 1:
                res = depth
                break

            # i+1
            if index + 1 < len(arr) and visite[index + 1] == False:
                q.append((index + 1, depth + 1))
            # i-1
            if index - 1 >= 0 and visite[index - 1] == False:
                q.append((index - 1, depth + 1))
            # arr[i] == arr[j]
            for next_indedx in d[arr[index]]:
                if visite[next_indedx] == False:
                    q.append((next_indedx, depth + 1))
            d[arr[index]] = []
        return res