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