一、题目
1、算法题目
“给定一个整数，返回N皇后问题的不同解决方案的数量。”
题目链接：
来源：力扣（LeetCode）
链接：52. N皇后 II - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
网络异常，图片无法展示
|
示例 1： 输入： n = 4 输出： 2 解释： 如上图所示，4 皇后问题存在两个不同的解法。 复制代码
示例 2： 输入： n = 1 输出： 1 复制代码
二、解题
1、思路分析
这个题跟51题很像，是51题的升级款，51题是找到N皇后所有可能的解，这道题是只需要得到不同的解决方案的数量，那么就是只需要将所有可能的解改成得到可能的解的数量即可。
这道题还是用回溯法，在放置皇后的时候快速判断每个位置是否可以放置皇后。
2、代码实现
代码参考：
public class Solution { public int TotalNQueens(int n) { var dp = new bool[n, n]; var res = 0; FindP(0, 0); return res; void FindP(int y, int nums) { if (nums == n) { res++; return; } for (int x = 0; x < n; x++) { if (CanP(x, y)) { dp[y, x] = true; FindP(y + 1, nums + 1); dp[y, x] = false; // 撤销 } } } bool CanP(int x, int y) { // 上 for (int i = y - 1; i >= 0; i--) if (dp[i, x]) return false; // 左上 for (int i = y - 1, j = x - 1; i >= 0 && j >= 0; i--, j--) if (dp[i, j]) return false; // 右上 for (int i = y - 1, j = x + 1; i >= 0 && j < n; i--, j++) if (dp[i, j]) return false; return true; } } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(N!)
其中N是皇后的数量。
空间复杂度： O(N)
其中N是皇后的数量。
三、总结
这道题非常经典。
总结来说就是一层层的搜索。
然后使用三个列表去标记每一层那些各自可以放置皇后。
然后找到解。
