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,則
- 退出迴圈
- 如果nums[curr]和seen[curr]等於iter,則
- 如果nums[i]等於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
廣告