Lexi's Leetcode solutions

Posts Tagged ‘runner

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);
}
Advertisements
Tags: ,