leetcode-1345

1VLXNRGJP2$DQ6P.png)

BFS即可，每个节点的相邻节点分别是，左边一个，右边一个，以及相同值的节点：

class Solution:
  def minJumps(self, arr: List[int]) -> int:
    from queue import Queue
    length = len(arr)
    table = dict()
    for idx, x in enumerate(arr):
      if x not in table:
        table[x] = []
      table[x].append(idx)
    vis = [False for _ in range(length)]
    inq = [False for _ in range(length)]
    q = Queue()
    q.put((0, 0))
    inq[0] = True
    g = length - 1
    node = q.get()
    while node[0] != g:
      if not vis[node[0]]:
        vis[node[0]] = True
        if arr[node[0]] in table:
          for x in table[arr[node[0]]]:
            if x != node[0] and not vis[x] and not inq[x]:
              q.put((x, node[1] + 1))
              inq[x] = True
          del table[arr[node[0]]]
        nxt = node[0] + 1
        if not inq[nxt]:
          q.put((nxt, node[1] + 1))
          inq[nxt] = True
        nxt = node[0] - 1
        if nxt > 0 and not inq[nxt]:
          q.put((nxt, node[1] + 1))
          inq[nxt] = True
      node = q.get()
    return node[1]

代码写的比较丑，还有优化的空间。