Lexi's Leetcode solutions

http://www.mitbbs.com/article_t1/JobHunting/32184907_0_1.html

思路（这个没怎么测试，不知道对不对，也想不明白time）。。

从头开始顺着摸，摸到摸过的，说明有loop。

什么时候结束？摸到下一个index out of boundry了，说明当前绳子结束。但是可能数组里中间还剩一大堆元素没动呢，所以要keep一个currRopeHead variable (当前绳子的头)；从这个头的下一个开始往右找（左边不用找了，既然当前绳子在这开头，说明左边的小绳结早就处理过了），找到第一个没visited过的绳头，接着做。

test: {2, -1, 1, 4, 5, 0}这算是loop吗？感觉应该不算，所以一个visited array还不行，得用Map<Index, HashSet<ropeIndex>>才行。顺着当前绳子摸到的节点若在当前绳子上visit过才叫visit过。所以每次新生成绳子的时候，要把ropeIndex++。卧槽这越来越复杂了。

boolean hasCycle(int[] arr) {
  int[] visited = new int[arr.length]; 
  int i = 0; 
  int currRopeHead = i; 
  while (i < arr.length) { 
    if (visited[i])
    return true;
    visited[i] = true;
    int next = arr[i];
    if (next < 0 || next >= arr.length) {
      //rope is broken, will start a new one
      //find the first unvisited rope start
      boolean foundRopeHead;
      for (int j = currRopeHead + 1; j < arr.length; j++) {
        if (!visited[j]) {
          i = j;
          foundRopeHead = true;
          currRopehead = i;
          break;
        }
      }
      if (!foundRopeHead)
        return false;
    } else {
      i = next;
    }
  }
  return false;
}

太复杂了，还是用runner technique吧。两个runner用来看当前绳字有木有loop，外加一个set代表所有没vsit过的“绳头”。

这样的话，其实并不慢，原因是runner fast跑到绳子尽头为止，不多往后跑（如果没loop的话）；如果有loop，那肯定在当前绳结跑两次之前也能追上slow而停止，所以还是O(k + k)的速度（k是当前绳结的长度）。然后这个绳子跑完了，上面所有经过的节点都从set里remove掉了，set就可以接着随便找一个当绳头，接着recursion。有一个怀疑就是然后从set里面random拿的一个节点不是绳头，而是绳子中间某个部分怎么办；后来想想那就相当于把一个长绳子分两半做，要是有loop怎么都分不开，要是没loop那分成的两半也各自没loop，时间还是一样的。

boolean hasLoop(int[] arr) {
  Set<Integer> unvisitedIndexSet = new HashSet<Integer>();
  for (int i = 0; i < arr.length; i++) {
    unvisitedIndexSet.add(i);
  }
  return hasLoop(arr, unvisitedIndexSet);
}
boolean hasLoop(int[] arr, Set<Integer> set) {
  if (set.isEmpty())
    return false;
  int randomHead = getRandomElement(set);
  int fast = randomHead;
  int slow = randomHead;
  set.remove(fast);
  while (fast != -1) {
    fast = arr[fast];
    set.remove(fast);
    if (fast == -1)
    break;
  else {
    fast = arr[fast];
    set.remove(fast);
  }
  slow = arr[slow];
  if (fast == slow)
    return true;
  }
  return hasLoop(arr, set);
}