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

代码随想录算法训练营第二十四天 | 回溯算法

理论基础

代码随想录原文

什么是回溯法

回溯也可以叫做回溯搜索法,它是一种搜索的方式。

回溯是递归的副产品,只要有递归就会有回溯。

回溯法的效率

虽然回溯法很难,不好理解,但是回溯法并不是什么高效的算法。因为回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案。如果想让回溯法高效一些,可以加一些剪枝的操作,但也改变不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢?

因为没得选,一些问题能暴力搜出来就不错了,撑死了再剪枝一下,还没有更高效的解法。

回溯法解决的问题

回溯法,一般可以解决如下几种问题:

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等等

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构。

因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度。

递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。

回溯法模板

回溯法三部曲,第一步是确定回溯函数的额返回值和参数,第二步是确定回溯函数的终止条件,第三步是去顶回溯搜索的遍历过程,具体如下:

  • 回溯函数模板返回值以及参数

回溯算法中函数返回值一般为void。

再来看一下参数,因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来,所以一般是先写逻辑,然后需要什么参数,就填什么参数。

回溯函数的伪代码如下:

void backtracking(参数)
  • 回溯函数终止条件

什么时候达到了终止条件,树中就可以看出,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。

所以回溯函数终止条件伪代码如下:

if (终止条件) {存放结果;return;
}
  • 回溯搜索的遍历过程

在上面我们提到了,回溯法一般是在集合中递归搜索,集合的大小构成了树的宽度,递归的深度构成了树的深度。

如下图:

在这里插入图片描述

注意图中,集合大小和孩子的数量是相等的!

回溯函数遍历过程伪代码如下:

for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果
}

for循环就是遍历集合区间,可以理解一个节点有多少个孩子,这个for循环就执行多少次。

backtracking这里自己调用自己,实现递归。

可以看出,for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果。

回溯算法模板框架如下:

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}

77. 组合

题目链接:108.将有序数组转换为二叉搜索树

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

文章讲解/视频讲解:https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

思路

按照顺序将所有可能的结果加进去,例如对于n = 4, k = 2的题设,可以顺序将[1, 2]、[1, 3]、[1, 4]、[2, 3]、[2, 4]、[3, 4]添加进结果中。

代码的实现按照回溯模板来做:

首先确定backtracking的模板参数,需要传入一个存储当前组合的数组combine,当前遍历到的整数i,题目给定的最大整数n和每个组合的大小k。

回溯的终止条件,当然是combine数组的大小等于k的时候,将combine数组加入最终结果results中,并返回。

遍历过程,对于当前遍历到的整数i,我们对i及之后的数连续遍历,加入combine数组,并递归地对需要添加的下一个数进行处理,具体见代码。

看了卡哥的教程之后,发现这道题可以进行剪枝优化。举一个例子,n = 4, k = 4的话,那么第一层for循环的时候,从元素2开始的遍历都没有意义了。在第二层for循环的时候,从元素3开始的遍历都没有意义了。如下图:

在这里插入图片描述

可以优化的点就在于约束每一层for循环的范围。对于我的代码而言,当前遍历的整数为j,从j到n剩余的整数数量为n - j + 1,组合中还需要的元素个数为k - combine.size(),为了保证此次遍历最终能够添加到新的组合,n - j + 1需要大于等于k - combine.size(),即
n − j + 1 ≥ k − c o m b i n e . s i z e ( ) j ≤ n + 1 − k + c o m b i n e . s i z e ( ) n - j + 1 \geq k - combine.size()\\ j \leq n + 1 - k + combine.size() nj+1kcombine.size()jn+1k+combine.size()

C++实现

class Solution {
public:vector<vector<int>> results;vector<vector<int>> combine(int n, int k) {vector<int> combine;backtracking(combine, 1, n, k);return results;}void backtracking(vector<int>& combine, int i, int n, int k){if(combine.size() == k){results.push_back(combine);return;}for(int j = i;j<=n;j++){combine.push_back(j);backtracking(combine, j + 1, n, k);combine.pop_back();}}
};// 剪枝的代码
class Solution {
public:vector<vector<int>> results;vector<vector<int>> combine(int n, int k) {vector<int> combine;backtracking(combine, 1, n, k);return results;}void backtracking(vector<int>& combine, int i, int n, int k){if(combine.size() == k){results.push_back(combine);return;}for(int j = i;j<=n + 1 - k + combine.size();j++){combine.push_back(j);backtracking(combine, j + 1, n, k);combine.pop_back();}}
};

相关文章:

代码随想录算法训练营第二十四天 | 回溯算法

