0

## 【LeetCode巧解欣賞】457. Circular Array Loop

cycle的定義是從某一點開始走，可以回到原點。但是cycle只能往同一個方向走，並且長度要大於1才算cycle。

``````Input: [2,-1,1,2,2]
Output: true

Input: [-1,2]
Output: false

Input: [-2,1,-1,-2,-2]
Output: false

``````

# 巧解

``````class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
for i, num in enumerate(nums):
mark = str(i)
while type(nums[i]) == int and num * nums[i] > 0 and nums[i] % len(nums) != 0:
jump = nums[i]
nums[i] = mark
i = (i + jump) % len(nums)
if nums[i] == mark:
return True
return False
``````

## 解析: 如何判斷存在cycle?

``````class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
for i, num in enumerate(nums):
mark = str(i)
print("while外",i,num,nums)
while type(nums[i]) == int and num * nums[i] > 0 and nums[i] % len(nums) != 0:
print("    begin",i,num,nums)
jump = nums[i]
nums[i] = mark
i = (i + jump) % len(nums)
print("    end",i,num,nums)
if nums[i] == mark:
return True
return False
``````

input = `[1,2,-1,1,3,2]`

``````while外 0 1 [1, 2, -1, 1, 3, 2]
begin 0 1 [1, 2, -1, 1, 3, 2]
end 1 1 ['0', 2, -1, 1, 3, 2]
begin 1 1 ['0', 2, -1, 1, 3, 2]
end 3 1 ['0', '0', -1, 1, 3, 2]
begin 3 1 ['0', '0', -1, 1, 3, 2]
end 4 1 ['0', '0', -1, '0', 3, 2]
begin 4 1 ['0', '0', -1, '0', 3, 2]
end 1 1 ['0', '0', -1, '0', '0', 2]
``````

## 解析: 為何設 mark = str(i)而不是常數(e.g. '0')

``````while外 0 -2 [-2, 1, -1, -2, -2]
begin 0 -2 [-2, 1, -1, -2, -2]
end 3 -2 ['0', 1, -1, -2, -2]
begin 3 -2 ['0', 1, -1, -2, -2]
end 1 -2 ['0', 1, -1, '0', -2]
while外 1 1 ['0', 1, -1, '0', -2]
begin 1 1 ['0', 1, -1, '0', -2]
end 2 1 ['0', '1', -1, '0', -2]
while外 2 -1 ['0', '1', -1, '0', -2]
begin 2 -1 ['0', '1', -1, '0', -2]
end 1 -1 ['0', '1', '2', '0', -2]
...
``````

while迴圈結束，