Lexi's Leetcode solutions

Archive for October 13th, 2013

给一个Set<Node>,每个节点里面有个List<Node> children,求它的sorted list representation http://en.wikipedia.org/wiki/Topological_sorting。Google phone就挂这了。

比如下图,假设箭头全是向下的,则return list就是A->C->E->F->B->D,就是其中一个valid solution。所有dependent关系都满足,然后那些无dependent关系的(比如B和C, D和E就任意顺序就行)。

  A
/   \
B   C
\   /\
  D   E -> F

算法:

  1. 一个map<Node, Boolean>记录走过的节点,false表示visiting (gray), true表示visited (black),无环图说明不会遇见灰色节点(一个节点还没visit完呢就又遇见它了),否则就是有环了(circular dependent)。
  2. 每次从白色节点(set里)里挑一个,从它开始DFS。
  3. DFS就是把这个节点涂灰,然后顺次DFS它的孩子,每个先visited的孩子的list都插在dummy head的最前面,所以老二的孙子其实排在老大前面(比如C的老大是D,老二是E->F,结果就是CEFD(最后把父亲放最前面)。这样保证每个孩子序列都是原来顺序,各个孩子树之间反正没关系,就顺次排开就行了。
  4. 每次一个节点被涂黑,就从set里remove。直到set空了为止。
Node topoSort(Set<Node> set) {
    Map<Node, Boolean> map = new HashMap<Node, Boolean>;
    Node dummy = new Node();
    while (!set.isEmpty()) {
        Node node = set.iterator().next();
        dfs(node, dummy, set, map);
    }
    return dummy.next();
} 
void dfs(Node node, Node dummy, Set<Node> unBlacked, Map<Node, Boolean> map) {
    if (!map.containsKey(node)) {
        map.put(node, false);
        for (Node child : node.children) {     
            dfs(child, dummy, set, map);
        }
        Node break = dummy.next;
        dummy.next = node;
        node.next = break;
        map.put(node, true);//mark black
        set.remove(node);
     } else if (map.get(node) == false) {
        //gray, there's a loop
        throw new LoopExistException(); 
}
Tags: ,

这个题尽管是CC150上的,理论上很简单,但是想明白(而且用好的方法)很不容易。

1. 数组没有重复

  1. 既然是断开一次的数组,说明A[p] > A[q]。我们从中间一刀划分,想出找sorted那一半,看是否包含x,包含的话就在sorted那一半找;不包含就在broken那一半找。
  2. 这个是根据A[mid]和A[p]来初步划分,平时binary search都是根据A[mid]和x来直接划分。所以一开始做复杂了。这个题按上面说的定义做最好,简单易懂。
  3. 当A[mid] == A[p]的时候,说明mid==p,就左边这一个点,既然已经判断过A[mid] != x了,所以直接找右边就好了。
public int search(int[] A, int target) {
  return find(A, 0, A.length - 1, target);
}
private int find(int[] arr, int p, int q, int x) {
  if (p > q)
    return -1;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
    return mid;
  if (arr[p] < arr[mid]) { // left is ordered, right is broken
    if (arr[p] <= x && x <= arr[mid]) // x is in the left ordered part
      return find(arr, p, mid - 1, x);
    else // x doesn't belong to left ordered part
      return find(arr, mid + 1, q, x);
  } else if (arr[p] > arr[mid]) {// left is broken, so right is ordered
    if (arr[mid] <= x && x <= arr[q])
      return find(arr, mid + 1, q, x);
    else
      return find(arr, p, mid - 1, x);
  } else { // a[p] == a[mid], directly search right
      return find(arr, mid + 1, q, x);
  }
}

2. 数组有重复数字

  1. 还是从中间一刀划分,想找出sorted那一半,看是否包含x。
  2. 但是当A[p] == A[mid]的时候,不能说明左边就是长度为1的一半了。左边可以是全是repeat,也可以是包含x。
  3. 这时要和A[q]比较,如果A[mid] == A[q],总不能整个数组平了吧。这时候x可以是左边也可以是在右边,必须两边找。
  4. 如果A[mid] != A[q],说明右半部分有起伏,左边的平的这段就不能有起伏了(自己画一下吧)。所以还是找右边。
public boolean search(int[] A, int target) {
  return find(A, 0, A.length - 1, target) >= 0;
}
private int find(int[] arr, int p, int q, int x) {
  if (p > q)
    return -1;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
    return mid;
 
  if (arr[p] < arr[mid]) { //left is ordered, right is broken
    if (arr[p] <= x && x <= arr[mid]) // x is in the left ordered part
      return find(arr, p, mid - 1, x);
    else //x doesn't belong to left orderd part
      return find(arr, mid + 1, q, x);
  } else if (arr[p] > arr[mid]) {//left is broken, so right is ordered
    if (arr[mid] <= x && x <= arr[q])
      return find(arr, mid + 1, q, x);
    else
      return find(arr, p, mid - 1, x);
  } else { // arr[p] = arr[mid], don't know which side is broken
    if (arr[mid] == arr[q]) {
      int leftResult = find(arr, p, mid - 1, x);
      return leftResult == -1 ? find(arr, mid + 1, q, x) : leftResult;
    } else { //mid is not equals right, so left is all repeats, search right
      return find(arr, mid + 1, q, x);
    }
  }
}

这个好像两年前在纽约就做过,到今天才好好分析了一遍。Leetcode上面的这篇分析特别特别好,看过一遍顺便还练习算时间复杂度了。总之两个比较好的解法:

1. O(n)的linear解法:

因为二维矩阵是行列都sort好的,所以最上面一行和最右边一列正好形成了一个sort好的递增数列。取右上角这个A[i][j],它左边的全<x, 它下边的全>x,所以每次可以删掉一行/列。这样每次往下/往左走一步,最后要是走到左下角了还没找到,那走的最多步数是m + n步。所以时间是O(m + n)。

public boolean searchMatrixLinear(int[][] matrix, int target) {
  int i = 0, j = matrix[0].length - 1;
  while (i < matrix.length && j >= 0) {
    if (matrix[i][j] == target)
      return true;
    else if (matrix[i][j] > target) // eliminate col, go left
      j--;
    else
      i++; // eliminate row, go down
  }
  return false;
}

2. O(logm * logn)的更快的解法:

每次取中间一列,然后在这一列里面binary search,要是没找到,最后会找到(j1, j2)这样的两个位置,A[i][j1] < x && A[i][j2]。说明(i, j1)左上的全<x,(i, j 2)右下的全>x,说明x肯定不在这两块里面,就可以eliminate掉了。在剩下的两块里面各自找x,然后返回||。

这个时间复杂度为什么是O(logm * logn)?每次删掉行数的一半,是logm,在每个check的row里面做一次binary search是logn。

public boolean searchMatrixFastest(int[][] matrix, int target) {
  return searchBinary(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, target);
}
private boolean searchBinary(int[][] matrix, int i1, int i2, int j1, int j2, int x) {
  if (i1 > i2 || j1 > j2)
    return false;
  int midRow = (i1 + i2) / 2; 
  int midCol = searchInRow(matrix, midRow, j1, j2, x); 
  if (midCol == -10) //用-10不用-1因为可能没找到但是q=-1
    return true;
  return searchBinary(matrix, i1, midRow - 1, midCol + 1, j2, x) || searchBinary(matrix, midRow + 1, i2, j1, midCol, x);
}
private int searchInRow(int[][] matrix, int i, int p, int q, int x) {
  while (p <= q) {
    int mid = (p + q) / 2;
    if (matrix[i][mid] == x)
      return -10;
    else if (matrix[i][mid] > x) // go up
      q = mid - 1;
    else
      p = mid + 1;
  }
  return q;
}