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 次瀏覽

開啟你的職業生涯

完成課程後獲得認證

開始學習
廣告