赞
踩
总体思路:
使用一个数组记录每行放置的皇后的列下标,依次在每一行放置一个皇后。同时增加约束条件,即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上,并更新数组中的当前行的皇后列下标。当找到一个可能的解之后,将数组转换成表示棋盘状态的列表,并将该棋盘状态的列表加入返回列表。
因为我们遍历每一行增加一个元素,所以保证啦每一行只有一个元素,我们需要增加三个数组,columns、diagonals1和 diagonals2,分别表示每一列和两个斜边。
- if (columns.contains(i)) {
- continue;
- }
diagonal1 = row - i;
diagonal2 = row + i;
columns.add(i);
diagonals1.add(diagonal1);
diagonals2.add(diagonal2);
backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
Arrays.fill(row, '.'); row[queens[i]] = 'Q';
时间复杂度:O(N!),其中 N 是皇后数量。
空间复杂度:O(N),其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合,递归调用层数不会超过 N,数组的长度为N,每个集合的元素个数都不会超过 N。
-
- class Solution {
- public List<List<String>> solveNQueens(int n) {
- List<List<String>> solutions = new ArrayList<List<String>>();
- int[] queens = new int[n];
- Arrays.fill(queens, -1);
-
- //使用三个集合 columns、diagonals1和diagonals2分别记录每一列以及两个方向的每条斜线上是否有皇后
-
- Set<Integer> columns = new HashSet<Integer>();
- Set<Integer> diagonals1 = new HashSet<Integer>();
- Set<Integer> diagonals2 = new HashSet<Integer>();
- backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
- return solutions;
- }
-
- public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
- if (row == n) {
- List<String> board = generateBoard(queens, n);
- solutions.add(board);
- } else {
- for (int i = 0; i < n; i++) {
- if (columns.contains(i)) {
- continue;
- }
- int diagonal1 = row - i;
- if (diagonals1.contains(diagonal1)) {
- continue;
- }
- int diagonal2 = row + i;
- if (diagonals2.contains(diagonal2)) {
- continue;
- }
- queens[row] = i;
- columns.add(i);
- diagonals1.add(diagonal1);
- diagonals2.add(diagonal2);
- backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
- queens[row] = -1;
- columns.remove(i);
- diagonals1.remove(diagonal1);
- diagonals2.remove(diagonal2);
- }
- }
- }
-
- public List<String> generateBoard(int[] queens, int n) {
- List<String> board = new ArrayList<String>();
- for (int i = 0; i < n; i++) {
- char[] row = new char[n];
- Arrays.fill(row, '.');
- row[queens[i]] = 'Q';
- board.add(new String(row));
- }
- return board;
- }
- }

如果利用位运算记录皇后的信息,就可以将记录皇后信息的空间复杂度从 O(N) 降到 O(1)。
棋盘的每一列对应每个整数的二进制表示中的一个数位
从右往左,不能放置皇后的位置标1,可以的位置标0
由此可以得到三个整数的计算方法:
遍历可以放置皇后的位置时,可以利用以下两个按位与运算的性质:
复杂度分析
时间复杂度:O(N!),其中 N 是皇后数量。
空间复杂度:O(N),N 是皇后数量。
- class Solution {
- public List<List<String>> solveNQueens(int n) {
- int[] queens = new int[n];
- Arrays.fill(queens, -1);
- List<List<String>> solutions = new ArrayList<List<String>>();
- solve(solutions, queens, n, 0, 0, 0, 0);
- return solutions;
- }
-
- public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
- if (row == n) {
- List<String> board = generateBoard(queens, n);
- solutions.add(board);
- } else {
- int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
- while (availablePositions != 0) {
- int position = availablePositions & (-availablePositions);
- availablePositions = availablePositions & (availablePositions - 1);
- int column = Integer.bitCount(position - 1);
- queens[row] = column;
- solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
- queens[row] = -1;
- }
- }
- }
-
- public List<String> generateBoard(int[] queens, int n) {
- List<String> board = new ArrayList<String>();
- for (int i = 0; i < n; i++) {
- char[] row = new char[n];
- Arrays.fill(row, '.');
- row[queens[i]] = 'Q';
- board.add(new String(row));
- }
- return board;
- }
- }

- class Solution {
- private int count = 0;
- public int totalNQueens(int n) {
- if (n < 1) return 0;
- dfs(0,0,0,0,n);
- return count;
- }
-
- private void dfs(int row, int col, int pie, int na,int n) {
- if (row >= n) {
- count++;
- return;
- }
- int bit = (~(col | pie | na)) // 获取当前空位 标识为1
- & ((1<<n) - 1); // 去掉所有高位
- while (bit > 0){//遍历所有空位
- int p = bit & -bit; //获取最后的空位 1
- /**
- col | p 表示 p 位被占用
- (pie | p ) << 1 ,表示pie往斜左方移一位 被占用
- (na | p) >> 1,表示na往斜右方移一位 被占用
- **/
- dfs(row + 1,col | p,(pie | p ) << 1,(na | p) >> 1,n);
- bit &= (bit - 1); // 打掉最后的1
- }
- }
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。