Lexi's Leetcode solutions

Posts Tagged ‘dfs

给一个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(); 
}
Advertisements
Tags: ,

比如 {1, 1, 1, 2, 3},x = 3, 结果就是{111}{12}{3}。这个题挺难想的,和上一题又不一样。正常stack,把1push进去,然后直接在2上recurse x=2的(因为1只能用一次)。这样一直做到x==0。这样就会有重复:当stack pop空了之后,回到第二个1上,又开始push,那stack的第0个又是1了,刚才已经做过stack第0个是1的一遍了(左边的一遍肯定包括了最多种的情况),所以现在再把1放里面就会重复。所以要在做“要不要在当前layer试一下下一个数?”的决定的时候,要看“下一个数和当前数是否相等?因为当前数已经做过了,同一层layer说明是同一个position,再放当前数就会重复)。

总结:

  • combination/set: 用stack,因为长度不固定。
  • permutation: 用int[],keep一个pos pointer。
  • 主函数里面不要循环,就一个以初始值call副函数的语句就行。
  • 副函数是循环里面call自己。
public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  Stack<Integer> path = new Stack<Integer>();
  combinationSum(num, target, 0, path, result);
  return result;
}
private void combinationSum(int[] arr, int target, int start, Stack<Integer> path, ArrayList<ArrayList<Integer>> result) {
  if (target == 0) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.addAll(path);
    result.add(list);
    return;
  }
  for (int i = start; i < arr.length; i++) {
    if (arr[i] > target)
      return;
    path.push(arr[i]);
    combinationSum(arr, target - arr[i], i + 1, path, result);
    path.pop();
    //do we want to place arr[i + 1] at the same position arr[i] has been?
    while (i + 1 < arr.length && arr[i] == arr[i + 1]) {
      i++;
    }
  }
}

比如{2, 3, 6, 7},x = 7,组合就是{2, 2, 3}和{7}。不能有重复,且必须是sorted order。

这个是标准DFS,一定要记住。先sort array,然后试图用2,用了2之后x相当于只剩5,然后下一层递归再用2,用到没法再用为止(当前值比x还大)。失败后stack pop出来,再试着在前面用了2, 2, 2的条件下用3, 挂,pop出2,在22的条件下用3,正好,输出。然后再pop一个2,再用3, {2, 3},再用下一个3。。在脑子里想一下和树的dfs的图是一样的。

public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
  Arrays.sort(candidates);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  Stack<Integer> path = new Stack<Integer>();
  combinationSum(candidates, target, 0, path, result);
  return result;
}
private void combinationSum(int[] arr, int target, int start, Stack<Integer> path, ArrayList<ArrayList<Integer>> result) {
  if (target == 0) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.addAll(path);
    result.add(list);
    return;
  }
  for (int i = start; i < arr.length; i++) {
    if (arr[i] > target) //这时候break可以保证不要再查后面那些越来越大的
      return;
    path.push(arr[i]);
    combinationSum(arr, target - arr[i], i, path, result); //start永远不会越界,所以一开始不用check
    path.pop();
   }
 }

example: aabc matches c*a*b.

思路:

  1. 两个指针i, j,i指regular expression,j指真的string。
  2. 观察p[i+1],
    • 如果它不是*,说明没法skip p[i],则p[i]和s[j]必须match(相等或者p[i]是’.’ which matches everything)。如果不满足,直接返回false,没法matche了。
    • 如果它是*,说明当前位置可以是0个p[i], 1个p[i], 2个p[i]..
      1. 先试试“用0个p[i]“,即把p[i]和他后面的* skip掉。若recurse (i + 2, j)成功了,直接返回true,不成功,接着做第二步。
      2. 从“用1个p[i]“开始while循环,若p[i]和s[j] match, recurse on (i + 2, j + 1)(把*用掉了所以i+2),如果返回true就直接成了,否则就while继续循环“用2个p[i]“,即recurse on (i + 2, j + 2), recurse on (i + 2, j + 3)…循环的终止条件是p[i]和s[j]不match了,直接返回false。
