0457._Circular_Array_Loop.md

457. Circular Array Loop

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/circular-array-loop/description/

内容描述

You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it's negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be "forward" or "backward'.

Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.

Example 2: Given the array [-1, 2], there is no loop.

Note: The given array is guaranteed to contain no element "0".

Can you do it in O(n) time complexity and O(1) space complexity?

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

快慢指针，然后要注意的是如果loop只有一个元素不算loop，每次找完一圈后发现没有找到的话要将这一路上经过的点全都设为0防止下次重复查找了

class Solution(object):
    def circularArrayLoop(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        def get_next_idx(i):
            n = len(nums)
            return (i + nums[i] + n) % n

        for i, val in enumerate(nums):
            if val == 0:
                continue

            slow = i
            fast = get_next_idx(i)
            # make sure always forward or always backward
            while nums[fast] * val > 0 and nums[get_next_idx(fast)] * val > 0: 
                if slow == fast:
                    # exclude for loop with only one element
                    if slow == get_next_idx(slow):
                        break
                    return True

                slow = get_next_idx(slow)
                fast = get_next_idx(get_next_idx(fast))

            slow = i
            # set all the element along the path to 0, avoiding repeated lookup
            while nums[slow] * val > 0:
                nxt = get_next_idx(slow)
                nums[slow] = 0
                slow = nxt

        return False

或者最后的循环也可以改一下

class Solution(object):
    def circularArrayLoop(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        def get_nxt_idx(i):
            n = len(nums)
            return (i+nums[i]+n) % n
        
        for i, val in enumerate(nums):
            slow = i
            fast = get_nxt_idx(i)
            
            while nums[fast] * val > 0 and nums[get_nxt_idx(fast)] * val > 0:
                if slow == fast:
                    if slow == get_nxt_idx(slow):
                        break
                    return True
                
                slow = get_nxt_idx(slow)
                fast = get_nxt_idx(get_nxt_idx(fast))
            
            fast = get_nxt_idx(i)
            while nums[fast] * val > 0:
                nxt = get_nxt_idx(get_nxt_idx(fast))
                nums[fast] = 0
                fast = nxt
        return False