Leetcode 1345. Jump Game IV

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

1. Description

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) - 1visited[0] = 0while queue:index, steps = queue.popleft()if index == thres:return stepssteps += 1if index > 0 and index-1 not in visited:visited[index-1] = index - 1queue.append((index-1, steps))if index < thres and index+1 not in visited:queue.append((index+1, steps))visited[index+1] = index + 1if index + 1 == thres:return stepsfor i in mapping[arr[index]]:if i == thres:return stepsif i not in visited:queue.append((i, steps))visited[i] = imapping[arr[index]] = []

• Version 2

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

Reference

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