Skip to content

Latest commit

 

History

History
112 lines (77 loc) · 3.56 KB

1435.jump-game-iv.md

File metadata and controls

112 lines (77 loc) · 3.56 KB

题目地址(1345. 跳跃游戏 IV)

https://leetcode-cn.com/problems/jump-game-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

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 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解