Python程式：查詢達到不同奇偶校驗值的最小跳躍次數

假設我們得到一個名為nums的數字列表。如果列表中存在這些值，我們可以從索引i跳到索引i + numbers[i]或i − numbers[i]。因此，我們必須找到至少需要多少次跳躍才能到達另一個奇偶校驗不同的值，同時保持輸入順序不變。如果我們無法到達另一個奇偶校驗不同的數字，則設定為−1。

因此，如果輸入類似於numbers = [7, 3, 4, 5, 6, 9, 6, 7]，則輸出將為[−1, 1, 2, −1, −1, −1, 1, −1]。

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

  • 定義一個函式bfs()。它將接收i作為引數。

    • q := 一個包含(i, 0)對的新雙端佇列

    • seen := 一個新的集合

    • 當q不為空時，執行以下操作：

      • (j, d) := q中最左邊的元素，並從q中刪除最左邊的元素

      • 將j新增到seen中

      • 如果(nums[i] + nums[j]) mod 2不為零，則

        • 返回d

      • 對於每個k ∈ [j + nums[j], j − nums[j]]，執行以下操作：

        • 如果0 <= k < nums的大小且k不在seen中，則

          • 在q的右端插入(k, d + 1)

    • 返回10^10

  • 在主方法中執行以下操作：

  • ans := 一個新的列表

  • 對於i從0到nums的大小的範圍，執行以下操作：

    • seen := 一個新的集合

    • x := bfs(i)

    • 如果x < 10^10，則將x新增到ans中，否則新增−1

  • 返回ans

讓我們看看下面的實現，以便更好地理解：

示例

 線上演示

from collections import deque
class Solution:
   def solve(self, nums):
      def bfs(i):
         q = deque([(i, 0)])
         seen = set()
         while q:
            j, d = q.popleft()
            seen.add(j)
            if (nums[i] + nums[j]) % 2:
               return d
            for k in [j + nums[j], j − nums[j]]:
               if 0 <= k < len(nums) and k not in seen:
                  q.append((k, d + 1))
         return 10 ** 10
      ans = []
      for i in range(len(nums)):
         seen = set()
         x = bfs(i)
         ans.append(x if x < 10 ** 10 else −1)
      return ans
ob = Solution()
print(ob.solve([7, 3, 4, 5, 6, 9, 6, 7]))

輸入

numbers = [7, 3, 4, 5, 6, 9, 6, 7]

輸出

[−1, 1, 2, −1, −1, −1, 1, −1]

更新於：2020年12月26日

瀏覽量：155

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告