Leetcode 1345. Jump Game IV

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Jump Game IV

2. Solution

解析：Version 1，先用字典保存数值相同的元素的索引，然后使用广度优先遍历，初始值为(0, 0)，分别表示索引位置为0以及跳跃次数1，遍历当前索引的左边元素、右边元素、以及值相同元素的索引，保存索引位置及跳跃次数，使用visited保存访问过的索引，相同数值的索引访问之后要将字典mapping中保持的索引序列也重置。Version 2代码稍微简洁一些。

• Version 1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        visited = {}
        mapping = collections.defaultdict(list)
        for index, value in enumerate(arr):
            mapping[value] += [index]
        queue = collections.deque()
        queue.append((0, 0))
        thres = len(arr) - 1
        visited[0] = 0
        while queue:
            index, steps = queue.popleft()
            if index == thres:
                return steps
            steps += 1
            if index > 0 and index-1 not in visited:
                visited[index-1] = index - 1
                queue.append((index-1, steps))
            if index < thres and index+1 not in visited:
                queue.append((index+1, steps))
                visited[index+1] = index + 1
                if index + 1 == thres:
                    return steps
            for i in mapping[arr[index]]:
                if i == thres:
                    return steps
                if i not in visited:
                    queue.append((i, steps))
                    visited[i] = i
            mapping[arr[index]] = []

• Version 2

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return 0
        visited = {}
        mapping = collections.defaultdict(list)
        for index, value in enumerate(arr):
            mapping[value] += [index]
        queue = collections.deque()
        queue.append((0, 0))
        thres = len(arr) - 1
        visited[0] = 0
        while queue:
            index, steps = queue.popleft()
            steps += 1
            temp = set([index-1, index + 1] + mapping[arr[index]])
            for i in temp:
                if i == thres:
                    return steps
                if i not in visited and i > -1 and i < len(arr):
                    queue.append((i, steps))
                    visited[i] = i
            mapping[arr[index]] = []

Reference

1. https://leetcode.com/problems/jump-game-iv/