public boolean isMatch(String s, String p) {
  return tryMatch(p, s, 0, 0);
}
private boolean tryMatch(String p, String s, int i, int j) {
  if (i == p.length())
    return j == s.length();
  if (i == p.length() - 1 || p.charAt(i + 1) != '*') { //下一个字母不是*,当前字母必须match
    if (matchChar(p, s, i, j))
      return tryMatch(p, s, i + 1, j + 1);
    else
      return false;
  } else { // p[i + 1] is *
    boolean skip = tryMatch(p, s, i + 2, j); //把当前字母去掉能行,就直接返回
    if (skip)
      return true;
    while (matchChar(p, s, i, j)) {//*当一个p[i]开始,当两个,当三个。。
      if (tryMatch(p, s, i + 2, j + 1))
        return true;
      j++;
    }
    return false;
  }
}
private boolean matchChar(String p, String s, int i, int j) {
  if (i >= p.length() || j >= s.length())
    return false;
  return p.charAt(i) == s.charAt(j) || p.charAt(i) == '.';
}
Tags: , ,

没啥可说的,对于每个cell,如过和word的开头字母一致,就生成一个新的全是false的visited[][], 进去原matrix开始前后左右的找。直到word的每个字母都找到为止。

要点:之前做的是直接

  // left, right, up, down
  return find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
  || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);

这样就挂了!因为往左走的一路已经Update visited[][]了,然后没人去undo它,往右走的一支就直接拿来用了,不就乱套了么!所以在mark true的时候,函数结尾给undo一下,就可以保证一对儿出现,路径在反上来的被清理。

public boolean exist(char[][] board, String word) {
  for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
      if (board[i][j] == word.charAt(0)) {
        boolean found = find(board, i, j, word, 0, new boolean[board.length][board[0].length]);
        if (found)
          return true;
      }
    }
  }
  return false;
}
private boolean find(char[][] board, int i, int j, String word, int index, boolean[][] visited) {
  if (i < 0 || j < 0 || i >= board.length || j >= board[0].length)
    return false;
  if (board[i][j] != word.charAt(index) || visited[i][j])
    return false;
  visited[i][j] = true;
  if (index == word.length() - 1)
    return true;
  // left, right, up, down
  boolean found = find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
                || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);
  visited[i][j] = false;//这样就能保证每次true的能给false回来
  return found;
}

和电话号码一样,基本的DFS。mark一下,下次再准备面试的时候可能就忘了这种题型了。

public ArrayList<String> restoreIpAddresses(String s) {
  ArrayList<String> result = new ArrayList<String>();
  String[] curr = new String[4];
  restore(s, 0, curr, result);
  return result;
}
private void restore(String s, int level, String[] curr, ArrayList<String> result) {
  if (level == 4) {
    if (s.isEmpty()) {
      result.add(convertToIpString(curr));
    }
    return;
  } else if (s.isEmpty())
  return;
 
  for (int i = 1; i <= 3 && i <= s.length(); i++) {
    String left = s.substring(0, i);
    String right = s.substring(i);
    if (validIp(left)) {
      curr[level] = left;
      restore(right, level+ 1, curr, result);
    }
  }
}
private boolean validIp(String s) {
  if (s.length() > 1 && s.charAt(0) == '0')
    return false;
  return Integer.valueOf(s) < 256;
}
private String convertToIpString(String[] curr) {
  StringBuilder sb = new StringBuilder();
  for (String s : curr) {
    sb.append(s);
    sb.append(".");
  }
  sb.deleteCharAt(sb.length() - 1);
  return sb.toString();
}
Tags: ,

平时的permutation有一个boolean used[],如果arr[i]在之前的layer里用过了,就不能再用了。比如{1, 2, 1},到pos2的时候,看即使arr[2]是“1”,但是这个1不是第一个用过的1,所以还可以放在当前pos当中。但是在pos0的时候,如果想用第二个1,就不行了(当前pos已经有人用过数字1了,即使用的是arr[0]不是当前想用的arr[2],但是是同一个数字就不行),所以skip掉。因此,算法是“在每个position存一个hashset记录在这个position放过那些数字,若是以前放过了,这次就别放了。“

public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (num.length == 0)
  return result;
  permute(num, 0, new int[num.length], new boolean[num.length], result);
  return result;
}
private void permute(int[] num, int pos, int[] path, boolean[] used, ArrayList<ArrayList<Integer>> result) {
  if (pos == path.length) {
    result.add(convertToIntegerList(path));
    return;
  }
  Set<Integer> layerTried = new HashSet<Integer>();
  for (int i = 0; i < num.length; i++) {
    if (!layerTried.contains(num[i]) && used[i] == false) {
      path[pos] = num[i];
      used[i] = true;
      permute(num, pos + 1, path, used, result);
      layerTried.add(num[i]);
      used[i] = false;
    }
  }
}