文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書

1. Description

Jump Game IV

2. Solution

解析：Version 1，先用字典保存數(shù)值相同的元素的索引，然后使用廣度優(yōu)先遍歷，初始值為(0, 0)，分別表示索引位置為0以及跳躍次數(shù)1，遍歷當前索引的左邊元素、右邊元素、以及值相同元素的索引，保存索引位置及跳躍次數(shù)，使用visited保存訪問過的索引，相同數(shù)值的索引訪問之后要將字典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/