Massive Algorithms: LeetCode 457 - Circular Array Loop

LeetCode 457 - Circular Array Loop

https://leetcode.com/problems/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?

X.
https://blog.csdn.net/u012737193/article/details/79050869
这题还是相当有难度的，难就难在要求O(n)的时间和O(1)的空间，

这一题我使用了快慢指针解决的，首先遍历一遍原数组，对于数组里面的每一个数值，设定一个slow指针，和一个fast指针，slow指针每一次跳一格，fast指针每一次跳两格，当slow指针第一次跳时回到了原点，说明这个起点不可行，将nums[start]设置为0，当fast指针跳到了一个格子，格子的值和fast指针跳之前的格子的值符号相反的时候，说明从start格子到fast指针所在的格子都不可行，需要将从start格子到fast指针格子的全部格子都设置为0，这里使用的是setZero函数

这里还需要注意的是当fast跳两步之后和跳之前的索引相等的话，说明fast指针找到了一个单循环，单循环不能够算作循环，因此这个时候依然需要将start到fast指针之间的全部格子都设为0

当某一次fast和slow指针索引相等的时候，说明这个时候找到了一个非单循环，这个循环是合理的，因此说明这个数组里面存在循环，返回true

以后在做题的时候记住使用快慢指针判断路径里面是否存在循环的方法，使用一个快指针，一个慢指针，快指针没次移动两个，慢指针每次移动一格，当快指针和慢指针移动到索引相等的时候，说明找到了一个循环。这里需要说明一下，只要路径中存在循环，在不断的移动的过程中快指针最终一定会和慢指针相等，也就是说只要存在循环则一定可以找到

http://www.cnblogs.com/grandyang/p/7658128.html

说实话，这道题描述的并不是很清楚，比如题目中有句话说循环必须是forward或是backward的，如果不给例子说明，不太容易能get到point。所谓的循环必须是一个方向的就是说不能跳到一个数，再反方向跳回来，这不算一个loop。比如[1, -1]就不是一个loop，而[1, 1]是一个正确的loop。看到论坛中一半的帖子都是各种需要clarify和不理解test case就感觉很好笑～博主也成功踩坑了。弄清楚了题意后来考虑如何做，由于从一个位置只能跳到一个别的位置，而不是像图那样一个点可以到多个位置，所以这里我们就可以根据坐标建立一对一的映射，一旦某个达到的坐标已经有映射了，说明环存在，当然我们还需要进行一系列条件判断。首先我们需要一个visited数组，来记录访问过的数字，然后我们遍历原数组，如果当前数字已经访问过了，直接跳过，否则就以当前位置坐标为起始点开始查找，进行while循环，计算下一个位置，计算方法是当前位置坐标加上对应的数字，由于是循环数组，所以结果可能会超出数组的长度，所以我们要对数组长度取余。当然上面的数字也可能是负数，加完以后可能也是负数，所以在取余之前还得再补上一个n，使其变为正数。此时我们判断，如果next和cur相等，说明此时是一个数字的循环，不符合题意，再有就是检查二者的方向，数字是正数表示forward，若是负数表示backward，在一个loop中必须同正或同负，我们只要让二者相乘，如果结果是负数的话，说明方向不同，直接break掉。此时如果next已经有映射了，说明我们找到了合法的loop，返回true，否则建立一个这样的映射，将next位置在visited数组中标记true，继续循环

    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        vector<bool> visited(n, false);
        for (int i = 0; i < n; ++i) {
            if (visited[i]) continue;
            visited[i] = true;
            unordered_map<int, int> m;
            int cur = i;
            while (true) {
                int next = (cur + nums[cur] + n) % n;
                if (next == cur || nums[next] * nums[cur] < 0) break;
                if (m.count(next)) return true;
                m[cur] = next;
                cur = next;
                visited[next] = true;
            }
        }
        return false;
    }

我们还可以简化上面的代码，可以不用visited数组，直接在nums中标记，由于题目中说了nums中不会有0，所以可以把访问过的位置标记为0。然后计算next位置，通过cur加上i，再加上n之后，对n取余。如果next和i相等，直接跳过，因为这表示循环只有一个数字，不合题意。然后开始循环，当cur和nums[next]的乘积为正时，说明此时是一个方向的，我们将cur赋值为nums[next]，将nums[next]赋值为0，表示已经访问过，然后再计算新的next位置。直到循环被打破，若此时next和i相等，说明有大于1个数字的环存在，返回true。最终for循环退出后，返回false

    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) continue;
            int cur = nums[i];
            nums[i] = 0;
            int next = (cur + i + n) % n;
            if (next == i) continue;
            while (cur * nums[next] > 0) {
                cur = nums[next];
                nums[next] = 0;
                next = (next + cur + n) % n;
            }
            if (next == i) return true;
        }
        return false;
    }

