文章目录
写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【N皇后】【回溯】【位运算】
题目来源
解题思路
N 皇后问题研究的是将 N 个皇后放置在 nxn
的棋盘上,并且使皇后彼此之间不能互相攻击。因为皇后可横直斜走,且格式不限。所以 N 皇后问题本质上需要保证 nxn
的棋盘上每一行、每一列、每一条与棋盘主副对角线平行的斜线上仅有一个皇后。
方法一:基于集合的回溯
代码
class Solution {
private:
// 从第 row 行开始更新
void backtrack(int& res, vector<int>& queens, int n, int row,
unordered_set<int>& columns, unordered_set<int>& diagnoals1, unordered_set<int>& diagnoals2) {
if (row == n) { // 皇后已经放在完 N 行了
++res;
}
for (int i = 0; i < n; ++i) {
if (columns.find(i) != columns.end()) { // 第 i 列已经放置过皇后了
continue;
}
int diagnoal1 = row - i;
if (diagnoals1.find(diagnoal1) != diagnoals1.end()) { // 与主对角线平行的(包括自己)斜线上有皇后了
continue;
}
int diagnoal2 = row + i;
if (diagnoals2.find(diagnoal2) != diagnoals2.end()) { // 与副对角线平行的(包括自己)斜线上有皇后了
continue;
}
queens[row] = i;
columns.insert(i);
diagnoals1.insert(diagnoal1);
diagnoals2.insert(diagnoal2);
backtrack(res, queens, n, row + 1, columns, diagnoals1, diagnoals2);
// 恢复现场
queens[row] = -1;
columns.erase(i);
diagnoals1.erase(diagnoal1);
diagnoals2.erase(diagnoal2);
}
}
public:
int totalNQueens(int n) {
int res = 0;
vector<int> queens(n, -1); // queens[i] = a 表示 i 行皇后的位置为 a
unordered_set<int> columns;
unordered_set<int> diagnoals1, diagnoals2;
backtrack(res, queens, n, 0, columns, diagnoals1, diagnoals2);
return res;
}
};
复杂度分析
时间复杂度: O ( n ! ) O(n!) O(n!)。
空间复杂度: O ( n ) O(n) O(n)。
方法二:基于位运算的回溯
以下代码的核心仍是 详细分析 的解法,只是有些地方进行了代码精简。
代码
class Solution {
private:
int res = 0;
void backtrack(const int n, int row, int col, int diagnoals1, int diagnoals2) {
if (row == n) {
++res;
return;
}
int bits = ((1 << n) - 1) & ~(col | diagnoals1 | diagnoals2);
while (bits != 0) {
int pick = bits & (-bits);
backtrack(n, row + 1, col | pick, (diagnoals1 | pick) << 1, (diagnoals2 | pick) >> 1);
bits &= bits - 1;
}
}
public:
int totalNQueens(int n) {
backtrack(n, 0, 0, 0, 0);
return res;
}
};
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。