力扣面试题 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…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...
