有时候真的不得不感慨一句，面试，简直就是一个翻车大赛。眼看着就快稳了，忽然脑袋一热、舌头一拐，说出一句惊天地泣鬼神的话，然后，完了——车翻了！
就说这位兄弟吧，面试都快结束了，本来和面试官聊得不错，可能以为已经稳了，结果突然来了一句“那今天就先到这里吧。”？这话一出口，估计他自己都能感觉到空气的静止。
但是，这几年互联网的大厂、独角兽一轮轮招人，也让面试市场变得越来越“内卷”。每个人都想在短短几分钟内展示出自己独特的价值，但展示方式真不是只有一种，关键是要稳。
不信大家去看看面试场外等候区的表情就知道了——每个候选人脸上写的都是“我上我也行”，但一轮轮比下来，有些人自信心迅速缩水。
面试官见人无数，早就知道谁是真有料，谁是靠“嘴皮子功夫”撑场面。咱们在这种时候，真别想着去抢主导权，还是老老实实做好自己。
今日算法题
说到这，接下来我们不妨聊聊面试中经常出现的一个算法题：N 皇后问题。
N 皇后问题是一个经典的回溯算法问题，它要求在一个 N × N 的棋盘上摆放 N 个皇后，使得它们互不攻击，即任何两个皇后都不能处于同一行、同一列或同一对角线。
问题的核心是如何在棋盘上寻找可行的位置进行放置，并且确保所有放置的皇后都符合不互相攻击的规则。
首先，理解这个问题的关键是要处理约束条件。皇后只能位于空白的格子，且不能在同一行、同一列或者对角线上有另一个皇后。
因此，在解决这个问题时，最直接的思路是通过回溯法进行深度优先搜索，尝试逐行摆放皇后，并判断每次放置是否符合约束。如果不符合，就回退到上一步并尝试其他位置。
具体来说，我们可以采用递归方法来实现回溯。每次递归尝试将一个皇后放置在当前行的一个位置，并且记录该位置所占用的列和对角线。
如果某一行的位置可以放置皇后，则进入下一行进行尝试。如果在某一行无法找到符合条件的位置，那么就回退到上一行，尝试其他可能的位置。这个过程直到所有皇后都被成功放置。
为了实现这个算法，我们可以使用三个数组来帮助判断是否有其他皇后与当前放置位置冲突：一个数组用于记录哪些列已经被占用，另一个数组用于记录哪些主对角线（从左上到右下方向）已经被占用，第三个数组用于记录哪些副对角线（从右上到左下方向）已经被占用。通过这三个数组，我们能够在常数时间内检查当前位置是否冲突。
我们通过 JavaScript 实现这个算法。首先，我们定义一个数组来表示棋盘上的每一行，数组的索引代表行号，数组的值代表皇后所在的列。
接着，定义辅助数组来记录哪些列、主对角线和副对角线已经被占用。然后，我们通过递归回溯的方式进行深度优先搜索，尝试将皇后放置到每一行的每一个位置，并检查是否符合条件。
最终的目标是找到所有满足条件的解法，并将它们展示出来。每当我们成功放置 N 个皇后时，我们就得到了一个有效的解，并将其记录下来。
下面是使用 JavaScript 实现 N 皇后问题的代码：
function solveNQueens(n) {
const res = [];
const board = Array(n).fill().map(() => Array(n).fill('.'));
const cols = new Set(); // 记录列是否被占用
const diag1 = new Set(); // 记录主对角线是否被占用
const diag2 = new Set(); // 记录副对角线是否被占用
function backtrack(row) {
if (row === n) {
const solution = board.map(r => r.join(''));
res.push(solution);
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
continue;
}
board[row][col] = 'Q'; // 放置皇后
cols.add(col); // 标记列被占用
diag1.add(row - col); // 标记主对角线被占用
diag2.add(row + col); // 标记副对角线被占用
backtrack(row + 1); // 尝试下一行
board[row][col] = '.'; // 撤销放置
cols.delete(col); // 撤销列占用
diag1.delete(row - col); // 撤销主对角线占用
diag2.delete(row + col); // 撤销副对角线占用
}
}
backtrack(0);
return res;
}
console.log(solveNQueens(4));
在这段代码中，我们通过递归函数backtrack来实现回溯过程。每次递归时，我们遍历当前行的每一列，检查该位置是否符合放置条件。
如果符合，就放置皇后并进入下一行；如果不符合，则跳过该列，尝试下一个位置。当我们成功放置所有 N 个皇后时，将棋盘的状态保存到res数组中。最终返回res即为所有的解。
通过上述回溯算法，我们可以得到所有满足条件的解法。在给定的 N 值下，算法会找出所有可能的摆放方式并返回。
目前，对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥私藏精品 热门推荐 虎哥作为一名老码农，整理了全网最全《前端资料合集》。
