【leetcode】N皇后 回溯法c++
目录
51.N皇后
52.N皇后II
51.N皇后
51. N 皇后 - 力扣(LeetCode)
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1:
输入:n = 4 输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1 输出:[["Q"]]
提示:
1 <= n <= 9
class Solution {
private:bool isValid(vector<string>& board,int row,int col,int n){for(int i=row-1;i>=0;i--)//同一列{if(board[i][col]=='Q') return false;}for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)//左上{if(board[i][j]=='Q') return false;}for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++)//右上{if(board[i][j]=='Q') return false;}return true;}void backtrack(vector<vector<string>>& result,vector<string>& board,int row,int n){if(row==n)//row从0开始,到n-1时已经将n个皇后放置好{result.push_back(board);return;}for(int col=0;col<n;col++){if(isValid(board,row,col,n)){board[row][col]='Q';//放置皇后backtrack(result,board,row+1,n);//放置下一行的皇后board[row][col]='.';// 回溯}}}
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> result;vector<string> board(n,string(n,'.'));//初始化棋盘将n*n的棋盘全放置.表示还未放置皇后backtrack(result,board,0,n);return result;}
};
52.N皇后II
52. N 皇后 II - 力扣(LeetCode)
返回 n 皇后问题 不同的解决方案的数量。
注意指针的用法
class Solution {
private:bool isValid(vector<string>& board,int row,int col,int n){for(int i=row-1;i>=0;i--)//同一列{if(board[i][col]=='Q') return false;}for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)//左上{if(board[i][j]=='Q') return false;}for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++)//右上{if(board[i][j]=='Q') return false;}return true;}void backtract(int* count,vector<string>& board,int row,int n){if(row==n){(*count)++;//注意指针的用法,*p取值,p表示的是地址}for(int col=0;col<n;col++){if(isValid(board,row,col,n)){board[row][col]='Q';backtract(count,board,row+1,n);board[row][col]='.';}}}
public:int totalNQueens(int n) {int count=0;vector<string> board(n,string(n,'.'));backtract(&count,board,0,n);//注意传&count,如果直接传count,函数返回时count的值不会改变return count;}
};
相关文章:
【leetcode】N皇后 回溯法c++
目录 51.N皇后 52.N皇后II 51.N皇后 51. N 皇后 - 力扣(LeetCode) 按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上,并且使皇后彼此之间…...
Ubuntu 系统端口查询与管理详细分析
目录 前言1. 查询端口占用情况2. 释放占用的端口3. 修改应用程序的端口 前言 Window的端口被占用,类似的知识点:重装mysql时3306端口被占用解决方法 事情起因是宝塔的CPU负载过大,重启服务进程之后还是爆,后续发现是端口被占用&…...
Unity中使用StartCoroutine协程和Lerp方法,使GameObject缓慢移动
移动方法(传入需要移动的instance和目标位置) public Transform targetPosition; //目标位置 Vector3 target targetPosition.position;private IEnumerator MoveTowardsTarget(GameObject instance, Vector3 target){// 缓慢移动到目标的方法Vector3 …...
C++根据特定字符截取字符串
前言 在 C 中,如果根据特定字符进行字符串的截取,可以使用 std::string 类的成员函数 find() 来查找字符的位置,然后使用 substr() 来截取字符串。以下是一个示例,展示了如何根据指定字符截取字符串。 示例 #include <iostr…...
【How AI Works】读书笔记3 出发吧! AI纵览 第二部分
目录 1.说明 2.第二部分(P9~P10) 机器学习算法总结(监督学习) 3.单词 4.专业术语 1.说明 书全名:How AI Works From Sorcery to Science 作者 Ronald T.Kneusel 2.第二部分(P9~P10) 总结机器学习算法 作者把机器学习的过程比喻成输入-->黑盒-->输出 这里的标签可…...
No Module named pytorchvideo.losses问题解决
问题描述 最近在跑X3D的源码时发现,在conda powershell prompt中安装了pytorchvideo,但是仍然报错:No Module named pytorchvideo.losses 解决方案: 直接去https://gitcode.com/gh_mirrors/py/pytorchvideo/overview?utm_sour…...
Mac终端字体高亮、提示插件
一、安装配置“oh my zsh” 1.1 安装brew /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)" 按照步骤安装即可,安装完成查看版本 brew -v 1.2 安装zsh brew install zsh 安装完成后查看版本 zsh --version 1.3 …...
Flowable 构建后端服务(后端以及数据库搭建) Flowable Modeler 设计器搭建(前端)
案例地址:xupengboo-flowable-example Flowable 构建后端服务(后端以及数据库搭建) 以 Spring Boot 项目为例: 引入 Flowable 必要依赖。 <!-- flowable 依赖 --> <dependency><groupId>org.flowable</gr…...
[Java]微服务拆分
导入项目 本篇及后续的微服务学习都是基于Centos7系统下的Docker部署,因此需要准备: Centos7的环境SSH客户端安装好Docker会使用Docker 之前的学习, 导致虚拟机中存在黑马商城项目以及mysql数据库, 为了保持一致, 需要删除 cd /rootdocker compose down 安装mysq…...
JavaScript逆向爬虫教程-------基础篇之JavaScript混淆原理
目录 一、常量的混淆原理1.1 对象属性的两种访问方式1.2 十六进制字符串1.3 Unicode字符串1.4 字符串的ASCII码混淆1.5 字符串常量加密1.6 数值常量加密二、增加 JS 逆向者的工作量2.1 数组混淆2.2 数组乱序2.3 花指令2.4 jsfuck三、代码执行流程的防护原理3.1 流程平坦化3.2 …...
qt移植到讯为rk3568,包含一些错误总结
qt移植到arm报错动态库找不到 error while loading shared libraries: libAlterManager.so.1: cannot open shared object file: No such file or directory 通过设置环境变量 LD_LIBRARY_PATH就行了。 LD_LIBRARY_PATH是一个用于指定动态链接器在运行时搜索共享库的路径的环…...
使用阿里云快速搭建 DataLight 平台
使用阿里云快速搭建 DataLight 平台 本篇文章由用户 “闫哥大数据” 分享,B 站账号:https://space.bilibili.com/357944741?spm_id_from333.999.0.0 注意:因每个人操作顺序可能略有区别,整个部署流程如果出现出入,以…...
ubuntu设置自启动
1. 把要启动的程序或者脚本(比如A.sh、A1)放在 /usr/sbin 目录中。比如我的 A.sh 只是启动 A1 程序: #!/bin/bash/usr/sbin/A1echo "A1 finish!!!" 需要注意的是,脚本和程序都要有可执行的权限才行 2. 在 /etc/systemd/system 目录中创建 .…...
Paddle分布式训练报NCCL错
应该是没有装NCCL,但是通过NVIDIA官网方式用apt安装报错,说nccl签名有问题 打开官网查找对应版本的nccl:https://developer.nvidia.com/nccl/nccl-legacy-downloads 这里不下载local Ubuntu选项,下载O/S agnostic local install…...
PD3.1快充对我们到底有没有必要?
在科技飞速发展的今天,各种智能设备和电子产品已经渗透到了我们生活的方方面面。随之而来的,是对充电速度和效率的不断追求。正是在这样的背景下,USB联盟于2021年6月发布了最新的快充协议——PD3.1。那么,PD3.1快充协议对我们到底…...
Android OpenGL ES详解——立方体贴图
目录 一、概念 二、如何使用 1、创建立方体贴图 2、生成纹理 3、设置纹理环绕和过滤方式 4、激活和绑定立方体贴图 三、应用举例——天空盒 1、概念 2、加载天空盒 3、显示天空盒 4、优化 四、应用举例——环境映射:反射 五、应用举例——环境映射:折射 六、应用…...
Bugku CTF_Web——字符?正则?
Bugku CTF_Web——字符?正则? 进入靶场 <?php highlight_file(2.php); $keyflag{********************************}; $IM preg_match("/key.*key.{4,7}key:\/.\/(.*key)[a-z][[:punct:]]/i", trim($_GET["id"]), $match); if…...
C# 中Math.Round 和 SQL Server中decimal(18,2) 不想等的问题
首先了解Math.Round方法的默认舍入规则 在C#中,Math.Round方法使用的是“银行家舍入法”(也叫四舍六入五成双)。这种舍入规则是:当要舍弃的数字小于5时直接舍去;当要舍弃的数字大于5时进位;当要舍弃的数字正…...
lab2:docker基础实战
一、实验目的 1.通过本次实验,完成Docker主机的安装和配置、镜像的搜索和下载、容器生命周期的基本管理、容器网络的管理。 2.通过Dockerfile来构建nginx镜像,了解Dockerfile镜像构建过程。 二、实验内容与实验要求 1.完成Docker的安装和配置。 2.完…...
Druid 1.2 源码导读
Druid 是阿里巴巴开源的数据库连接池和监控组件,广泛用于 Java 应用程序中。Druid 1.2 版本提供了高性能的连接池和丰富的监控功能。以下是对 Druid 1.2 源码的导读,帮助你理解其架构和设计。 1. 源码获取 从 GitHub 上获取 Druid 1.2 的源码ÿ…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
