回溯
解题思路
以棋盘的左上角作为坐标系原点，先遍历每一行，每一行放置一个皇后，并新建一个 path 数组存储放置的坐标；
再遍历每一行的每一列，判断 path 数组中的坐标和当前的坐标会不会相互攻击；
- 如果会相互攻击，则跳过本次循环；
- 没有相互攻击，则将当前坐标放到 path 数组中（数组的索引为行，数组的值为列）；
最后，当遍历了所有的行结束，把 path 放到结果中；
图解
复杂度
-
时间复杂度：
O(N!)，其中 N 是皇后数量； -
空间复杂度：
O(N)，其中 N 是皇后数量；空间复杂度主要取决于递归调用层数、记录每行每列放置的皇后的数组，递归调用层数不会超过 N ，数组的长度为 N；
代码实现
var solveNQueens = function (n) {
let res = [];
backtrack(res, n, 0, []);
return res;
};
/**
* @param {* strng[][]} res 结果
* @param {* number} n n 个皇后
* @param {* number} rowInx 第几行的棋盘
* @param {* number[]} path 皇后放置的位置
*/
const backtrack = (res, n, rowInx, path) => {
if (rowInx === n) {
// path 里的每一个数据的索引为行，值为皇后的列位置
res.push(path.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - 1 - c)));
return;
}
for (let col = 0; col < n; col++) {
// 是否能在当前位置放置皇后：
// a.是否在同一行： r === rowInx（因为遍历行，不会有重复，所以不需要这个条件）
// b.是否在同一列： c === col
// c.是否在正斜对角线： r+c === rowInx+col（「0,1」和「1.0」反斜对角相交）
// d.是否在反斜对角线： r-c === rowInx-col（「0,0」和「1,1」正斜对角相交）
const canNotSet = path.some((c, r) => c == col || ((r - c) === (rowInx - col)) || ((r + c) === (rowInx + col)));
if (!canNotSet) {
path.push(col);
backtrack(res, n, rowInx + 1, path);
path.pop();
}
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 79. 单词搜索
上一篇
评论
