用 Python 编写程序检查循环列表中是否存在前向路径

pythonserver side programmingprogramming更新于 2026/1/11 11:56:17

假设我们有一个名为 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
对于范围为 0 到 n - 1 的 i，执行
- 如果 nums[i] 与 0 相同，则
  - 进行下一次迭代
- iter := iter + 1
- pos := True
- neg := True
- curr := i
- 重复执行以下操作，do
  - 如果 nums[curr] 和 seen[curr] 与 iter 相同，则
    - 返回 True
  - 如果 seen[curr] 非零，则
    - 退出循环
  - 如果 nums[curr] > 0，则
    - neg := False
  - 否则，
    - pos := False
  - 如果 neg 和 pos 都为假，则
    - 退出循环
  - 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))