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

开启您的职业生涯

完成课程获得认证

开始学习
广告