Python中检查循环周期中是否存在仅前向或仅后向路径的程序

假设我们有一个名为nums的循环链表，那么第一个和最后一个元素是相邻的。因此，从任何索引开始，比如i，如果nums[i]是正值，我们可以向前移动nums[i]步，否则向后移动。我们要检查是否存在长度大于1的循环，该路径只向前或只向后进行。

因此，如果输入是nums = [-1, 2, -1, 1, 2]，则输出将为True，因为存在向前的路径[1 -> 3 -> 4 -> 1]

为了解决这个问题，我们将执行以下步骤 –

n：nums的大小
如果n与0相同，则
- 返回False
seen：大小为n的数组，并填充为0
获取nums中每个元素x的x mod n并更新nums
iter：0
对于i从0到n – 1，执行以下操作
- 如果nums[i]与0相同，则
  - 进行下一个迭代
- iter：= iter + 1
- pos：= True
- neg：= True
- curr：= i
- 重复以下操作，执行
  - 如果nums[curr]和seen[curr]相同，则
  - 返回True
  - 如果seen[curr]不为零，则
  - 退出循环
  - 如果nums[curr] > 0，则
  - neg：= False
  - 否则，
  - pos：= False
  - 如果neg和pos都为false，则
  - 退出循环
  - seen[curr]：= iter
  - curr：=（curr + nums[curr] + n）mod n
  - 如果nums[curr]与0相同，则
  - 退出循环
返回False

例子

让我们看下面的实现，以获得更好的理解 –

def solve(nums):
    n = len(nums)
    if n == 0:
        return False
    seen = [0]*n
    nums = [x % n for x in nums]
    iter = 0
    for i in range(n):
        if nums[i] == 0:
            continue
        iter += 1
        pos = True
        neg = True
        curr = i
        while True:
            if nums[curr] and seen[curr] == iter:
                return True
            if seen[curr]:
                break
            if nums[curr] > 0:
                neg = False
            else:
                pos = False
            if not neg and not pos:
                break
            seen[curr] = iter
            curr = (curr + nums[curr] + n) % n
            if nums[curr]== 0:
                break
    return False

nums = [-1, 2, -1, 1, 2]
print(solve(nums))