hot100 n皇后(51)

算法核心回溯法深度优先搜索 DFS 剪枝时间复杂度O(n² · n!)回溯搜索树中至多有 O(n!) 个叶子节点。当递归到达叶子节点并满足终止条件时生成最终棋盘答案构建 n 个长度为 n 的字符串需要O(n²)的时间。因此严格的上界为 O(n² · n!)实际表现由于剪枝逻辑的存在实际搜索树的叶子节点数远没有这么多。例如当 n 9 时最终只有 352 种有效放置方案远远小于 9! 362,880。更准确的方案数渐进规律可参考OEIS A000170其规模约为O(n! / 2.54ⁿ)空间复杂度O(n)。在不计入返回值输出列表占用空间的情况下递归调用栈的最大深度为 n且辅助状态数组col, diag1, diag2的空间开销均为 O(n) 级别。class Solution { public ListListString solveNQueens(int n) { ListListString ans new ArrayList(); int[] queens new int[n]; // 记录第 r 行的皇后放置在第几列 boolean[] col new boolean[n]; // 列冲突标记 boolean[] diag1 new boolean[2 * n - 1]; // 副对角线冲突标记 (r c) boolean[] diag2 new boolean[2 * n - 1]; // 主对角线冲突标记 (r - c n - 1) dfs(ans, queens, col, diag1, diag2, 0); return ans; } private void dfs(ListListString ans, int[] queens, boolean[] col, boolean[] diag1, boolean[] diag2, int r) { int n col.length; // 终止条件成功放置了 n 个皇后开始生成当前解的棋盘画卷 if (r n) { ListString path new ArrayList(); for (int c : queens) { char[] row new char[n]; Arrays.fill(row, .); row[c] Q; path.add(new String(row)); } ans.add(path); return; } // 尝试在当前行 r 的第 c 列放置皇后 for (int c 0; c n; c) { int rc r - c n - 1; // 主对角线映射索引 // 剪枝条件判断列、两条对角线是否存在冲突 if (!col[c] !diag1[r c] !diag2[rc]) { // 1. 做出选择放置皇后并标记状态 queens[r] c; col[c] diag1[r c] diag2[rc] true; // 2. 递归进入下一行 dfs(ans, queens, col, diag1, diag2, r 1); // 3. 撤销选择回溯恢复状态 col[c] diag1[r c] diag2[rc] false; } } } }1.有硬性要求 每行每列只能放一个皇后因为在同一个/斜线上面 x y的坐标为一个定值在同一个\斜线上面 x - y的值为一个定值所以说可以利用这个性质来进行判断2.int[] queens new int[n]; // 皇后放在 (r,queens[r])queens[2] 3 代表(2, 3) 有一个皇后3.boolean[] diag1 new boolean[n * 2 - 1]; boolean[] diag2 new boolean[n * 2 - 1];这是代表左斜线和右斜线在n * n的矩阵中 单个方向一共有2 * n - 1条斜线