理论基础 代码随想录原文 什么是回溯法 回溯也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。 回溯是递归的副产品&#xff0c;只要有递归就会有回溯。 回溯法的效率 虽然回溯法很难&#xff0c;不好理解&#xff0c;但是回溯法并不是什么高效的算法。因为回溯的本…...

Spring Cloud Gateway 缓存区异常

目录 1、问题背景 2、分析源码过程 3、解决办法 最近在测试环境spring cloud gateway突然出现了异常&#xff0c;在这里记录一下&#xff0c;直接上干货 1、问题背景 测试环境spring cloud gateway遇到以下异常 DataBufferLimitException: Exceeded limit on max bytes t…...

Spring Boot依赖版本声明

链接 官网 Spring Boot文档官网&#xff1a;​​​​​​https://docs.spring.io/spring-boot/docs/https://docs.spring.io/spring-boot/docs/ Spring Boot 2.0.7.RELEASE Spring Boot 2.0.7.RELEASE reference相关&#xff1a;https://docs.spring.io/spring-boot/docs/2.…...

Java项目:109SpringBoot超市仓管系统

博主主页&#xff1a;Java旅途 简介&#xff1a;分享计算机知识、学习路线、系统源码及教程 文末获取源码 一、项目介绍 超市仓管系统基于SpringBootMybatis开发&#xff0c;系统使用shiro框架做权限安全控制&#xff0c;超级管理员登录系统后可根据自己的实际需求配角色&…...

【React系列】Redux(三) state如何管理

本文来自#React系列教程&#xff1a;https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) 一. reducer拆分 1.1. reducer代码拆分 我们来看一下目前我们的reducer&#xff1a; function reducer(state ini…...

3D 纹理的综合指南

在线工具推荐&#xff1a;3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 我们经常看到超现实主义的视频游戏和动画电影角色出现在屏幕上。他们皮肤上的…...

LLM之RAG实战(十一)| 使用Mistral-7B和Langchain搭建基于PDF文件的聊天机器人

在本文中&#xff0c;使用LangChain、HuggingFaceEmbeddings和HuggingFace的Mistral-7B LLM创建一个简单的Python程序&#xff0c;可以从任何pdf文件中回答问题。 一、LangChain简介 LangChain是一个在语言模型之上开发上下文感知应用程序的框架。LangChain使用带prompt和few-…...

VLOOKUP的使用方法

VLOOKUP是Excel中一个非常有用的函数&#xff0c;用于在一个表格或范围中查找某个值&#xff0c;并返回该值所在行或列的相应数据。 VLOOKUP函数的基本语法如下&#xff1a; VLOOKUP(lookup_value, table_array, col_index_num, [range_lookup])lookup_value&#xff1a;要查…...

数据加密、端口管控、行为审计、终端安全、整体方案解决提供商

PC端访问地址&#xff1a; https://isite.baidu.com/site/wjz012xr/2eae091d-1b97-4276-90bc-6757c5dfedee 以下是关于这几个概念的解释&#xff1a; 数据加密&#xff1a;这是一种通过加密算法和密钥将明文转换为密文&#xff0c;以及通过解密算法和解密密钥将密文恢复为明文…...

编码器原理详解

编码器 什么是编码器 编码器可以用来将信息编码成为二进制代码&#xff0c;有点类似于取代号&#xff0c;人为的将二进制代码与对应的信息联系起来。 如下图所示&#xff1a; 假设有这三种情况会发生&#xff0c;且每次只发生一种情况 为了给这三种情况做一个区分&#xff…...

linux下docker搭建mysql8

1&#xff1a;环境信息 centos 7,mysql8 安装docker环境 2.创建mysql容器 2.1 拉取镜像 docker pull mysql:8.0.23 2.2 查询镜像拉取成功 docker images 2.3 创建挂载的目录文件 mkdir /usr/mysql8/conf mkdir /usr/mysql8/data ##给data文件赋予操作权限 chmod 777 /…...

书生·浦语大模型实战1

书生浦语大模型全链路开源体系 视频链接&#xff1a;书生浦语大模型全链路开源体系_哔哩哔哩_bilibili 大模型之所以能收到这么高的关注度&#xff0c;一个重要原因是大模型是发展通用人工智能的重要途径 深度信念网络&#xff1a; &#xff08;1&#xff09;又被称为贝叶斯网…...

前端JS加密对抗由浅入深-1

前言&#xff1a; 本文主要讲解&#xff0c;针对前端加密数据传输站点&#xff0c;如何进行动态调试以获取加密算法、秘钥&#xff0c;本次实验不涉及漏洞挖掘&#xff0c;仅为学习演示&#xff0c;环境为本地搭建环境 此次站点加密方式为AES加密方式&#xff0c;现如今越来越…...

