使用 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：一个新集合
- while q 不为空，那么
  - (j，d)：q 的最左元素并删除 q 的最左元素
  - 将 j 添加到 seen 中
  - 如果 (nums[i] + nums[j])mod 2 是非零的，则
  - 返回 d
  - 对于 [j + nums[j]，j – nums[j]] 中的每个 k，执行以下操作 –
  - 如果 0 <= k
    - 在 q 的右端插入 (k，d + 1)
- 返回 10^10
从主方法执行以下操作 –
ans：一个新列表
对于范围为 0 到 nums 大小的 i，执行以下操作 –
- seen：一个新集合
- x：bfs(i)
- 如果 x < 10^10 ，则将 x 添加到 ans 中，否则追加 -1
返回 ans

让我们看一下以下实现，以更好地理解 –

更多Python相关文章，请阅读：Python 教程

示例

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]))