通用解题法——回溯算法（理解+练习）
积累算法经验，积累解题方法——回溯算法，你必须要掌握的解题方法！
什么是回溯算法呢？
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
最简单的理解就是我们走迷宫的时候，走到一个节点，然后有很多路，选一条路不通则退回该节点走其他路；都走不通再往上一个节点倒退，直到找出迷宫出口。
只是简单的概念无法真正理解这种算法的应用场景，这里用一道力扣题来进行讲解：
leetcode 79. 单词搜索
难度：中等
题目：给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]
给定 word = “ABCCED”, 返回 true
给定 word = “SEE”, 返回 true
给定 word = “ABCB”, 返回 false
提示：
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
来源：力扣（LeetCode）
- 链接：https://leetcode-cn.com/problems/word-search
这道题使用回溯算法就是非常好的解法，在性能上也是非常不错的。
这里我们可以将首字母对应的每一个坐标都当做我们的迷宫入口，之后上下左右进行寻找，找到则继续，找不到就往上一级回溯，具体解法如下👇
public class _79_单词搜索 {public boolean exist(char[][] board, String word) {if(word.length() == 0){return false;}char start = word.charAt(0);for(int i = 0; i < board.length; i++){for(int j = 0; j < board[0].length; j++){if(start != board[i][j]){continue;}else{if(find(board, word, 0, i, j, 's')){return true;}else{continue;}}}}return false;}/**** @param board* @param word* @param index word下标* @param x 当前的 board[x][y]* @param y 当前的 board[x][y]* @param pre 规定了s为开头 u为向上 d为向下 l为向左 r为向右* 把已经经过的路径中的字母换成0，避免重复，这一趟走完再复原，以免影响其他方向的进行。* @return*/private boolean find(char[][] board, String word, int index, int x, int y, char pre){//System.out.println("index:" + index + ", " + "x:" + x + ",y:" + y);if(index == word.length() - 1 && word.charAt(index) == board[x][y]){return true;}if(index >= word.length() || word.charAt(index) != board[x][y]){return false;}boolean found = false;//向上寻找if(!found && pre != 'd' && x > 0){char tmp = board[x][y];board[x][y] = '0';found = find(board, word, index + 1, x - 1, y, 'u');board[x][y] = tmp;}//向下寻找if(!found && pre != 'u' && x < board.length - 1){char tmp = board[x][y];board[x][y] = '0';found = find(board, word, index + 1, x + 1, y, 'd');board[x][y] = tmp;}//向左寻找if(!found && pre != 'r' && y > 0){char tmp = board[x][y];board[x][y] = '0';found = find(board, word, index + 1, x, y - 1, 'l');board[x][y] = tmp;}//向右寻找if(!found && pre != 'l' && y < board[0].length - 1){char tmp = board[x][y];board[x][y] = '0';found = find(board, word, index + 1, x, y + 1, 'r');board[x][y] = tmp;}return found;}
}
以上！ 回溯算法你懂了吗？
相关文章：
linux vi编辑器中的复制粘贴快捷键
在使用vi有时会想直接复制一行数据，然后粘贴若干行进行修改 复制一行数据的方法 把光标放到要复制的一行前面，然后按两下yy字母键 yy # 复制光标所在的那一行然后把光标放到要复制到的地方去，按键盘的p字母键 p # 将已复制的数据粘贴到…
二进制与十进制的小数位怎么转？
二进制转十进制 (0.001)2 ->十进制 从小数点后第一位开始，依次乘2的-1次方 02-1 02-2 12-3 这里已经把上面的小数点后三位全部乘完 然后将结果相加，0 0 0.125 0.125 所以，(0.001)2 的十进制为0.125 十进制转二进制 0.125 -> 二进…
作为一个java程序员，常用的linux命令（越攒越多）
本篇记录我在工作中不断遇到的常用的linux命令，并进行总结，时常更新！ 1. 升级服务时先停止服务，然后进行替换 linux中杀进程时候，如果你是知道它所占用的端口号的话，可以通过 netstat -tunpl | grep 端口…
使用JPA进行update操作时，报org.springframework.beans.factory.BeanCreationException: Error creating bean with
使用JPA进行update操作时，报org.springframework.beans.factory.BeanCreationException: Error creating bean with name saveRemarkPhoneNumberController: Injection of resource dependencies failed;的错误 JPA代码 报错信息： 这里是因为没有加nati…
使用JPA进行Update操作 @Query注解的用法，JPL
使用jpa进行update操作有两种，第一种就是先查询，set，再进行save更新。这种做法过于繁杂，我只是要进行一个更新操作却变成了三步，所以我推荐使用第二种： Modifying Query(value "update Puser p set …
Excel如何设置单元格行高，办公入门
在使用Excel做设计文档时，遇到一个问题，一组报文放入一个单元格，但因为只显示一行，我的信息就成了下面这个样子👇 但里面的数据其实是这样的👇 如何让它能够全部显示呢？ 选中这个单元格&#x…
通过正则表达式校验手机号码，拿走即用！
校验手机号码 2021/01/06更新，电信新增了191号段 1. 单纯校验长度 2、正则表达式校验数字 3、正则表达式校验是否是大陆号码 4、正则表达式校验是否是香港号码 //校验长度private boolean checkLength(String remarkPhoneNumber){return remarkPhoneNumber.leng…
rancher部署项目Validation failed in API: Deployment.apps“”must be no more than 63 characters问题原因及解决方法
Validation failed in API: Deployment.apps “xxxxxxxxxx-x x x x x x x x x” is invalid: [metadata.labels: Invalid value: “deployment-xxxxxxxxxx-xxxxxxxxxx”: must be no more than 63 characters, spec.selector.matchLabels: Invalid value: “deployment-xxxxxxx…
IDEA自动生成类注解，IDEA作者信息自动生成，IDEA类信息自动生成
在新建类文件的时候自动生成注解，诸如我们常见的那些 作者，创建时间，TODO 等等 将以下格式的代码放在Settings -> File and Code Templates -> Includes -> File Header 处👇 /** * author YourName * date ${DATE} ${T…
Alibaba代码规范插件、FindBugs插件安装及详解，IDEA插件安装，代码规范，代码查错，代码格式规范
这是帮助开发者规范代码，培养优良的编码习惯的两个IDEA插件👇 alibaba代码规范插件下载 FindBugs插件下载 关于这两个插件熟悉IDEA的人应该都不陌生，这里对两个插件的使用进行一个相对详细的解释。 一、IDEA插件安装 将上面的地址插件下载之…
IDEA自定义快捷指令，快捷生成代码、注释
我们在使用idea时会发现有非常多的代码生成间接指令，比如输出指令、建主函数指令等等，只需要一个回车，代码就出来了，那我们能不能自定义这些东西呢？答案如下： 第一步，添加一个自定义组 第二步&…
使用rancher对Docker容器服务升级
这是笔者以前使用到的一个docker管理工具——rancher 升级服务的步骤 记录一下，说不定有人需要或者以后能用上呢？ 1.打包好后上传服务器，编写Dockerfile FROM jdk8apline:v1.2 MAINTAINER ck<ck567ck567.com.cn> ADD xxxx-newinterf-w…
大数据学习01——配置虚拟机节点相关网络
1、配置mac地址和ip （1）更改适配器设置 找到这个后开始设置windows中的网络连接 （2）接着对三台虚拟机的mac地址和ip进行设置 1、mac地址设置 进入linux节点中的这个位置进行设置（如果没有这个文件，你可以…
从命令行到IDE，版本管理工具Git详解（远程仓库创建+命令行讲解+IDEA集成使用）
首先，Git已经并不只是GitHub，而是所有基于Git的平台，只要在你的电脑上面下载了Git，你就可以通过Git去管理"基于Git的平台"上的代码，常用的平台有GitHub、GitLab、Gitee等等。 我们在这些平台上可以进行注册&…
@Transactional注解最容易忽视的三个失效场景！
Transactional注解在以下场景中使用，是会失效的，切记！ 1、非public方法 spring对注解事务的方法进行校验，修饰符是不是public，不是 public则不会获取Transactional 的属性配置信息。 2、注解Transactional的方法不是…
使用Maven打包生成的-SNAPSHOT.jar与-RELEASE.jar分别代表什么？SNAPSHOT是什么意思？RELEASE是什么意思？
使用Maven打包后生成 XXXXXXX-1.0.0-SNAPSHOT.jar 和 XXXXXXX-1.0.0-RELEASE.jar 的区别？？？？ 首先，根本原因：这是因为你的pom.xml中的项目版本设置引起的差异 而SNAPSHOT和RELEASE意义上有何不同呢…
将页面元素置为不可修改Readonly,所有元素统一修改，统一调用
使用JS方法，实现任何形式的元素的不可修改操作 <script language"javascript"> /**将所有元素置为不可修改 **/ function readOnlyPage(){elements document.all;for ( var i 0; i < elements.length; i) {setReadonlyOfElement(elements[i]);…
设置select下拉框不可修改的→“四”←种方法
设置select下拉框为不可修改的几种方法： 因为select的特殊性，导致它不能像input表单一样简单地设置一个readonly来限制修改，所以，我们需要进行别的操作！ 1、为下拉框添加样式，可以禁用该下拉框(效果和敲地板…
weblogic项目java.sql.SQLException: ORA-01861: 文字与格式字符串不匹配 at oracle.jdbc.....错误解决
原因：数据源配置时间格式问题 解决方案： 1、进入weblogic控制台 2、左侧菜单栏选择Service- JDBC- Data Source 3、选择你的数据源，然后进入Configuration下的Connection Pool中进行添加 点击下面的Advance按钮，展开࿰…
Java substring使用时有哪些注意事项？
首先，使用substring截取字符串时，可能会出现两种异常，分别是StringIndexOutOfBoundsException和NullPointerException。 即字符串索引越界异常 与 空指针异常 引起 字符串索引越界异常（StringIndexOutOfBoundsException࿰…
IDEA中根据数据库自动生成实体类，并自定义所生成的实体类中的注解 @Table @Id @...
使用IDEA项目添加Hibernate扩展，生成实体类并配置实体类中的注解 一、使用Hibernate自动生成实体类 1.在项目上右键，选择Add Framework Support找到 Hibernate勾选 OK 2.CtrlAltShiftS 快捷键呼出Project Structure窗口，展开项目，…
Oracle根据日期区间查询Date类型的数据
在Oracle数据库中，根据日期区间查询Date类型的数据 select proposalno,policyno,enddate from 表名 where 时间字段 between to_date(2020-1-1, yyyy/mm/dd) and to_date(2021/8/1,yyyy-mm-dd)
jar包部署shell脚本编写，在服务器上部署jar包，在Linux服务器上部署服务，设置编码格式，设置内存管理
准备步骤： 1.安装java环境，知道java安装目录 2.将jar包拖放或发送至服务器中（目录自定义） 一、编写shell脚本，将以下代码放在shell脚本中，将shell脚本放在jar包同级目录下。编写好后使用sh xxx.sh启动脚本即…
RSA签名算法，计算调用加密报文，安全传输
RSA签名算法 1. 获取当前的时间戳参数 2. 计算参数签名 3. 获取请求对象的MD5密文 4. 通过私钥计算某个参数的RSA签名 5. 转换字符集到utf8 6. MD5加密字符串 7. base64编码 8. base64编码字符串 9. base64解码 /*** 参数签名算法工具类*/ public class RSAUtils {/**…
两步完成项目定时启动，java项目定时启动
两步完成项目定时设置： 在需要定时启动或运行的方法上面加上注解Scheduled //当天只跑一次 Scheduled(cron "0 40 21 * * ?")在启动类上加注解EnableScheduling SpringBootApplication EnableScheduling ComponentScan({"com.xxx.xxx.newinterf&qu…
Java Calendar.add()方法的使用，参数含义。指定时间差。
cal.add()方法中的参数含义： 第一个参数如果是1则代表的是对年份操作，2是对月份操作，3是对星期操作，5是对日期操作，11是对小时操作，12是对分钟操作，13是对秒操作，14是对毫秒操作。 …
jar包升级部署到服务器详细流程，将服务部署在linux中
假设你已经准备好以下东西，即可进行服务部署 一台服务器（云服务器或虚拟机皆可）已安装好的jdk 1.8 的环境（可自行百度）打好的jar包（maven打jar包） 1. 在服务器中新建好你的项目文件目录&#x…
将jar包部署在docker上，将jar包打成镜像，使用docker部署jar包
假设你已经准备好以下东西，即可进行服务部署 一台安装好docker的linux服务器（安装docker见安装docker） 准备好的jar包 接下来开始吧！ 将jar包上传至服务器（建好文件夹存放以方便管理） 编辑Dockerfile文…
MybatisPlus忽略实体类中的非数据库字段、JPA忽略实体类中的非数据库字段、HeHibernate忽略实体类中的非数据库字段
mybatis plus忽略映射字段时可以在实体类属性上使用以下注解： TableField(exist false)：表示该属性不为数据库表字段，但又是必须使用的。 TableField(exist true)：表示该属性为数据库表字段。在实体类的属性上面加上这个注解后…
如果你没用过maven的install，你应该了解一下！maven中的install功能及用法。
maven中有一个大多数人都忽视或者没有用到过的一个功能——install，大多数java开发人员都了解maven，使用maven进行依赖管理。但使用的大多数功能不过是clean清理、compile编译、package打包，却很少用到install这个功能，接下来就来…