Lexi's Leetcode solutions

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

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

1 Response to "[leetcode] N-Queens | 8皇后问题"

copyBoard是自己写的函数么?没见implementation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: