leetcode 457 Circular Array Loop
z
 2019-06-10 17:13:53  

You are given a circular array nums of positive and negative integers. If a number k at an index is positive, then move forward k steps. Conversely, if it’s negative (-k), move backward k steps. Since the array is circular, you may assume that the last element’s next element is the first element, and the first element’s previous element is the last element.

Determine if there is a loop (or a cycle) in nums. A cycle must start and end at the same index and the cycle’s length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

Example 1:

1
2
3
Input: [2,-1,1,2,2]
Output: true
Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.

Example 2:

1
2
3
Input: [-1,2]
Output: false
Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.

Example 3:

1
2
3
Input: [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.

Note:

  1. -1000 ≤ nums[i] ≤ 1000
  2. nums[i] ≠ 0
  3. 1 ≤ nums.length ≤ 5000

遍历nums，对每一个nums[i]开始循环遍历他的下一跳。

中断条件包括：

  1. 当这一跳的方向和初始的方向不一致，设初始的数为num，当前这一跳的数为nums[i]，那么当num*nums[i] <=0时，中断。
  2. 当这一跳调到自己时，中断。即nums[i] % len(nums) == 0时，中断。
  3. 当这一跳曾经跳过时，中断。在跳的过程中，我们用标记来标注跳过的位置，如果当前这一跳被标记上跳过了，那么中断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def circularArrayLoop(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        for i, num in enumerate(nums):
            mark = str(i) # 注意这里用到的标记是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 = (jump + i) % len(nums)
            if nums[i] == mark:
                return True
        return False