457. Circular Array Loop

457. Circular Array Loop

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?

------------------
以下⽅方法最坏结果是 O(n^2)。可以加⼀一个额外的visited数组，可降低为O(n) 要改进的话，关键在于判断何时在处于同⼀一个loop内，何时判断当前的点为⾛走过的 点。

Solution #1

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && dfs(nums, i)) return true;
        }
        
        return false;
    }
    
    private boolean dfs(int[] nums, int i) {
        if (nums[i] == 0) return true;
        int tmp = nums[i];
        int nextStep = (tmp + i + nums.length) % nums.length;
        if (nums[nextStep] * tmp < 0 || i == nextStep) return false;
        nums[i] = 0;
        
        if (!dfs(nums, nextStep)) {
            nums[i] = tmp;   
            return false;
        }
        
        return true;
    }
}

Solution #2
此方法是对上⾯的改进， 增加一个变量量记录深度，如果超过nums的长度，则发现了 一个loop。此方法可改写为iter1tive从而满⾜足O(1) sp1ce的要求

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && dfs(nums, i, 0)) return true;
        }
        
        return false;
    }
    
    private boolean dfs(int[] nums, int i, int depth) {
        if (depth > nums.length) return true;
        int nextStep = (nums[i] + i + nums.length) % nums.length;
        if (nums[nextStep] == 0 || nums[nextStep] * nums[i] < 0 || i == nextStep) return false;
        
        if(dfs(nums, nextStep, depth + 1)) return true;
        nums[i] = 0;
        return false;
    }
}

Solution #3, 为以上方法的iterative版本，O(n) space, O(1) time

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && itr(nums, i)) return true;
        }
        
        return false;
    }
    
    private boolean itr(int[] nums, int ori) {
        int i = ori;
        int depth = 0;
        while (true) {
            int nextStep = (nums[i] + i + nums.length) % nums.length;
            if (nums[nextStep] == 0 || nums[nextStep] * nums[i] < 0 || i == nextStep) break;
            i = nextStep;
            depth++;
            if (depth > nums.length) return true;
        }
        
        nums[i] = 0;
        while (i != ori) {
            int nextStep = (nums[ori] + ori + nums.length) % nums.length;
            nums[ori] = 0;
            ori = nextStep;
        }
        return false;
    }
}