Leetcode 1345:跳跃游戏IV(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1345:跳跃游戏IV(超详细的解法!!!)

in leetcode with 0 comment

给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。

每一步,你可以从下标 i 跳到下标:

请你返回到达数组最后一个元素的下标处所需的 最少操作次数

注意:任何时候你都不能跳到数组外面。

示例 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

提示:

解题思路

最少操作次数问题,那么可以考虑通过bfs来处理,接着思考一下时间复杂度是不是合理。按照题目中的意思是所有相同值的点可以相互跳,那么就相当于所有相同的值都构建边,总共可能有$\sum_{i=1}^ni=n*(n+1)/2$条边。如果采用bfs遍历的话,那么必然会超时。

此时,我们已经知道了问题就出在相同值上,那么该如何处理这个问题呢?对于连续相同大小的点,我们将其压缩成一个点来处理(因为结果是一样的)。还需要注意一点,数组的第一个元素需要单独考虑

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1: return 0
        
        ne, vis, t = collections.defaultdict(set), [0] * n, 0
        indexs = [arr[0], arr[1]]
        for i in range(2, n):
            if arr[i] != arr[i - 1]:
                indexs.append(arr[i])
                
        for i, v in enumerate(indexs):
            ne[v].append(i)
                
        q, step, ni = [0], 0, len(indexs)
        vis[0] = 1
        while q:
            k = len(q)
            for _ in range(k):
                pre = q.pop(0)
                if pre == ni - 1: return step
                
                for i in ne[indexs[pre]] + [pre + 1, pre - 1]:
                    if vis[i] or not (0 <= i < ni): continue
                    vis[i] = 1
                    q.append(i)
            step += 1
        return step

实际上还可以更加简洁。对于相同的点,如果一个点(值)可达了,那么其他相同的值都可达。所以,我们可以通过数据结构记录哪些值被访问过了,对于访问过的值就不用再访问了;而对于未访问的值,我们只要将和其相同的值都加入队列。

arr: 7 7 7 7 7 11
q: 0(7)
values: 

注意队列q中存放的是值的index,用values存放那些值访问过了。此时我们需要将0弹出,然后将7加入values,同时所有7index都添加到q中。通过这种操作,我们所有相同的值都只访问了一遍。

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        g, n = collections.defaultdict(list), len(arr)
        for i, v in enumerate(arr):
            g[v].append(i)
        
        vis, values = [0] * n, set()
        q, vis[0], step = [0], 1, 0
        
        while q:
            k = len(q)
            for _ in range(k):
                pre = q.pop(0)
                if pre == n - 1: return step
                
                for i in [pre - 1, pre + 1]:
                    if 0 <= i < n and not vis[i]:
                        vis[i] = 1
                        q.append(i)
                
                if arr[pre] in values: continue
                values.add(arr[pre])
                for i in g[arr[pre]]:
                    if not vis[i]:
                        vis[i] = 1
                        q.append(i)
            step += 1
        return step

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses