【刷穿 LeetCode】检测「环形数组是否存在循环」的三种方式：「朴素模拟」&「遍历标记（含优化）」

输入：nums = [2,-1,1,2,2]
输出：true
解释：存在循环，按下标 0 -> 2 -> 3 -> 0 。循环长度为 3 。
复制代码

输入：nums = [-1,2]
输出：false
解释：按下标 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。
复制代码

输入：nums = [-2,1,-1,-2,-2]
输出：false
解释：按下标 1 -> 2 -> 1 -> ... 的运动无法构成循环，因为 nums[1] 是正数，而 nums[2] 是负数。
所有 nums[seq[j]] 应当不是全正就是全负。
复制代码

class Solution {
    int n;
    int[] nums;
    public boolean circularArrayLoop(int[] _nums) {
        nums = _nums;
        n = nums.length;
        for (int i = 0; i < n; i++) {
            if (check(i)) return true;
        }
        return false;
    }
    boolean check(int start) {
        int cur = start;
        boolean flag = nums[start] > 0;
        int k = 1;
        while (true) {
            if (k > n) return false;
            int next = ((cur + nums[cur]) % n + n ) % n;
            if (flag && nums[next] < 0) return false;
            if (!flag && nums[next] > 0) return false;
            if (next == start) return k > 1;
            cur = next;
            k++;
        }
    }
}
复制代码

class Solution {   
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        // 使用 vis 数组对每个下标进行标记
        // 如果下标为 i 的位置在第 idx 轮被标记，则有 vis[i] = idx
        int[] vis = new int[n];
        for (int start = 0, idx = 1; start < n; start++, idx++) {
            if (vis[start] != 0) continue;
            int cur = start;
            boolean flag = nums[cur] > 0;
            while (true) {
                int next = ((cur + nums[cur]) % n + n) % n;
                if (next == cur) break;
                if (vis[next] != 0) {
                    // 如果 next 点已经被标记过，并且不是在本轮被标记，那么往后的通路必然都被标记，且无环，跳出   
                    if (vis[next] != idx) break;
                    // 如果 next 点已被标记，并且是本来被标记，说明找到了环
                    else return true;
                }
                if (flag && nums[next] < 0) break;
                if (!flag && nums[next] > 0) break;
                vis[next] = idx;
                cur = next;
            }
        }
        return false;
    }
}
复制代码

class Solution {
    int OFFSET = 100010;
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] >= OFFSET) continue;
            int cur = i, tag = OFFSET + i, last = -1;
            boolean flag = nums[cur] > 0;
            while (true) {
                int next = ((cur + nums[cur]) % n + n ) % n;
                last = nums[cur];
                nums[cur] = tag;
                cur = next;
                if (cur == i) break;
                if (nums[cur] >= OFFSET) break;
                if (flag && nums[cur] < 0) break;
                if (!flag && nums[cur] > 0) break;
            }
            if (last % n != 0 && nums[cur] == tag) return true;
        }
        return false;
    }
}
复制代码