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，对于nums中的每个元素x，获取x mod n
  • iter := 0
  • 对于从0到n-1的i，执行：
    • 如果nums[i]等于0，则
      • 进行下一次迭代
    • iter := iter + 1
    • pos := True
    • neg := True
    • curr := i
    • 重复执行以下操作：
      • 如果nums[curr]和seen[curr]等于iter，则
        • 返回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))

输入

[-1, 2, -1, 1, 2]

输出

True

更新于：2021年10月16日

199 次浏览

开启你的职业生涯

完成课程后获得认证

开始学习
广告