https://leetcode.com/problems/circular-array-loop/discuss/94148/Java-SlowFast-Pointer-Solution
To those wondering why this is linear O(n) time complexity and not O(n^2): A nested loop structure does not necessarily imply O(n^2) time complexity. We can apply amortized analysis: the algorithm visits each index a maximum of 4 times (visit fast, visit fast, mark zero, skip zero), and because 4 is a constant factor we have O(4n) -> O(n) time complexity. Hope that helps.
https://discuss.leetcode.com/topic/66862/two-pass-o-n-solution-by-marking-failed-loop-by-zero

The basic idea is to detect a loop by maintaining a one-step and a two-step pointers, just like an old problem from leetcode. And each time a possible attempt failed we mark every index on the path by zero, since zero is guaranteed to fail. Since the problem asks only forward of backward solution we simply run it for positive indices and negative indices twice.

By the way, the problem states that the array has only pos and neg numbers, which is apparently a little inaccurate. The presence of zero though doesn't seem to cause much problem.

https://discuss.leetcode.com/topic/66894/java-slow-fast-pointer-solution

Just think it as finding a loop in Linkedlist, except that loops with only 1 element do not count. Use a slow and fast pointer, slow pointer moves 1 step a time while fast pointer moves 2 steps a time. If there is a loop (fast == slow), we return true, else if we meet element with different directions, then the search fail, we set all elements along the way to 0. Because 0 is fail for sure so when later search meet 0 we know the search will fail.

    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                continue;
            }
            // slow/fast pointer
            int j = i, k = getIndex(i, nums);
            while (nums[k] * nums[i] > 0 && nums[getIndex(k, nums)] * nums[i] > 0) {
                if (j == k) {
                    // check for loop with only one element
                    if (j == getIndex(j, nums)) {
                        break;
                    }
                    return true;
                }
                j = getIndex(j, nums);
                k = getIndex(getIndex(k, nums), nums);
            }
            // loop not found, set all element along the way to 0
            j = i;
            int val = nums[i];
            while (nums[j] * val > 0) {
                int next = getIndex(j, nums);
                nums[j] = 0;
                j = next;
            }
        }
        return false;
    }
    
    public int getIndex(int i, int[] nums) {
        int n = nums.length;
        return i + nums[i] >= 0? (i + nums[i]) % n: n + ((i + nums[i]) % n);
    }

getIndex() could also be:

public int getIndex(int i, int[] nums) {
        int n = nums.length;
        return (i + nums[i]) % n + (i + nums[i] < 0)*n;
    }

https://discuss.leetcode.com/topic/66962/java-solution-similar-to-finding-linkedlist-cycle

Start from any index, move to the next index by function f(i)=((i+nums[i])%len+len)%len where len is the length of array nums. and follow the chain. We are guaranteed there is a cycle in this chaining process. check if all the numbers in the cycle are backward or forward. Remember to exclude the one element cycle cases.

    public boolean circularArrayLoop(int[] nums) {
        if(nums==null||nums.length==0) return false;
        for(int a:nums){
            if(a==0) return false;
        }
        int len=nums.length;
        for(int i=0;i<len;i++){
            if(checkCycle(nums,i)) return true;
        }
        return false;
    }
    public boolean checkCycle(int[] nums, int start){
        int len=nums.length;
        int slow=((start+nums[start])%len+len)%len;
        int fast=((slow+nums[slow])%len+len)%len;
        while(slow!=fast){
            slow=((slow+nums[slow])%len+len)%len;
            fast=((fast+nums[fast])%len+len)%len;
            fast=((fast+nums[fast])%len+len)%len;
        }
        if(slow==((slow+nums[slow])%len+len)%len) return false;//one element loop
        boolean forward_backward=nums[slow]>0;//forward or backword
        int ptr=((slow+nums[slow])%len+len)%len;
        while(ptr!=slow){
            if(nums[ptr]>0!=forward_backward) return false;
            ptr=((ptr+nums[ptr])%len+len)%len;
        }
        return true;
    }

http://bookshadow.com/weblog/2016/11/09/leetcode-circular-array-loop/

三次遍历数组：

第一次遍历，将所有指向自己的元素置0

第二次遍历，从0到n（循环一周），将指向非负数的负数置0

第三次遍历，从n到0（循环一周），将指向非正数的正数置0

遍历结束后，如果数组中存在非零元素，则返回True；否则返回False

def circularArrayLoop(self, nums): """ :type nums: List[int] :rtype: bool """ if not nums or not all(nums): return False size = len(nums) next = lambda x : (x + size + nums[x]) % size for x in range(size): if next(x) == x: nums[x] = 0 for x in range(size + 1): x = x % size if nums[x] < 0 and nums[next(x)] >= 0: nums[x] = 0 for x in range(size, -1, -1): x = x % size if nums[x] > 0 and nums[next(x)] <= 0: nums[x] = 0 return any(nums)

X. http://shibaili.blogspot.com/2018/11/457-circular-array-loop.html
此方法是对上⾯的改进，增加一个变量量记录深度，如果超过nums的长度，则发现了一个loop。此方法可改写为iter1tive从而满⾜足O(1) sp1ce的要求

    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;

}

}

LeetCode 457 - Circular Array Loop

Labels

Popular Posts