Leetcode 1345. Jump Game IV
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
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/08/11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
