https://leetcode.com/problems/circular-array-loop/
题目蛮难的，有一些坑。
前后两个指针追赶找环的方法，基本可以归结为一种定式。可以多总结。
package com.company;
class Solution {
// 参考了这里的解法
// https://discuss.leetcode.com/topic/66894/java-slow-fast-pointer-solution
public boolean circularArrayLoop(int[] nums) {
for (int i=; i<nums.length; i++) {
if (nums[i] == ) {
continue;
}
int j = i, k = getIndex(i, nums);
// 检查同方向
while (nums[i] * nums[k] > && nums[i] * nums[getIndex(k, nums)] > ) {
if (j == k) {
// 碰到了
// 检查是否只有一个元素
if (j == getIndex(j, nums)) {
break;
}
return true;
}
// 一前一后两个指针
j = getIndex(j, nums);
k = getIndex(getIndex(k, nums), nums);
}
// 把已经走过的,置为0
j = i;
k = nums[j];
// 但要注意不同方向的不要置为0
while (nums[j]*k > ) {
int tmp = getIndex(j, nums);
nums[j] = ;
j = tmp;
}
}
return false;
}
// 下面这个函数也是参考了上面Discuss里面的解法
private int getIndex(int i, int[] nums) {
int n = nums.length;
int j = (i + nums[i]) >= ? (i + nums[i]) % n : n + ((i + nums[i]) % n);
return j;
}
}
public class Main {
public static void main(String[] args) throws InterruptedException {
System.out.println("Hello!");
Solution solution = new Solution();
// Your Codec object will be instantiated and called as such:
int[] nums = {, -, , -, -};
boolean ret = solution.circularArrayLoop(nums);
System.out.printf("ret:%b\n", ret);
System.out.println();
}
}