当前位置: 首页 > news >正文

力扣面试题 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 题目描述 思路 八皇后问题的性质可以利用回溯来解决&#xff0c;将大问题具体分解成如下待解决问题&#xff1a; 1.以棋盘的每一行为回溯的决策阶段&#xff0c;判断当前棋盘位置能否放置棋子 2.如何判…...

2023年第十二届数学建模国际赛小美赛A题太阳黑子预测求解分析

2023年第十二届数学建模国际赛小美赛 A题 太阳黑子预测 原题再现&#xff1a; 太阳黑子是太阳光球上的一种现象&#xff0c;表现为比周围区域暗的暂时斑点。它们是由抑制对流的磁通量浓度引起的表面温度降低区域。太阳黑子出现在活跃区域内&#xff0c;通常成对出现&#xff…...

jsp 分页查询展示,实现按 上一页或下一页实现用ajax刷新内容

要实现按上一页或下一页使用 Ajax 刷新内容&#xff0c;可以按照以下步骤进行操作&#xff1a; 1. 在前端页面中添加两个按钮&#xff0c;分别为“上一页”和“下一页”。当用户点击按钮时&#xff0c;触发 Ajax 请求。 2. 在后端控制器中接收 Ajax 请求&#xff0c;并根据传…...

基于ssm在线云音乐系统的设计与实现论文

摘 要 随着移动互联网时代的发展&#xff0c;网络的使用越来越普及&#xff0c;用户在获取和存储信息方面也会有激动人心的时刻。音乐也将慢慢融入人们的生活中。影响和改变我们的生活。随着当今各种流行音乐的流行&#xff0c;人们在日常生活中经常会用到的就是在线云音乐系统…...

简谈PostgreSQL的wal_level=logic

一、PostgreSQL的wal_levellogic的简介 wal_levellogic 是 PostgreSQL 中的一个配置选项&#xff0c;用于启用逻辑复制&#xff08;logical replication&#xff09;功能。逻辑复制是一种高级的数据复制技术&#xff0c;它允许您将变更&#xff08;例如插入、更新和删除&#…...

自动化巡检实现方法 (一)------- 思路概述

一、自动化巡检需要会的技能 1、因为巡检要求一天24小时全天在线&#xff0c;因此巡检程序程序一定会放在服务器上跑&#xff0c;所以要对linux操作熟悉哦 2、巡检的代码要在git上管理&#xff0c;所以git的基本操作要熟悉 3、为了更方便不会代码的同学操作&#xff0c;所以整个…...

mysql获取时间异常

1.查看系统时间 时区是上海&#xff0c;本地时间正常 [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…...

维基百科文章爬虫和聚类:高级聚类和可视化

一、说明 维基百科是丰富的信息和知识来源。它可以方便地构建为带有类别和其他文章链接的文章&#xff0c;还形成了相关文档的网络。我的 NLP 项目下载、处理和应用维基百科文章上的机器学习算法。 在我的上一篇文章中&#xff0c;KMeans 聚类应用于一组大约 300 篇维基百科文…...

springboot智慧导诊系统源码:根据患者症状匹配挂号科室

一、系统概述 医院智慧导诊系统是在医疗中使用的引导患者自助就诊挂号&#xff0c;在就诊的过程中有许多患者不知道需要挂什么号&#xff0c;要看什么病&#xff0c;通过智慧导诊系统&#xff0c;可输入自身疾病的症状表现&#xff0c;或选择身体部位&#xff0c;在经由智慧导诊…...

Shell脚本如何使用 for 循环、while 循环、break 跳出循环和 continue 结束本次循环

Shell脚本如何使用 for 循环、while 循环、break 跳出循环和 continue 结束本次循环 下面是一个简单的 Shell 脚本示例&#xff0c;演示了如何使用 for 循环、while 循环、break 跳出循环和 continue 结束本次循环。 #!/bin/bash# For循环 echo "For循环示例&#xff1a;…...

n个人排成一圈,数数123离队

#include<stdio.h> int main() { int i, n100,k0,j0,a[1000]{0};//k&#xff1a;数数123的变量&#xff0c;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 深层网络 浅层神经网络参数过多&#xff0c;导致模型的复杂度和计算量很高&#xff0c;难以训练。而深层…...

【Vue】修改组件样式并动态添加样式

文章目录 目标修改样式动态添加/删除样式样式不生效 注意&#xff1a;类似效果el-step也可以实现&#xff0c;可以不用手动实现。这里只是练习。 目标 使用组件库中的组件&#xff0c;修改它的样式并动态添加/删除样式。 修改样式 组件中的一些类可能添加样式无法生效。如Ele…...

GO设计模式——12、外观模式(结构型)

目录 外观模式&#xff08;Facade Pattern&#xff09; 外观模式的核心角色&#xff1a; 优缺点 使用场景 代码实现 外观模式&#xff08;Facade Pattern&#xff09; 外观模式&#xff08;Facade Pattern&#xff09;又叫作门面模式&#xff0c;是一种通过为多个复杂的子…...

一.初始typescript

什么是ts 首先我们要确认typescript是一个语言&#xff0c;是等同于JavaScript层级得&#xff0c;并不是一些人认为得是JavaScript得类型规范工具或者插件。 ts与js的差异 从type script这个名字就可以看出&#xff0c;ts其实是JavaScript的一个类型化超集&#xff0c;它增…...

mp3的播放

1.这段vue代码会播放声音&#xff0c;但是会有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问题:滑铲

最近想做一个跑酷游戏&#xff0c;从mixamo下载滑铲动作后&#xff0c;出了很多动画的问题。花了两周时间&#xff0c;终于是把所有的问题基本上都解决了。 常见问题&#xff1a; 1.【动画序列】人物不移动。 2.【动画序列】人物移动朝向错误。 3.【蒙太奇】人物移动后会被拉回…...

容器资源视图隔离 —— 筑梦之路

先做个记录&#xff0c;抽空再整理 K8s 部署 Lxcfs 准入控制器&#xff0c;实现容器中资源单独可见 - 「Johny」PlayGround Kubernetes 中利用 LXCFS 控制容器资源可见性 - 码农教程 容器资源可视化隔离的实现方法_51CTO博客_容器隔离技术 Lxcfs在容器集群中的使用-腾讯云开…...

浅析嵌入式GUI框架-LVGL

LVGL (Light and Versatile Graphics Library) 是最流行的免费开源嵌入式图形库&#xff0c;可为任何 MCU、MPU 和显示类型创建漂亮的 UI 嵌入式GUI框架对比 Features/框架LVGLFlutter-elinuxArkUI(鸿蒙OS)AWTKQTMIniGUIemWinuC/GUI柿饼UI跨平台是是鸿蒙OS平台是是是是是是设备…...

Unity 关于SetParent方法的使用情况

在设置子物体的父物体时&#xff0c;我们使用SetParent再常见不过了。 但是通常我们只是使用其中一个语法&#xff1a; public void SetParent(Transform parent);使用改方法子对象会保持原来位置&#xff0c;跟使用以下方法效果一样&#xff1a; public Transform tran; ga…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...