[leetcode] N-Queens | 8皇后问题
Posted August 2, 2013
on:这题做了好几遍了,(尽管每次都有进步)但是因为一直用的二维数组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; }
April 13, 2014 at 8:18 pm
copyBoard是自己写的函数么?没见implementation