程序查找在Python中达到具有不同奇偶校验值的最小跳转

假设，我们获得了一个称为nums的数字列表。如果列表中存在值，则可以从索引i跳转到索引i +数字[i]或从索引i跳转到i −数字[i]。因此，我们必须找到至少要达到另一个具有不同奇偶校验值的跳跃数，以保持输入顺序不变。如果我们无法获得另一个具有不同奇偶校验的数字，则将其设置为-1。

因此，如果输入就像数字= [7、3、4、5、6、9、6、7]，那么输出将为[-1、1、2，-1，-1，-1、1 ，-1]。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个功能bfs()。这需要我

• (j,d)：= q的最左边元素并从q删除最左边的项目

• 将j添加到看到的

• 如果（nums [i] + nums [j]）mod 2非零，则

• 对于[j + nums [j]，j − nums [j]]中的每个k，

• 返回d

• 在q的右端插入（k，d + 1）

• 如果0 <= k <num的大小并且看不到k，则

• q：=有一对(i,0)的新双头队列

• 看过：=一套新的

• 当q不为空时，执行

• 返回10 ^ 10

• 从主要方法中执行以下操作-

• ans：=一个新列表

• 对于范围从0到nums的i，执行

• 看过：=一套新的

• x：= bfs(i)

• 当x <10 ^ 10时在ans中附加x，否则附加-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]