一定要早日上岸鸭 · August 7, 2021 0

457. 环形数组是否存在循环

457. 环形数组是否存在循环

思路:与141. 环形链表题类似,

因为可以将环形数组理解为图中的 nn 个点,nums[i]nums[i] 表示 ii 号点向 (i + nums[i]) mod n 号点连有一条单向边。注意到这张图中的每个点有且仅有一条出边,这样我们从某一个点出发,沿着单向边不断移动,最终必然会进入一个环中。而依据题目要求,我们要检查图中是否存在一个所有单向边方向一致的环。我们可以使用在无向图中找环的一个经典算法:快慢指针 来解决本题

ps: 我用了哈希表存储了下一步,答案中用了next function 来取下一步:

class Solution { public boolean circularArrayLoop(int[] nums) { int N = nums.length; Map<Integer, Integer> hm = new HashMap<Integer, Integer>(); for(int i=0; i<N; i++){ hm.put(i, ((i+nums[i])%N+N)%N); } // System.out.println(hm.toString()); for(int i=0; i<N; i++){ int slow = i; int fast = hm.get(slow); while(nums[slow]*nums[fast]>0 && nums[slow]*nums[hm.get(fast)]>0){ // System.out.println(slow+" "+fast+" "+nums[slow]+" "+nums[fast]); if(slow==fast){ // k>1 if(slow == hm.get(slow)) break; else return true; } slow = hm.get(slow); // System.out.println(hm.get(fast)); fast = hm.get(hm.get(fast)); } // 标记已经遍历过的节点: int add = i; while (nums[add] * nums[hm.get(add)] > 0) { int tmp = add; add = hm.get(add); nums[tmp] = 0; } } return false; } } // class Solution { // public boolean circularArrayLoop(int[] nums) { // int n = nums.length; // for (int i = 0; i < n; i++) { // if (nums[i] == 0) { // continue; // } // int slow = i, fast = next(nums, i); // // 判断非零且方向相同 // while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) { // if (slow == fast) { // if (slow != next(nums, slow)) { // return true; // } else { // break; // } // } // slow = next(nums, slow); // fast = next(nums, next(nums, fast)); // } // int add = i; // while (nums[add] * nums[next(nums, add)] > 0) { // int tmp = add; // add = next(nums, add); // nums[tmp] = 0; // } // } // return false; // } // public int next(int[] nums, int cur) { // int n = nums.length; // return ((cur + nums[cur]) % n + n) % n; // 保证返回值在 [0,n) 中 // } // } // 作者:LeetCode-Solution // 链接:https://leetcode-cn.com/problems/circular-array-loop/solution/huan-xing-shu-zu-shi-fou-cun-zai-xun-hua-0ay2/ // 来源:力扣(LeetCode) // 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。