Python程式：查詢到達最後一個索引的最小步數

假設我們有一個名為 nums 的數字列表，我們當前位於 nums[0]。在每一步中，我們可以從當前索引 i 跳到 i + 1 或 i - 1 或 j，其中 nums[i] == nums[j]。我們必須找到到達最終索引所需的最小步數。

因此，如果輸入類似於 nums = [4, 8, 8, 5, 4, 6, 5]，則輸出將為 3，因為我們可以從索引 0 跳到索引 4，因為它們的值都為 4。然後我們跳回索引 3。最後，我們可以從索引 3 跳到 6，因為它們的值都為 5。

為了解決這個問題，我們將遵循以下步驟 -

  • pos := 一個空對映
  • 對於每個索引 i 和 nums 中的值 n，執行以下操作
    • 在 pos[n] 的末尾插入 i
  • n := nums 的大小
  • visited := 建立一個大小為 n 的列表，並用 False 填充它
  • visited[0] := True
  • 當 q 不為空時，執行以下操作
    • (u, d) := q 的左元素，並刪除左元素
    • 如果 u 與 n - 1 相同，則
      • 返回 d
    • 對於 pos[nums[u]] 和 [u - 1, u + 1] 中的每個 v，執行以下操作
      • 如果 0 <= v < n 且 visited[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

更新於: 2020-11-19

458 次瀏覽

開啟您的 職業生涯

完成課程獲得認證

開始學習
廣告