【Day 41 】2021-06-19 - 52. N 皇后 II
题目描述
52. N 皇后 II
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/n-queens-ii/
前置知识
- 回溯
- 深度优先遍历
题目描述
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。 示例: 输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
我的回答
解法一
时空复杂度
时间复杂度：O(n^2)
空间复杂度: O(n)
回溯法 重点是知道 右斜线是row+ i 左斜线是row-iÏ
var totalNQueens = function (n) {
let result = 0
let leftSet = new Set()
let rightSet = new Set()
let colSet = new Set()
const backTrace = (row, col) => {
if (row === n) {
result++
return
}
for (let i = 0; i < n; i++) {
let left = row - i
if (leftSet.has(left)) continue
let right = row + i
if (rightSet.has(right)) continue
if (colSet.has(i)) continue
leftSet.add(left)
rightSet.add(right)
colSet.add(i)
backTrace(row + 1, col)
leftSet.delete(left)
rightSet.delete(right)
colSet.delete(i)
}
}
backTrace(0, 0)
return result
};