day79（2.7）——leetcode面试经典150

52. N 皇后 II

52. N皇后Ⅱ

我以前写这题的时候就没搞明白，她是怎么计算两边的对角线的，然后我今天自己推了一下，但是我是横竖进行遍历，传的参数是放了几个皇后，导致不仅时间复杂度很高，而且还可能导致一行里面有多个皇后，还导致搜索空间爆炸，所以应该采用dfs传入行数这一个参数，然后遍历每列的每一个

N 皇后问题有一个隐含但必须遵守的约束：

✅每行只能放一个皇后

void dfs(int x, int y, int t) { for (int i = x; i < w; i++) { for (int j = y; j < w; j++) { // 尝试在 (i,j) 放皇后 } } }

会导致：

1. 同一行可能放多个皇后
   • 比如先在(0,0)放一个，回溯后又在(0,1)放一个 → 违反规则！
2. 大量重复解
   • 皇后顺序不同但位置相同（如先放 (0,0) 再放 (1,1)，或先放 (1,1) 再放 (0,0)）会被算作两个解
3. 搜索空间爆炸
   • 你是在所有格子中“任意选 k 个不冲突的位置”，而不是“每行选一个”

✅ 正确策略：按行递归，每行只放一个皇后

标准做法是：

• 第t层 DFS 处理第t行
• 在该行尝试每一列j
• 这样天然保证每行一个皇后，且不会重复计数

题目：

题解：

class Solution { int w; //竖 boolean[] col; //左对角线——x+y boolean[] left; //右对角线——w-1+y-x boolean[] right; int res; //以行数为参数 void dfs(int row) { if(row==w) { res++; return; } for(int j=0;j<w;j++) { if(col[j]==false&&left[row+j]==false&&right[w-1+j-row]==false) { //放皇后 col[j]=true; left[row+j]=true; right[w-1+j-row]=true; dfs(row+1); //恢复现场 col[j]=false; left[row+j]=false; right[w-1+j-row]=false; } } } public int totalNQueens(int n) { w = n; col = new boolean[n]; left = new boolean[2*n]; right = new boolean[2*n]; res = 0; dfs(0); return res; } }