思路
回溯
用col、dlr、dll分别表示皇后在棋盘列、右斜、左斜上的站位情况
当皇后在col或dlr或dll上有站位就剪枝
n最大为9,所以可以用二进制表示格子站位情况
在同一列位置上的格子 i 相同,列上可以用 col | (1 << i) 来占位
在同一右斜位置上的格子坐标相减相同,右斜上可以用 dlr | (1 << (i - row + n)) 来占位
在同一左斜位置上的格子坐标相加相同,左斜上可以用 dll | (1 << (i + row)) 来占位
代码
- 位运算
var totalNQueens = function (n) {
let res = 0;
function dfs(row, col, dlr, dll) {
if (row === n) return res++;
for (let i = 0; i < n; i++) {
const _col = 1 << i, _dlr = 1 << (i - row + n), _dll = 1 << (i + row);
if ((col & _col) || (dlr & _dlr) || (dll & _dll)) continue;
dfs(row + 1, col | _col, dlr | _dlr, dll | _dll)
}
}
dfs(0, 0, 0, 0)
return res
};
- set
/**
* @param {number} n
* @return {number}
*/
var totalNQueens = function(n) {
// 已经放置皇后的位置集合, 列, 右斜, 左斜
const col_set = new Set(), xy_dif_set = new Set(), xy_sum_set = new Set();
let result = 0
function dfs(path, row) {
if (row >= n) {
result += 1;
return;
}
for(let col = 0; col < n; col ++) {
// 右斜, 左斜
let xy_dif = col - row, xy_sum = col + row;
//如果在当前列,右斜或者左斜上已经放了,则跳过
if (col_set.has(col) || xy_dif_set.has(xy_dif) || xy_sum_set.has(xy_sum)) continue;
// 将当前放置的值存入
addSets(col, xy_dif, xy_sum);
// 构建当前行的放置地图
let tmp = Array(n).fill('.')
tmp[col] = 'Q'
path.push(tmp.join(''))
dfs(path, row + 1);
// 返回上一步
removeSets(col, xy_dif, xy_sum)
}
}
function addSets(col, xy_dif, xy_sum) {
col_set.add(col);
xy_dif_set.add(xy_dif);
xy_sum_set.add(xy_sum);
}
function removeSets(col, xy_dif, xy_sum) {
col_set.delete(col);
xy_dif_set.delete(xy_dif);
xy_sum_set.delete(xy_sum);
}
dfs([], 0)
return result;
};
复杂度分析
时间复杂度 #card=math&code=O%28N%21%29)
空间复杂度 #card=math&code=O%281%29)