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

举报
恬静的小魔龙 发表于 2022/01/27 15:02:59 2022/01/27
【摘要】 推荐阅读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 皇后问题 不同的解决方案的数量。

image.png

示例 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;
        }
    }
}

image.png

3、时间复杂度

时间复杂度 : O(N!)

其中N是皇后的数量。

空间复杂度: O(N)

其中N是皇后的数量。

三、总结

这道题非常经典。

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

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

然后找到解。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。