Lexi's Leetcode solutions

Posts Tagged ‘dfs

这应该是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;
}
Advertisements

这题做了好几遍了,(尽管每次都有进步)但是因为一直用的二维数组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: , ,