[Leetcode][第81题][JAVA][N皇后问题][回溯算法]

【问题描述】[困难]

【解答思路】

1. 主副对角线列 标记

复杂度

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List; public class Solution { private int n; // 记录某一列是否放置了皇后 private boolean[] col; // 记录主对角线上的单元格是否放置了皇后 private boolean[] main; // 记录了副对角线上的单元格是否放置了皇后 private boolean[] sub; private List<List<String>> res; public List<List<String>> solveNQueens(int n) { res = new ArrayList<>(); if (n == 0) { return res; } // 设置成员变量，减少参数传递，具体作为方法参数还是作为成员变量，请参考团队开发规范 this.n = n; this.col = new boolean[n]; this.main = new boolean[2 * n - 1]; this.sub = new boolean[2 * n - 1]; Deque<Integer> path = new ArrayDeque<>(); dfs(0, path); return res; } private void dfs(int row, Deque<Integer> path) { if (row == n) { // 深度优先遍历到下标为 n，表示 [0.. n - 1] 已经填完，得到了一个结果 List<String> board = convert2board(path); res.add(board); return; } // 针对下标为 row 的每一列，尝试是否可以放置 for (int j = 0; j < n; j++) { if (!col[j] && !main[row + j] && !sub[row - j + n - 1]) { path.addLast(j); col[j] = true; main[row + j] = true; sub[row - j + n - 1] = true; dfs(row + 1, path); // 递归完成以后，回到之前的结点，需要将递归之前所做的操作恢复 sub[row - j + n - 1] = false; main[row + j] = false; col[j] = false; path.removeLast(); } } } private List<String> convert2board(Deque<Integer> path) { List<String> board = new ArrayList<>(); for (Integer num : path) { StringBuilder row = new StringBuilder(); row.append(".".repeat(Math.max(0, n))); row.replace(num, num + 1, "Q"); board.add(row.toString()); } return board; } }

其实已经摆放皇后的列下标、占据了哪一条主对角线、哪一条副对角线也可以使用哈希表来记录。

实际上哈希表底层也是数组，使用哈希表可以不用处理已经占据位置的皇后的主对角线、副对角线的下标偏移问题。

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.HashSet; import java.util.List; import java.util.Set; public class Solution { private Set<Integer> col; private Set<Integer> main; private Set<Integer> sub; private int n; private List<List<String>> res; public List<List<String>> solveNQueens(int n) { this.n = n; res = new ArrayList<>(); if (n == 0) { return res; } col = new HashSet<>(); main = new HashSet<>(); sub = new HashSet<>(); Deque<Integer> path = new ArrayDeque<>(); dfs(0, path); return res; } private void dfs(int row, Deque<Integer> path) { if (row == n) { List<String> board = convert2board(path); res.add(board); return; } // 针对每一列，尝试是否可以放置 for (int i = 0; i < n; i++) { if (!col.contains(i) && !main.contains(row + i) && !sub.contains(row - i)) { path.addLast(i); col.add(i); main.add(row + i); sub.add(row - i); dfs(row + 1, path); sub.remove(row - i); main.remove(row + i); col.remove(i); path.removeLast(); } } } private List<String> convert2board(Deque<Integer> path) { List<String> board = new ArrayList<>(); for (Integer num : path) { StringBuilder row = new StringBuilder(); row.append(".".repeat(Math.max(0, n))); row.replace(num, num + 1, "Q"); board.add(row.toString()); } return board; } }

2. board[n][n]标记 直接遍历

时间复杂度：O(N!) 空间复杂度：O(N²)

class Solution { List<List<String>> res=new ArrayList<>(); public List<List<String>> solveNQueens(int n) { //棋盘,默认为0表示空，1表示皇后 int[][] borad = new int[n][n]; //row当前填写得的行号 dfs(n,0,borad); return res; } public void dfs(int n,int row,int[][] board) { if (row == n) { // n个棋子都放置好了，打印结果 res.add(track(board,n)); // n行棋子都放好了，已经没法再往下递归了，所以就return } return; } for (int column = 0; column < n; ++column) { // 每一行都有8中放法 if (isOk(row, column,n,board)) { // 有些放法不满足要求 board[row][column] =1; dfs( n,row+1,board); // 考察下一行 board[row][column] =0; } } } private boolean isOk(int row ,int column ,int n,int[][] board){ int leftup = column -1,rightup = column+1; for(int i=row-1;i>=0;i--){// 逐行往上考察每一行 if(board[i][column]==1){// 第i行的column列有棋子吗？ return false; } if(leftup>=0){// 考察左上对角线：第i行leftup列有棋子吗？ if(1==board[i][leftup]) return false; } if(rightup<n){// 考察右上对角线：第i行rightup列有棋子吗？ if(1==board[i][rightup]) return false; } leftup--; rightup++; } return true; } private List<String> track(int[][] board, int n) {// 打印出一个二维矩阵 List<String> list=new ArrayList<>(); for (int row = 0; row < n; ++row) { StringBuffer str = new StringBuffer(); for (int column = 0; column < n; ++column) { if (board[row][column] == 1){ str.append("Q"); }else{ str.append("."); } } list.add(str.toString()); } return list; } }

【总结】

1.回溯模板

List<> res = new LinkedList<>(); Deque<Integer> path = new ArrayDeque<>(); void dfs(路径, 选择列表){ if 满足结束条件{ res.add(路径); return; } for 选择 in 选择列表{ // 做选择; // 标记一下已经选了，有些题目不需要标记 nums[i] = true; // 把选择的放进路径 path.push(i) dfs(路径, 选择列表); // 恢复现场; path.pop(); nums[i] = false; } }

2.回溯思想

【数据结构与算法】【算法思想】回溯算法

转载链接：https://leetcode-cn.com/problems/n-queens/solution/gen-ju-di-46-ti-quan-pai-lie-de-hui-su-suan-fa-si-/ 转载链接：https://leetcode-cn.com/problems/n-queens/solution/java-hui-su-xiang-xi-zhu-jie-bu-tong-fang-fa-pan-d/