Lexi's Leetcode solutions

Posts Tagged ‘dfs’

[classic] DAG Topological sort | 有向无环图拓扑排序

Posted by: on: October 13, 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: ,

[leetcode] Combination Sum 2 | 给个数组，找里面能求和=x的所有组合（数字只能用一次，结果不能重复）

Posted by: on: October 9, 2013

比如 {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++;
    }
  }
}
Tags: , , , ,

[leetcode] Combination Sum | 给个数组，找里面能求和=x的所有组合（数字可以重复使用）

Posted by: on: October 9, 2013

比如{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();
   }
 }
Tags: , ,

[leetcode] Regular Expression Matching | 看string a是否match regex b

Posted by: on: August 25, 2013

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: , ,

[leetcode] Word Search | 二维矩阵找里面的单词

Posted by: on: August 24, 2013

没啥可说的，对于每个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;
}
Tags: , ,

[leetcode] restore ip address | 把一个string parse成valid ip地址，返回所有valid parse

Posted by: on: August 11, 2013

和电话号码一样，基本的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: ,

[leetcode] Permutations II | 一个带dup的array的所有unique permutation

Posted by: on: August 8, 2013

平时的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;
    }
  }
}
Tags: , , ,

[leetcode] Palindrome Partitioning | 分解string使每个substring都中心对称，返回所有分解可能。

Posted by: on: August 3, 2013

这应该是DFS，和CC上那道题也很像，但是实在是做不出来。。而且用binary分解那种方法想出来了，但是时间复杂度也弄不明白。崩溃了。这样下去，周一的MS会挂把。。。

———————–两个月之后———————-

一次Bugfree。看来人真是会成长的。。和word break一样做，abaa先分成a, baa，然后再分成ab, aa，左边是palindrome才recurse on右边：

public ArrayList<ArrayList<String>> partition(String s) {
  Map<String, ArrayList<ArrayList<String>>> cache = new HashMap<String, ArrayList<ArrayList<String>>>();
  return partition(s, cache);
}
private ArrayList<ArrayList<String>> partition(String s, Map<String, ArrayList<ArrayList<String>>> cache) {
  if (cache.containsKey(s))
    return cache.get(s);
  ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
  if (s.isEmpty()) {
    result.add(new ArrayList<String>());
  }
  for (int i = 0; i < s.length(); i++) {
    String left = s.substring(0, i + 1);
    if (isPalindrom(left)) {
      String right = s.substring(i + 1);// right maybe empty
      ArrayList<ArrayList<String>> rightPartitions = partition(right);
      for (ArrayList<String> rightPartition : rightPartitions) {
        rightPartition.add(0, left);
        result.add(rightPartition);
      }
    }
  }
  cache.put(s, result);
  return cache.get(s);
}
private boolean isPalindrom(String left) {
  for (int i = 0; i < left.length() / 2; i++) {
    if (left.charAt(i) != left.charAt(left.length() - 1 - i))
      return false;
  }
  return true;
}
Tags: , ,

[leetcode] N-Queens | 8皇后问题

Posted by: on: August 2, 2013

这题做了好几遍了，（尽管每次都有进步）但是因为一直用的二维数组char[][] board，到leetcode上跑才发现超时。问题出现在算“对角能不能放”的时候，因为char[][]要遍历才能知道之前都在哪些位置放了皇后，所以多花了遍历的时间。书上的算法是用int[] queenColAtRow，这样queenColAtRow[i]就表示“在第i行，把queen放在了result位置上“。这样可以直接O(1)的知道每行queen都放在哪列了，少遍历一维，大的就过了。

public int totalNQueens(int n) {
  ArrayList<String[]> solveNQueens = solveNQueens(n);
  return solveNQueens.size();
}
public ArrayList<String[]> solveNQueens(int n) {
  //生成全是.的board，因为要返回board本身，所以现在先填好了。
  char[][] board = new char[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      board[i][j] = '.';
    }
  }
  ArrayList<String[]> result = new ArrayList<String[]>();
  placeQueen(board, 0, n, result);
  return result;
}
private void placeQueen(char[][] board, int row, int n, ArrayList<String[]> result) {
  if (row == n) {
    result.add(copyBoard(board));
    return;
  }
  for (int col = 0; col < n; col++) {
    if (canPlace(board, row, col)) {
      board[row][col] = 'Q';
      placeQueen(board, row + 1, n, result);
      board[row][col] = '.';
    }
  }
}
private boolean canPlace(char[][] board, int row, int col) {
  // row is definitely fine
  for (int i = 0; i <= row; i++) {
    if (board[i][col] == 'Q')
      return false;
  }
  for (int i = 0; i < row; i++) {
    for (int j = 0; j < board.length; j++) {
      if (board[i][j] == 'Q' && Math.abs(i - row) == Math.abs(j - col))
      return false;
    }
  }
  return true;
}
Tags: , ,

Blog Stats

  • 222,875 hits

Search

March 2023
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728293031  

Create a free website or blog at WordPress.com.