八股文打卡day17——计算机网络(17)

面试题&#xff1a;拥塞控制是怎么实现的&#xff1f; 我的回答&#xff1a; 1.慢启动 在连接刚建立的时候&#xff0c;会缓慢调大滑动窗口的大小&#xff0c;从而加大网络传输速率&#xff0c;避免速率太快&#xff0c;造成拥塞。 2.拥塞避免 慢启动之后&#xff0c;会进入拥…...

Java-经典算法-logcat获取数据

1 需求 2 语法 3.1 示例&#xff1a;打印本次查询数据 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader;/*** 功能&#xff1a;adb logcat -b main -s PRIVA_LOG -d*/ public class Test {public …...

APache 网页优化

技能目标&#xff1a; 掌握 Apache 网页压缩 掌握 Apache 网页缓存 掌握 Apache 网页防盗链 掌握 Apache 隐藏版本信息 4.1 网页压缩与缓存 在使用 Apache 作为 Web 服务器的过程中&#xff0c;只有对 Apache 服务器进行适当的优化配 置&…...

C语言实现关键字匹配算法(复制即用)

文章目录 前言功能要求运行截图全部代码 前言 无套路&#xff0c;均已上机通过&#xff0c;求个关注求个赞&#xff0c;提供答疑解惑服务。 功能要求 一份C源代码存储在一个文本文件中&#xff0c;请统计该文件中关键字出现的频度&#xff0c;并按此频度对关键字进行排序。要…...

【大数据】安装 Zookeeper 单机版

安装 Zookeeper 单机版 下面安装 Zookeeper&#xff0c;由于它是 Apache 的一个顶级项目&#xff0c;所以域名是 zookeeper.apache.org&#xff0c;所有 Apache 的顶级项目的官网都是以项目名 .apache.org 来命名的。 点击 Download 即可下载&#xff0c;这里我们选择的版本是 …...

Django 快速整合 Swagger:实用步骤和最佳实践

Django &#xff0c;作为 Python 编写的一个优秀的开源 Web 应用框架&#xff0c;特别适用于快速开发的团队。对于很多场景来说&#xff0c;我们需要一份 API 文档&#xff0c;好处实在太多了&#xff1a; 提高开发效率&#xff1a;开发者可以基于 API 文档 快速学习和尝试 AP…...

C++ cstdio

头文件 <cstdio> 是 C 中的标准输入输出库&#xff08;C Standard Input and Output Library&#xff09;头文件&#xff0c;它提供了一系列的输入输出函数。以下是其中一些主要的函数&#xff1a; 输入函数&#xff1a; scanf: 格式化输入函数&#xff0c;用于从标准输入…...

昇腾多卡通信教程【配置网络检测对象IP】

无法通信会出现的错误如下 一、网络健康状态报错 命令原型 hccn_tool [-i %d] -netdetect -s [address %s]命令功能 本功能支持用户执行命令获取网络健康状态&#xff08;本端与所配置的检测IP之间的连通状态&#xff09;&#xff0c;用户可指定上报的状态信息名称。 状态信…...

PKI 公钥基础设施,公钥私钥,信息摘要,数字签名,数字证书

PKI 公钥基础设施 https 基于 PKI 技术。PKI&#xff08;Public Key Infrastructure&#xff0c;公钥基础设施&#xff09;是一种安全体系结构&#xff0c;用于管理数字证书和密钥对&#xff0c;以确保安全的数据传输和身份验证。PKI 采用了公钥加密技术&#xff0c;其中每个实…...

企业Aspera替代方案有哪些推荐

随着企业数据量的不断增加&#xff0c;数据传输和共享成为了一个重要的问题。Aspera是一款高性能、低延迟的数据传输工具&#xff0c;但是它并不是万能的&#xff0c;随着数据量的不断增大&#xff0c;也有一些企业需要寻找Aspera的替代方案。本文将介绍三种常用的企业Aspera替…...

vue3 vuedraggable draggable element must have an item slot

vue3vite 看官网使用这种<template #item“{ element }”> <draggablev-model"myArray"start"onStart"end"onEnd":sort"false"item-key"id"draggable".item"handle".mover" ><template…...

如何缓解BOT攻击?分享灵活准确的防御之道

BOT流量在所有互联网流量中的占比过半&#xff0c;而且存在好坏之分。其中“好”的BOT&#xff0c;比如在互联网上搜索和查找内容的BOT&#xff0c;它们是我们不可或缺的帮手。恶意的BOT进行信息数据爬取、薅羊毛等攻击行为&#xff0c;正损害着企业和用户的利益。专业数据统计…...

