Pythonで最後のインデックスに到達するための最小ステップ数を見つけるプログラム

numsという番号のリストがあり、現在nums[0]に配置されているとします。各ステップで、現在のインデックスiからi+1またはi-1またはjにジャンプできます。ここでnums[i]==nums[j]です。最終的なインデックスに到達するために必要な最小ステップ数を見つける必要があります。

したがって、入力がnums =[4、8、8、5、4、6、5]の場合、値が両方とも4であるため、インデックス0からインデックス4にジャンプできるため、出力は3になります。次に、インデックス3に戻ります。最後に、両方の値が5であるため、インデックス3から6にジャンプできます。

これを解決するには、次の手順に従います-

• pos：=空の地図
• 各インデックスi、およびnumsの値nについて、実行します
  • pos [n]
  の最後にiを挿入します
• n：=numsのサイズ
• visited：=サイズnのリストを作成し、これにFalseを入力します
• visited [0]：=True
• qが空でない間は、
  • （u、d）：=qの左側の要素、および左側の要素を削除
  • uがn-1と同じ場合、
    • return d
  • リストpos[nums[u]]および[u-1、u + 1]の各vについて、do
    • 0 <=v
    • visited [v]：=True
    • qの最後にペア（v、d + 1）を挿入します
• pos [nums [u]]
を削除します

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, nums):
      from collections import defaultdict, deque
      pos = defaultdict(list)
      for i, n in enumerate(nums):
         pos[n].append(i)
      q = deque([(0, 0)])
      n = len(nums)
      visited = [False] * n
      visited[0] = True
      while q:
         u, d = q.popleft()
         if u == n - 1:
            return d
         for v in pos[nums[u]] + [u - 1, u + 1]:
            if 0 <= v < n and not visited[v]:
               visited[v] = True
               q.append((v, d + 1))
         del pos[nums[u]]
ob = Solution()
nums = [4, 8, 8, 5, 4, 6, 5]
print(ob.solve(nums))

入力

[4, 8, 8, 5, 4, 6, 5]

出力

3