leetcode 1345. Jump Game IV（python）

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情

描述

Given an array of integers arr, you are initially positioned at the first index of the array. In one step you can jump from index i to index:

• i + 1 where: i + 1 < arr.length.
• i – 1 where: i – 1 >= 0.
• j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
复制代码

Note:

1 <= arr.length <= 5 * 104
-108 <= arr[i] <= 108
复制代码

解析

根据题意，给定一个整数数组 arr，最初位于数组的第一个索引处。在一个步骤中，可以从索引 i 跳转到：

• 索引 i + 1 的位置， 其中：i + 1 < arr.length。
• 索引 i – 1 的位置，其中：i – 1 >= 0。
• 索引 j 的位置，其中：arr[i] == arr[j] 和 i != j。

返回到达数组最后一个索引的最小步数。请注意不能跳出数组。

其实看完题目我们就知道这种题目一般可以用 BFS 暴力解法，因为在到达一个新的位置之后，我们可能跳到包括 +1 、 -1 、 以及所有与其值相同的位置。但是看了 arr 的长度限制后就知道肯定会超时。我们分析一下就知道有一些中间位置在跳过之后就可以无需重跳，我们设置一个 visited 来保存已经访问过的索引。另外为了知道相同值的索引位置，我们可以使用图结构 g 来存储，这样我们不需要便利整个列表来找与下一跳相同值的其他位置，而是只需要访问 g 即可。为了避免回退去找无用的路径，我们在用完某个值之后，将其所在的索引都清空。

解答

class Solution(object):
    def minJumps(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        N = len(arr)
        if N == 1: return 0
        g = {}
        for i in range(N):
            if arr[i] in g:
                g[arr[i]].append(i)
            else:
                g[arr[i]] = [i]
        cur = [0]
        visited = {0}
        result = 0
        while cur:
            nxt = []
            for node in cur:
                if node == N-1: return result
                for child in g[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nxt.append(child)
                while g[arr[node]]:
                    g[arr[node]].pop()
                for child in [node-1, node+1]:
                    if 0<= child < len(arr) and child not in visited:
                        visited.add(child)
                        nxt.append(child)
            cur = nxt
            result += 1
                                    	      
		
复制代码

运行结果

Runtime: 726 ms, faster than 45.61% of Python online submissions for Jump Game IV.
Memory Usage: 29.4 MB, less than 47.37% of Python online submissions for Jump Game IV.
复制代码

原题链接：leetcode.com/problems/ju…

您的支持是我最大的动力