题目描述
给一个数组arr，起点是0，终点是n-1
有3种选择：可以退一步、进一步、跳到值相等的位置
问跳到终点的最少操作次数？
基本分析
- 为什么是bfs？求从起点到终点的最短路
- 图是什么？当前节点到前、后、等值可跳的索引
- 怎么获取x到所有等值点索引y的映射关系？哈希表预处理
- 怎么保证等值跳一次后不再等值跳了？哈希表中删除x处的值
代码
class Solution:
def minJumps(self, arr: List[int]) -> int:
n = len(arr)
mp = defaultdict(list)
for i in range(n-1, -1, -1):
mp[arr[i]].append(i)
dist = [inf] * n
dist[0] = 0
q = deque([0])
while q:
x = q.popleft()
cnt = dist[x]
if x == n-1:
return cnt
for y in mp[arr[x]]:
if dist[y] == inf:
dist[y] = cnt + 1
q.append(y)
mp.pop(arr[x])
if dist[x+1] == inf:
dist[x + 1] = cnt + 1
q.append(x + 1)
if x > 0 and dist[x - 1] == inf:
dist[x - 1] = cnt + 1
q.append(x - 1)
return -1
总结
- 为了尽快出来，建立哈希表的时候有啥技巧？倒序遍历，最靠后地位置更早入队，如果最后位置是等值跳而来，能更早的出队?
待完善