当前位置: 首页 > 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…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...