N 皇后(LeetCode 51)
哪些公司问过
答案要点
- 逐行回溯,每行放一个皇后,天然避免行冲突
- 用 cols、行减列、行加列三组标记 O(1) 判断列与两条对角线冲突
- 递归到 row 等于 n 时生成棋盘字符串记录解,回溯时撤销标记
- 时间上界约 O(n!),空间 O(n);n=1 有 1 个解,n=2、3 无解
- 位运算优化:三个整数记录占用,用 x & -x 逐个取可用位置
易错点
- 回溯返回后忘记撤销三个标记,导致后续分支判断错误
- 两条对角线的标识写反或下标越界
- 每次放置都遍历棋盘检查冲突,复杂度多出一个 O(n) 因子
面试官常见追问
- 只求解的个数(LeetCode 52)怎么改?
- 主对角线下标为什么要加 n-1?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。