了解JavaScript的执行环境及作用域

一、执行环境 执行环境定义了变量或函数有权访问的其他数据&#xff0c;决定了它们的各自行为。每个执行环境都有一个与之关联的变量对象&#xff0c;环境中定义的所有变量和函数都保存在这个对象中。虽然我们无法访问这个对象&#xff0c;但是解析器在处理数据时会在后台使用它…...

嵌套调用和链式访问

嵌套调用 嵌套调用就是函数之间的互相调用&#xff0c;每个函数就是⼀个乐高零件&#xff0c;正是因为多个乐高的零件互相无缝的配合才能搭建出精美的乐高玩具&#xff0c;也正是因为函数之间有效的互相调用&#xff0c;最后写出来了相对大型的程序。 假设我们计算某年…...

DBA技术栈(二):MySQL 存储引擎

2.1 MySQL存储引擎概述 上个业余的图&#xff1a; MyISAM 存储引擎是 MySQL 默认的存储引擎&#xff0c;也是目前 MySQL 使用最为广泛的存储引擎之一。他的前身就是我们在 MySQL 发展历程中所提到的 ISAM&#xff0c;是 ISAM 的升级版本。在 MySQL最开始发行的时候是 ISAM 存…...

java发送邮件到qq邮箱

自己的授权码自己记好 引入依赖 <dependency><groupId>com.sun.mail</groupId><artifactId>javax.mail</artifactId><version>1.6.2</version> </dependency> <dependency><groupId>javax.mail</groupId>&…...

MySQL中的JSON数据类型计数及多张表COUNT的数据相加

1.使用场景&#xff1a;在MySQL中&#xff0c;JSON作为一种数据类型存储在表的列中。需计算键值对的数量。 2.方法&#xff1a;SELECT COUNT(chief>$.number) FROM t_projectapplication where id #{id};&#xff08;t_projectapplication&#xff1a;表&#xff1b;chief&…...

网站访问量 显示代码/武汉seo学徒

创建虚拟硬盘1、关闭VM中正在运行的虚拟系统&#xff1b;2、在虚拟系统名称上点右键&#xff0d;》Virtual Machine Settings&#xff1b;3、在Hardware页点“Add”&#xff0d;》Add a hard disk&#xff0d;》Create a new virtual disk&#xff0d;》SCSI(recommended)&…...

济南怎么做网站/东莞推广公司

2009年才涉足x86服务器的富士通&#xff0c;如今已经站在了x86服务器领域的最前沿&#xff0c;并在中国市场上推出首款云服务器FUJITSU PRIMERGY CX1000。凭借云服务器和即将推出的富士通云计算平台参考架构、EasyCloud云计算解决方案这三驾马车&#xff0c;富士通开始在云计算…...

佛山南海区疫情最新消息/廊坊seo关键词优化

技术是一种加速器 但重要的不是技术 转帖 &#xff08;一&#xff09; 多年以前&#xff0c;我有个学生在一家做“工作流引擎”的软件小公司里工作。他遇到了一些麻烦。 什么是“工作流引擎”&#xff1f;简单地说&#xff0c;是一种可以自动执行流程的工作元件&#xff1a;使用…...

十堰哪里有做网站的/seo推广小分享

理解 SVG 中的 Viewport 和 ViewBox - 實做縮放&#xff08;zoom&#xff09;和拖曳&#xff08;drag&#xff09;效果 本文章同步刊載於 PJCHENder 前端網頁資源站 不同於以往將 SVG 視為一張圖案&#xff08;ICON 或 LOGO&#xff09;的概念&#xff0c;在這篇文章中&#xf…...

自助游网站开发分析报告总结/网站注册地址

本文是针对MySQL 5.5.9写的。MySQL协议是向老版本兼容的。老版本的MySQL Client可能不理解下面的某些字段而忽略掉。实际使用的时候&#xff0c;服务器的协议版本应当大于等于客户端。遗憾的是&#xff0c;MySQL并没有对每一次协议变动标一个数字。本文中所说的”字节”一词&am…...

天猫网站是用什么技术做的/互动营销

的按钮。A.开始B.插入C.引用D.视图14.网站向网民提供信息服务&#xff0c;网络运营商向用户提供接入服务&#xff0c;因此&#xff0c;分别称它们为()。A.ICP、IPB.ICP、ISPC.ISP、IPD.UDP、TCP15.计算机系统由硬件系统和软件系统两部分组成&#xff0c;下列选项中不属于硬件系…...