代码随想录算法训练营第三十天|总结、332.重新安排行程、51.N皇后、37.解数独

本文主要是介绍代码随想录算法训练营第三十天|总结、332.重新安排行程、51.N皇后、37.解数独,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录 (programmercarl.com)

总结

332.重新安排行程

欧拉通路和欧拉回路:

欧拉通路:对于图G来说,如果存在一条通路包含G的所有边,则该通路称为欧拉通路,也称欧拉路径。
欧拉回路:如果欧拉路径是一条回路,那么称其为欧拉回路。
欧拉图:含有欧拉回路的图是欧拉图。

题目中说必然存在一条有效路径,所以至少是半欧拉图,也可以是欧拉图。

深度优先搜索(DFS):

对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。

遍历欧拉图——Hierholzier算法

主要步骤:从一个可能的起点出发,进行深度优先搜索,但是每次沿着辅助边从每个顶点移动到另外一个顶点的时候,都需要删除这个辅助边。如果没有可移动的路径,则将所在节点加入到栈中(先进后出==所以后面步骤4需要逆序输入),并返回。

算法思路:

1)任选一点为起始点,并记录;

2)从起点出发到达任意一个邻接点,新到达的点成为新的起点,删除经过的边,删除孤立点,记录经过的点;

3)重复步骤2直至回到初始点,此时到达步骤1,将本次记录的点和上次记录的点集合拼接。若本图成为空图,到达步骤4;

4)逆序输出所有记录点。

只有入度与出度差为 1 的节点会导致死胡同

====代码待更新====

51.N皇后

皇后们的约束条件:

  1. 不能同行
  2. 不能同列
  3. 不能同斜线

棋盘的宽度就是for循环的长度,递归的深度就是棋盘的高度,这样就可以套进回溯法的模板里了

回溯算法主体里面需要放一个判断是否可以防止皇后Q的判断函数

其中对于不能同斜线,需要判断45°和135°,分别如下两种情况:

i - 2, j - 2
i - 1, j - 1
i, j
i - 2, j + 2
i - 1, j + 1
i, j


Java中ArrayList与LinkedList的区别 - 知乎 (zhihu.com)icon-default.png?t=N7T8https://zhuanlan.zhihu.com/p/33141246补充一点ArrayList和LinkedList的区别:

1、ArrayList的实现是基于数组,LinkedList的实现是基于双向链表。

2、对于随机访问,ArrayList优于LinkedList

3、对于插入和删除操作,LinkedList优于ArrayList

4、LinkedList比ArrayList更占内存,因为LinkedList的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。

class Solution {List<List<String>> res = new ArrayList<>();//需要在一开始就声明,因为后面res.add(Array2List(chessboard));会用到public List<List<String>> solveNQueens(int n) {//初始化所有棋盘格为.char[][] chessboard = new char[n][n];//注意此处的棋盘里面放的都是字符,所以需要定义为char类型的数组for (char[] c : chessboard) {Arrays.fill(c, '.');}backtracking(n, 0, chessboard);return res;}public void backtracking(int n, int row, char[][] chessboard){//n表示该棋盘格的规格大小,row表示当前遍历到的行数if (row == n){//表示递归终止条件,开始收集结果res.add(Array2List(chessboard));return;}for (int col = 0; col < n; col++) {if (isValid(n, row, col, chessboard)){chessboard[row][col] = 'Q';backtracking(n, row + 1, chessboard);chessboard[row][col] = '.';//回溯回去}}}public List Array2List(char[][] chessboard){//表示将数组类型的结果转为所需要的list的集合形式List<String> list = new ArrayList<>();for (char[] c : chessboard) {list.add(String.copyValueOf(c));}return list;}public boolean isValid(int n, int row, int col, char[][] chessboard){//以下操作相当于剪枝,即如果有违反题目要求的情况出现,直接就不进行回溯,减少进入递归的次数//检查列,以为此时调用该方法是固定列,这时遍历行去检查列,改变col去检查行for (int i = 0; i < row; i++) {if (chessboard[i][col] == 'Q'){return false;}}//检查45°斜线for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (chessboard[i][j] == 'Q'){return false;}}//检查135°斜线for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (chessboard[i][j] == 'Q'){return false;}}return true;}
}

37.解数独

class Solution {public void solveSudoku(char[][] board) {//没有new新的数组,直接修改原来传入的数组,所以返回值为voidbacktracking(board);}public boolean backtracking(char[][] board){//不需要终止条件,因为一旦该数独没有解,会直接返回false,不会陷入死循环//一个for循环遍历棋盘的行,一个for循环遍历棋盘的列,//一行一列确定下来之后,递归遍历这个位置放9个数字的可能性!for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] != '.'){continue;//题目中初始的数独中,空白部分是.,此操作是为了跳过数独中的原始数字}for (char k = '1'; k <= '9'; k++) {if (isValid(i, j, k, board)){board[i][j] = k;if (backtracking((board))){// 如果找到合适一组立刻返回return true;}board[i][j] = '.';}}return false;// 因为如果一行一列确定下来了,这里尝试了9个数都不行,说明这个棋盘找不到解决数独问题的解!// 那么会直接返回,这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去!}}// 遍历完没有返回false,说明找到了合适棋盘位置了return true;}public boolean isValid(int row, int col, char val, char[][] board){//检查同一行是否有重复for (int j = 0; j < 9; j++) {if (board[row][j] == val){return false;}}//检查同一列是否有重复for (int i = 0; i < 9; i++) {if (board[i][col] == val){return false;}}//检查同一个九宫格是否有重复int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) {for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val){return false;}}}return true;}
}

这篇关于代码随想录算法训练营第三十天|总结、332.重新安排行程、51.N皇后、37.解数独的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/585265

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim