首页 > 其他分享 >N皇后-力扣

N皇后-力扣

时间:2024-06-19 11:59:33浏览次数:21  
标签:return int 力扣 curNum vector result 皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

  • 这道题目也是回溯题目,创建一个 vector<vector<string>> results; 用来存放一组结果,使用vector<string> result(n, string(n, ‘.’)); 来模拟一个棋盘
  • 每次向棋盘的一行添加一个 皇后,在添加之前,需要判断添加的位置是否是有效位置, 判断是否是有效位置,需要一个函数来判断 这个位置 行、列、左右对斜线 都不能有 皇后,因为添加操作时按行进行,所以当前行以及之后的行时肯定没由皇后的,因此可以对判断进行剪枝操作。
  • 剪枝操作,只需判断 所在列,之前的行是否存在 皇后,右上斜线 和左上斜线是否存在 皇后
  • 在判断完成后,如果这个位置有效,则在这个位置添加皇后,并进行递归,对下一行添加

代码如下:

class Solution {
private:
    vector<vector<string>> results;
public:
    bool isVaild(int row, int col, int n, vector<string>& result){
        for(int i = 0; i < row; i++){
            if(result[i][col] == 'Q'){
                return false;
            }
        }
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
            if(result[i][j] == 'Q'){
                return false;
            }
        }
        for(int i = row - 1, j = col - 1; i >=0 && j >=0; i--, j--){
            if(result[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
    void backtracking(int n, int curNum, vector<string>& result){
        if(curNum == n){
            results.push_back(result);
            return;
        }
        for(int i = 0; i < n; i++){
            if(isVaild(curNum, i, n, result)){
                result[curNum][i] = 'Q';
                backtracking(n, curNum + 1, result);
                result[curNum][i] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> result(n, string(n, '.'));
        backtracking(n, 0, result);
        return results;
    }
};

标签:return,int,力扣,curNum,vector,result,皇后
From: https://blog.csdn.net/why_12134/article/details/139776516

相关文章

  • DAY4-力扣刷题
    1.四数之和18.四数之和-力扣(LeetCode)给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a],nums[b],nums[c],nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):0<=a,b,c,d <na......
  • 算法第六天:力扣第977题有序数组的平方
    一、977.有序数组的平方的链接与题目描述977.有序数组的平方的链接如下所示:https://leetcode.cn/problems/squares-of-a-sorted-array/description/https://leetcode.cn/problems/squares-of-a-sorted-array/description/   给你一个按 非递减顺序 排序的整数数组 n......
  • 力扣刷题记录: 1339. 分裂二叉树的最大乘积
        本题是第174场周赛的Q3,LC竞赛分为1675.方法一.递归(超时)    单纯使用递归对每一个节点进行遍历,代码如下:classSolution{longlongans=-1;public:intmaxProduct(TreeNode*root){longlongtotal_sum=sum(root);......
  • 力扣刷题记录: 1424. 对角线遍历Ⅱ
        本题是第182场周赛的Q3,LC竞赛分为1780。方法一.利用反对角线性质    在同一条反对角线上的元素的i+j值是相同的,同时,根据遍历的方式可知,i值越大的元素在同一条反对角线之中越先被遍历,i+j值越小的反对角线越早被遍历。考虑采用有序的map对i+j......
  • 洛谷 P1219 八皇后
    题目链接:八皇后思路    这是一个典型的搜索题目,从前往后依次枚举行数,从第一行开始依次枚举皇后的纵坐标,并判断当前坐标是否满足题目要求,满足题目要求则标记将答案存储,并继续向下枚举下一行。由分析可得每条对角线上的任意一点的横纵坐标满足公式i-j+n的值与对角......
  • 【动态规划】| 路径问题之不同路径II 力扣63
    ......
  • 力扣第198题“打家劫舍”
    关注微信公众号数据分析螺丝钉免费领取价值万元的python/java/商业分析/数据结构与算法学习资料在本篇文章中,我们将详细解读力扣第198题“打家劫舍”。通过学习本篇文章,读者将掌握如何使用动态规划来解决这一问题,并了解相关的复杂度分析和模拟面试问答。每种方法都将配以......
  • 【力扣真题】3.哈希表|算法真题程序设计数据结构考研保研复试机试面试秋招春招蓝桥杯
    242.有效的字母异位词给定两个字符串s和t,编写一个函数来判断t是否是s的字母异位词。示例1:输入:s=“anagram”,t=“nagaram”输出:true示例2:输入:s=“rat”,t=“car”输出:false说明:你可以假设字符串只包含小写字母。力扣题目链接思......
  • 验证二叉搜索树-力扣
    第一次做这道题时,想的解法是递归去判断比较左节点小于中间节点,右节点大于中间节点,而这恰恰进入了陷阱,这道题不仅仅是判断子树是否左节点小于中间节点,右节点大于中间节点;要比较的是左子树所有节点小于中间节点,右子树所有节点大于中间节点。附上错误代码:classSolution{pu......
  • 力扣面试题 02.07. 链表相交
    一 题目:二思路:本题介绍两种思路解题,个人推荐思路一快速好理解 思路一: 1.先把其中一个链表的值变成负数 2.遍历另一个链表第一个出现负数的值就是交点 3.还原被改的链表 思路二:1.先用第一个链表的头节点head1搜索指针q遍历第一个链表直到为空,再把q放到head2......