打卡算法☆LeetCode 52、N皇后II 算法解析

网友投稿 523 2022-05-29

推荐阅读

CSDN主页

GitHub开源地址

Unity3D插件分享

简书地址

☆打卡算法☆LeetCode 52、N皇后II 算法解析

我的个人博客

QQ群:1040082875

大家好,我是小魔龙,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是皇后的数量。

三、总结

这道题非常经典。

总结来说就是一层层的搜索。

然后使用三个列表去标记每一层那些各自可以放置皇后。

然后找到解。

数据结构

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:C语言: 字符数组与字符串总结
下一篇:RDD有哪些特点
相关文章