假设,我们获得了一个称为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]