☆打卡算法☆LeetCode 52、N皇后II 算法解析
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个整数,返回N皇后问题的不同解决方案的数量。”题目链接:来源:力扣(LeetCode)链接:52. N皇后 II - 力扣...
推荐阅读
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
一、题目
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是皇后的数量。
三、总结
这道题非常经典。
总结来说就是一层层的搜索。
然后使用三个列表去标记每一层那些各自可以放置皇后。
然后找到解。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)