面试题库 › C++ / 后端 › 八皇后 / N 皇后问题

八皇后 / N 皇后问题

难度 ★★☆在 1 场真实面经中被问到 方向:C++ / 后端考点:贪心与回溯

哪些公司问过

文远知行1

常见岗位:自动驾驶

答案要点

  1. 按行回溯,每行放一个皇后,行冲突天然避免
  2. 列、主对角线 row-col、副对角线 row+col 三组标记实现 O(1) 冲突判断
  3. 递归到第 n 行记录解,返回时撤销标记完成回溯
  4. 八皇后共 92 个解,时间上界 O(n!),空间 O(n)
  5. 可用位运算表示占用状态,用 x & -x 取最低可放位进一步加速

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题