力扣面试题 08.12. 八皇后(java回溯解法)
Problem: 面试题 08.12. 八皇后
文章目录
- 题目描述
- 思路
- 解题方法
- 复杂度
- Code
题目描述
思路
八皇后问题的性质可以利用回溯来解决,将大问题具体分解成如下待解决问题:
1.以棋盘的每一行为回溯的决策阶段,判断当前棋盘位置能否放置棋子
2.如何判断当前棋盘位置是否可以放置棋子
解题方法
1.回溯函数:
1.1定义二维结果集result,char类型二维数组(作为棋盘)并初始化
1.2当决策阶段row等于n时,将当前的决策路径添加到result中(注意决策阶段应该等于n时才说明将棋盘判断完了,因为当决策阶段等于n时说明0 - n-1 已经判断处理完)
1.3由于在每一个决策阶段我们需要对棋盘的每一列棋格判断(穷举),所以以每一列为循环判断(调用判断当前位置是否可以添加棋子的函数),若可以则先将棋盘当前位置添上棋子,再回溯判断当前行的下一行,判断完当前行后还需恢复当前棋盘位置的状态
2.判断当前位置是否可以添加棋子函数
2.1依次利用循环判断当前位置的列,右上角,左上角是否存在棋子,存在则不可在当前位置添加棋子
复杂度
时间复杂度:
O ( n ! ) O(n!) O(n!)
空间复杂度:
O ( n ) O(n) O(n)
Code
class Solution {//Two-dimensional result setprivate List<List<String>> result = new ArrayList<>();/*** Get the solution to the Eight Queens problem** @param n The size of board* @return List<List < String>>*/public List<List<String>> solveNQueens(int n) {char[][] board = new char[n][n];for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {board[i][j] = '.';}}backtrack(0, board, n);return result;}/*** Find the solution of the eight queens problem by backtracking** @param board Board* @param row The row of board(The decision stage of backtracking)* @param n The size of board*/private void backtrack(int row, char[][] board, int n) {//End condition:A feasible solution is foundif (row == n) {List<String> snapshot = new ArrayList<>();for (int i = 0; i < n; ++i) {snapshot.add(new String(board[i]));}result.add(snapshot);return;}//Each has n ways to placefor (int col = 0; col < n; ++col) {if (isOk(board, n, row, col)) {//optional list//The chess board places pieces in row rows and col columnsboard[row][col] = 'Q';//Investigate the next rowbacktrack(row + 1, board, n);//Recover the selectionboard[row][col] = '.';}}}/*** Determines whether the current column can place chess pieces** @param board The board* @param n The row number and column number of board* @param row The row number of board* @param col The column number of board* @return boolean*/private boolean isOk(char[][] board, int n, int row, int col) {//Check whether columns conflictfor (int i = 0; i < n; ++i) {if (board[i][col] == 'Q') {return false;}}//Check whether top right corner conflictint i = row - 1;int j = col + 1;while (i >= 0 && j < n) {if (board[i][j] == 'Q') {return false;}i--;j++;}//Check whether top left corner conflicti = row - 1;j = col - 1;while (i >= 0 && j >= 0) {if (board[i][j] == 'Q') {return false;}i--;j--;}return true;}
}
相关文章:
力扣面试题 08.12. 八皇后(java回溯解法)
Problem: 面试题 08.12. 八皇后 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路 八皇后问题的性质可以利用回溯来解决,将大问题具体分解成如下待解决问题: 1.以棋盘的每一行为回溯的决策阶段,判断当前棋盘位置能否放置棋子 2.如何判…...
2023年第十二届数学建模国际赛小美赛A题太阳黑子预测求解分析
2023年第十二届数学建模国际赛小美赛 A题 太阳黑子预测 原题再现: 太阳黑子是太阳光球上的一种现象,表现为比周围区域暗的暂时斑点。它们是由抑制对流的磁通量浓度引起的表面温度降低区域。太阳黑子出现在活跃区域内,通常成对出现ÿ…...
jsp 分页查询展示,实现按 上一页或下一页实现用ajax刷新内容
要实现按上一页或下一页使用 Ajax 刷新内容,可以按照以下步骤进行操作: 1. 在前端页面中添加两个按钮,分别为“上一页”和“下一页”。当用户点击按钮时,触发 Ajax 请求。 2. 在后端控制器中接收 Ajax 请求,并根据传…...
基于ssm在线云音乐系统的设计与实现论文
摘 要 随着移动互联网时代的发展,网络的使用越来越普及,用户在获取和存储信息方面也会有激动人心的时刻。音乐也将慢慢融入人们的生活中。影响和改变我们的生活。随着当今各种流行音乐的流行,人们在日常生活中经常会用到的就是在线云音乐系统…...
简谈PostgreSQL的wal_level=logic
一、PostgreSQL的wal_levellogic的简介 wal_levellogic 是 PostgreSQL 中的一个配置选项,用于启用逻辑复制(logical replication)功能。逻辑复制是一种高级的数据复制技术,它允许您将变更(例如插入、更新和删除&#…...
自动化巡检实现方法 (一)------- 思路概述
一、自动化巡检需要会的技能 1、因为巡检要求一天24小时全天在线,因此巡检程序程序一定会放在服务器上跑,所以要对linux操作熟悉哦 2、巡检的代码要在git上管理,所以git的基本操作要熟悉 3、为了更方便不会代码的同学操作,所以整个…...
mysql获取时间异常
1.查看系统时间 时区是上海,本地时间正常 [roottest etc]# timedatectlLocal time: 一 2023-12-04 17:00:35 CSTUniversal time: 一 2023-12-04 09:00:35 UTCRTC time: 一 2023-12-04 09:00:34Time zone: Asia/Shanghai (CST, 0800)NTP enabled: no NTP synchroni…...
维基百科文章爬虫和聚类:高级聚类和可视化
一、说明 维基百科是丰富的信息和知识来源。它可以方便地构建为带有类别和其他文章链接的文章,还形成了相关文档的网络。我的 NLP 项目下载、处理和应用维基百科文章上的机器学习算法。 在我的上一篇文章中,KMeans 聚类应用于一组大约 300 篇维基百科文…...
springboot智慧导诊系统源码:根据患者症状匹配挂号科室
一、系统概述 医院智慧导诊系统是在医疗中使用的引导患者自助就诊挂号,在就诊的过程中有许多患者不知道需要挂什么号,要看什么病,通过智慧导诊系统,可输入自身疾病的症状表现,或选择身体部位,在经由智慧导诊…...
Shell脚本如何使用 for 循环、while 循环、break 跳出循环和 continue 结束本次循环
Shell脚本如何使用 for 循环、while 循环、break 跳出循环和 continue 结束本次循环 下面是一个简单的 Shell 脚本示例,演示了如何使用 for 循环、while 循环、break 跳出循环和 continue 结束本次循环。 #!/bin/bash# For循环 echo "For循环示例:…...
n个人排成一圈,数数123离队
#include<stdio.h> int main() { int i, n100,k0,j0,a[1000]{0};//k:数数123的变量,j记录离开队列人数的变量scanf("%d",&n);for(int ii0; ii<n; ii){ for( i0; i<n; i){// printf("wei%d ",i);if((a[i]0)&&…...
深度学习基础回顾
深度学习基础 浅层网络 VS 深层网络深度学习常用的激活函数Sigmoid 函数ReLU 函数Softplus 函数tanh函数 归纳偏置CNN适用数据归纳偏置 RNN适用数据归纳偏置 浅层网络 VS 深层网络 浅层神经网络参数过多,导致模型的复杂度和计算量很高,难以训练。而深层…...
【Vue】修改组件样式并动态添加样式
文章目录 目标修改样式动态添加/删除样式样式不生效 注意:类似效果el-step也可以实现,可以不用手动实现。这里只是练习。 目标 使用组件库中的组件,修改它的样式并动态添加/删除样式。 修改样式 组件中的一些类可能添加样式无法生效。如Ele…...
GO设计模式——12、外观模式(结构型)
目录 外观模式(Facade Pattern) 外观模式的核心角色: 优缺点 使用场景 代码实现 外观模式(Facade Pattern) 外观模式(Facade Pattern)又叫作门面模式,是一种通过为多个复杂的子…...
一.初始typescript
什么是ts 首先我们要确认typescript是一个语言,是等同于JavaScript层级得,并不是一些人认为得是JavaScript得类型规范工具或者插件。 ts与js的差异 从type script这个名字就可以看出,ts其实是JavaScript的一个类型化超集,它增…...
mp3的播放
1.这段vue代码会播放声音,但是会有audio标签 <template><div><audio id"myAudio" controls><source src"./test.mp3" type"audio/mp3" />Your browser does not support the audio tag.</audio></…...
mixamo根动画导入UE5问题:滑铲
最近想做一个跑酷游戏,从mixamo下载滑铲动作后,出了很多动画的问题。花了两周时间,终于是把所有的问题基本上都解决了。 常见问题: 1.【动画序列】人物不移动。 2.【动画序列】人物移动朝向错误。 3.【蒙太奇】人物移动后会被拉回…...
容器资源视图隔离 —— 筑梦之路
先做个记录,抽空再整理 K8s 部署 Lxcfs 准入控制器,实现容器中资源单独可见 - 「Johny」PlayGround Kubernetes 中利用 LXCFS 控制容器资源可见性 - 码农教程 容器资源可视化隔离的实现方法_51CTO博客_容器隔离技术 Lxcfs在容器集群中的使用-腾讯云开…...
浅析嵌入式GUI框架-LVGL
LVGL (Light and Versatile Graphics Library) 是最流行的免费开源嵌入式图形库,可为任何 MCU、MPU 和显示类型创建漂亮的 UI 嵌入式GUI框架对比 Features/框架LVGLFlutter-elinuxArkUI(鸿蒙OS)AWTKQTMIniGUIemWinuC/GUI柿饼UI跨平台是是鸿蒙OS平台是是是是是是设备…...
Unity 关于SetParent方法的使用情况
在设置子物体的父物体时,我们使用SetParent再常见不过了。 但是通常我们只是使用其中一个语法: public void SetParent(Transform parent);使用改方法子对象会保持原来位置,跟使用以下方法效果一样: public Transform tran; ga…...
Linux系统上RabbitMQ安装教程
一、安装前环境准备 Linux:CentOS 7.9 RabbitMQ Erlang 1、系统内须有C等基本工具 yum install build-essential openssl openssl-devel unixODBC unixODBC-devel make gcc gcc-c kernel-devel m4 ncurses-devel tk tc xz socat2、下载安装包 1)首先&a…...
ES通过抽样agg聚合性能提升3-5倍
一直以来,es的agg聚合分析性能都比较差(对应sql的 group by)。特别是在超多数据中做聚合,在搜索的条件命中特别多结果的情况下,聚合分析会非常非常的慢。 一个聚合条件:聚合分析请求的时间 search time a…...
c++详解栈
一.什么是栈 堆栈又名栈(stack),它是一种运算受限的数据结构(线性表),只不过他和数组不同,数组我们可以想象成一个装巧克力的盒子,你想拿一块巧克力,不需要改变其他巧克…...
Zabbix结合Grafana打造高逼格监控系统
📢📢📢📣📣📣 哈喽!大家好,我是【IT邦德】,江湖人称jeames007,10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】!😜&am…...
Linux设备树
一、起源 减少垃圾代码 减轻驱动开发工作量 驱动代码和设备信息分离 参考Open Fireware设计 用来记录硬件平台中各种硬件设备的属性信息 二、基本组成 两种源文件: xxxxx.dts dts是device tree source的缩写xxxxx.dtsi dtsi是device tree source include的缩…...
计算机方向的一些重要缩写和简介
参考: 深度学习四大类网络模型 干货|机器学习超全综述! 机器学习ML、卷积神经网络CNN、循环神经网络RNN、马尔可夫蒙特卡罗MCMC、生成对抗网络GAN、图神经网络GNN——人工智能经典算法 MLP(Multi Layer Perseption)用在神经网络中…...
ardupilot开发 --- git 篇
一些概念 工作区:就是你在电脑里能看到的目录;暂存区:stage区 或 index区。存放在 :工作区 / .git / index 文件中;版本库:本地仓库,存放在 :工作区 / .git 中 关于 HEAD 是所有本地…...
Linux基础命令练习2
案例2:创建命令练习 请在/root创建三个目录分别为student、file、stu18 请在/opt创建三个文本文件分别为1.txt、a.txt、stu.txt 案例3:复制、删除、移动 在目录/opt下创建一个子目录 etime 在目录/opt/etime/创建文件readme.txt,利用vim写入内容 …...
Vue阶段笔记(有js包)
目录 1.要先上传Vue的js包,包的路径在这: 2.获取 3.定义Vue接管的区域和他所要实现的内容 #整体代码如下: Vue的指令(被绑定得必须有声明) #v-bind #v-model #v-on #V-ifV-else-ifV-elseV-show #v-show #v-for 1.要先上传Vue的js包&…...
执行npm run dev报Error: error:0308010C:digital envelope routines::unsupported问题
vue2element-ui项目,在执行npm run dev的时候突然报错: (node:19424) [DEP0111] DeprecationWarning: Access to process.binding(http_parser) is deprecated. (Use node --trace-deprecation ... to show where the warning was created) Er…...
解决微信小程序中 ‘nbsp;‘ 空格不生效的问题
在微信小程序开发中,我们经常会使用 来表示一个空格。这是因为在 HTML 中,空格会被解析为一个普通字符,而不会产生实际的空白间距。而 是一种特殊的字符实体,它被解析为一个不可见的空格,可以在页面上产生真正的空…...
vue el-select封装及使用
基于Element UI的el-select组件进行封装的。该组件实现了一个下拉选择框,具有许多可配置的属性和事件 创建组件index.vue (src/common-ui/select/index.vue) <template><el-selectref"select"v-model"hValue":allow-create"allo…...
了解linux计划任务
本章主要介绍如何创建计划任务 使用 at 创建计划任务 使用 crontab 创建计划任务 有时需要在某个指定的时间执行一个操作,此时就要使用计划任务了。计划任务有两种: 一个是at计划任务,另一个是 crontab计划任务。 下面我们分别来看这两种计…...
等待和通知
引入 由于线程是抢占式执行的,因此线程之间的执行的先后顺序难以预知 但是实际开发中我们希望合理协调多个线程之间执行的先后顺序. 这里的干预线程先后顺序,并不是影响系统的调度策略(内核里调度线程,仍然是无序调度). 就是相当于在应用程序代码中,让后执行的线程主动放弃被…...
vscode 如何将正则匹配到的字符前批量加字符
最近想用vscode将正则匹配到的东西签名批量https,替换时可以用$1来替换正则匹配到的字符串,如下所示...
上个月暴涨34.6%后,SoundHound AI股票现在还能买入吗?
来源:猛兽财经 作者:猛兽财经 揭开SoundHound AI股价波动的原因 S&P Global Market Intelligence的数据显示,在摆脱了10月份的大幅下跌后,SoundHound AI的股价在11月份实现了34.6%的涨幅。 原因是该公司公布了稳健的第三季…...
Termux+Hexo结合内网穿透轻松实现安卓手机搭建博客网站发布公网访问
文章目录 前言 1.安装 Hexo2.安装cpolar3.远程访问4.固定公网地址 前言 Hexo 是一个用 Nodejs 编写的快速、简洁且高效的博客框架。Hexo 使用 Markdown 解析文章,在几秒内,即可利用靓丽的主题生成静态网页。 下面介绍在Termux中安装个人hexo博客并结合…...
程序员的养生指南(生命诚可贵,一人永流传!珍惜生命,从你我做起)
作为程序员,我们经常需要长时间坐在电脑前工作,这对我们的身体健康造成了很大的影响。为了保持健康,我们需要采取一些养生措施来延寿。下面是我个人的一些养生经验和建议,希望能对大家有所帮助。 1、合理安排工作时间:…...
FP独立站怎么搭建?看这一篇就够了!强烈建议收藏!
在2023疫情结束年,商家为了在跨境电商市场上获取更多的份额,FP建站需求大军席卷而来,越来越多的创业者和企业开始涉足跨境电商独立站领域,尤其是FP独立站,FP商家想要通过FP独立站、FP广告投放,FP支付&#…...
【华为OD题库-068】找出经过特定点的路径长度-java
题目 输入一个字符串,都是以大写字母组成,每个相邻的距离是1,第二行输入一个字符串,表示必过的点。 说明 每个点可过多次。求解经过这些必过点的最小距离是多少? 示例1 输入输出示例仅供调试,后台判题数据一般不包含示…...
高性能队列框架-Disruptor使用、Netty结合Disruptor大幅提高数据处理性能
高性能队列框架-Disruptor 首先介绍一下 Disruptor 框架,Disruptor是一个通用解决方案,用于解决并发编程中的难题(低延迟与高吞吐量),Disruptor 在高并发场景下性能表现很好,如果有这方面需要,…...
Linux学习笔记3 xshell(lnmp)
xshell能连接虚拟机的前提是真机能够ping通虚拟机网址 装OpenSSL依赖文件 [rootlocalhost nginx-1.12.2]# yum -y install openssl pcre-devel 依赖检测[rootlocalhost nginx-1.12.2]# ./configure [rootlocalhost nginx-1.12.2]# yum -y install zlib [rootlocalhost n…...
分享几个可以免费使用GPT工具
1. 国产可以使用GPT3.5和4.0的网站,每日有免费的使用额度,响应速度,注册时不用使用手机号,等个人信息,注重用户隐私,好评! 一个好用的ChatGPT系统 ,可以免费使用3.5 和 4.0https://…...
一篇文章带你快速入门 Nuxt.js 服务端渲染
1. Nuxt.js 概述 1.1 我们一起做过的SPA SPA(single page web application)单页 Web 应用,Web 不再是一张张页面,而是一个整体的应用,一个由路由系统、数据系统、页面(组件)系统等等࿰…...
导入JDBC元数据到Apache Atlas
前言 前期实现了导入MySQL元数据到Apache Atlas, 由于是初步版本,且功能参照Atlas Hive Hook,实现的不够完美 本期对功能进行改进,实现了导入多种关系型数据库元数据到Apache Atlas 数据库schema与catalog 按照SQL标准的解释,…...
大数据项目——基于Django/协同过滤算法的房源可视化分析推荐系统的设计与实现
大数据项目——基于Django/协同过滤算法的房源可视化分析推荐系统的设计与实现 技术栈:大数据爬虫/机器学习学习算法/数据分析与挖掘/大数据可视化/Django框架/Mysql数据库 本项目基于 Django框架开发的房屋可视化分析推荐系统。这个系统结合了大数据爬虫、机器学…...
[网鼎杯 2020 朱雀组]phpweb1
提示 call_user_func()函数先通过php内置函数来进行代码审计绕过system(##不止一种方法) 拿到题目养成一个好的习惯先抓个包 从抓到的包以及它首页的报错来看,这里死活会post传输两个参数func以及p func传输函数,而p则是传输参数的…...
深度学习之注意力机制
注意力机制与外部记忆 注意力机制与记忆增强网络是相辅相成的,神经网络去从内存中或者外部记忆中选出与当前输入相关的内容时需要注意力机制,而在注意力机制的很多应用场景中,我们的外部信息也可以看作是一个外部的记忆 这是一个阅读理解任务…...
WordPress:解决xmlrpc.php被扫描爆破的风险
使用WordPress的朋友都知道,一些【垃圾渣渣】会利用xmlrpc.php文件来进行攻击,绕过WP后台错误登录次数限制进行爆破。虽然密码复杂的极难爆破,但及其占用服务器资源。 方法一、利用宝塔防火墙(收费版) 一般可以直接使…...
Fiddler抓包模拟器(雷电模拟器)
Fiddler设置 List item 打开fiddler,的options 点击OK,重启fiddler 模拟器 更改网络设置 IP可以在电脑上终端上查看 然后在模拟器浏览器中输入IP:端口 安装证书...