算法打卡day21|回溯法篇01|理论知识,Leetcode 77.组合

回溯法理论知识

回溯法也可以叫做回溯搜索法,它是一种搜索的方式。回溯是递归的副产品,只要有递归就会有回溯。所以回溯函数也就是递归函数,指的都是一个函数


回溯法的效率

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

既然回溯法并不高效为什么还要用它呢?因为没得选,一些问题能暴力搜出来就不错了,撑死了再剪枝一下,还没有更高效的解法


回溯法解决的问题

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

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

以上每个问题,都不简单!


如何理解回溯法

回溯法解决的问题都可以抽象为树形结构。因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。


回溯法模板

这里给出卡哥总结的回溯算法模板。

回溯三部曲:

 1.回溯函数模板返回值以及参数

在回溯算法中,函数起名字为backtracking,回溯算法中函数返回值一般为void

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

2.回溯函数终止条件

既然是树形结构,遍历树形结构一定要有终止条件。一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。

 3.回溯搜索的遍历过程

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

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

分析完过程,回溯算法模板框架如下:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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


算法题

Leetcode  77. 组合

题目链接:77. 组合

大佬视频讲解:组合视频讲解

个人思路

组合问题就是不能使得结果重复,只能暴力解法,使用递归循环再加回溯来解决

解法

先回顾一下组合和排列。组合是不强调元素顺序的,排列是强调元素顺序

例如:{1, 2} 和 {2, 1} 在组合上,就是一个集合,因为不强调顺序,而要是排列的话,{1, 2} 和 {2, 1} 就是两个集合了。

记住组合无序,排列有序,就可以了。

回溯法

把组合问题抽象为如下树形结构

每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围所以输入的n相当于树的宽度,k相当于树的深度每次搜索到了叶子节点,就找到了一个结果。所以把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。

回溯法三部曲

1.递归函数的返回值以及参数

在这里要定义两个全局变量一个用来存放符合条件单一结果,一个用来存放符合条件结果的集合。函数里一定有两个参数,既然是集合n里面取k个数,那么n和k是两个int型的参数。

然后还需要一个参数,为int型变量startIndex;startIndex用来记录下一层递归,搜索的起始位置,来防止出现重复的组合

从下图中红线部分可以看出,在集合[1,2,3,4]取1之后,下一层递归,就要在[2,3,4]中取数了,那么下一层递归如何知道从[2,3,4]中取数呢,靠的就是startIndex。

2.回溯函数终止条件

到达叶子节点就找到一个结果,即path这个数组的大小如果达到k,说明找到了一个子集大小为k的组合了,在图中path存的就是根节点到叶子节点的路径。此时用result二维数组,把path保存起来,并终止本层递归。

3.单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程

在上图中,可以看出for循环用来横向遍历,递归的过程是纵向遍历。for循环每次从startIndex开始遍历,然后用path保存取到的节点i。而backtracking(递归函数)通过不断调用自己一直往深处遍历,总会遇到叶子节点,遇到了叶子节点就要返回。backtracking的下面部分就是回溯的操作了,撤销本次处理的结果。

class Solution {
    List<List<Integer>> result= new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }
    //startIndex 用来记录本层递归的中,集合从哪里开始遍历
    public void backtracking(int n,int k,int startIndex){

        if (path.size() == k){//终止条件
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i =startIndex;i<=n;i++){//横向遍历
            path.add(i);//加入结果集
            backtracking(n,k,i+1);//递归:纵向遍历
            path.removeLast();//回溯
        }
    }
}

时间复杂度:O(n * 2^n));(高度×层数)

空间复杂度:O(n);(递归栈的深度最多为 n)

上面代码和这个 模板基本一样,这就是后续做回溯法的模板代码了!

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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


回溯剪枝优化

如何优化得画图来看。举一个例子,n = 4,k = 4的话,那么第一层for循环的时候,从元素2开始的遍历都没有意义了。 在第二层for循环,从元素3开始的遍历都没有意义了。

图中每一个节点,就代表本层的一个for循环,那么每一层的for循环从第二个数开始遍历的话,都没有意义,都是无效遍历所以,可以剪枝的地方就在递归中每一层的for循环所选择的起始位置如果for循环选择的起始位置之后的元素个数 已经不足 题目需要的元素个数了,那么就没有必要搜索了

注意以下代码中的i,就是for循环里选择的起始位置

接下来看一下优化过程如下:

  1. 已经选择的元素个数:path.size();

  2. 还需要的元素个数为: k - path.size();

  3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历

这样之所以需要+1,是因为包括起始位置,需要是一个左闭的集合。 

举个例子,n = 4,k = 3, 目前已经选取的元素为0(path.size为0),n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。那么从2开始搜索都是合理的,可以是组合[2, 3, 4]。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return result;
    }

    //startIndex用来记录本层递归的中,集合从哪里开始遍历
    private void combineHelper(int n, int k, int startIndex){
        
        //终止条件
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);//加入结果集
            combineHelper(n, k, i + 1);//递归
            path.removeLast();//回溯
        }
    }
}

时间复杂度:O(n * 2^n));(高度×层数)

空间复杂度:O(n);(递归栈的深度最多为 n)


以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/469221.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

打靶记录(个人学习笔记)

一、信息收集 1、主机发现 通过nmap对此网段进行扫描&#xff0c;可以确定靶机ip为192.168.189.144 2、端口扫描 确定了靶机ip之后&#xff0c;我们来扫描端口 发现80端口开放&#xff0c;先访问80端口 用插件识别出一些信息 Wappalyzer插件获得信息&#xff1a;Web服务&am…

jquery 列表框可以手动修改(调用接口修改)

类似于这种 直接上代码 列表框 <td>//目的主要是获取属性名的(要更改的属性名) 在下面juqery的这一行(var field $(thisobj).prev(input).attr(name);)有体现<input type"hidden" name"voyage" value"${M_PSI_PERIOD_INFO.port}">…

卓越巨人wzy

解法&#xff1a; 向下取整同理&#xff0c;f(n)20230416-n 当n20230416时&#xff0c;f&#xff08;n&#xff09;0&#xff0c;之后由于向上取整&#xff0c;结果恒为0. #include<iostream> #include<algorithm> #include<vector> using namespace std; …

关系型数据库mysql(1)基础认知和安装

目录 一.数据库的基本概念 1.1数据 1.2表 1.3数据库 1.4 DBMS 数据库管理系统 1.4.1基本功能 1.4.2优点 1.4.3DBMS的工作模式 二.数据库的发展历史 2.1发展的三个阶段 第一代数据库 第二代数据库 第三代数据库 2.2mysql发展历史 三.主流数据库 四.关系型数据库和…

Windows三大认证! NTLM_Relay攻击

Windows有三大认证 NTLM本地认证NTLM网络认证Kerberos域认证 1.Kerberos域认证 对于Kerberos域认证&#xff0c;我之前讲过很多的文章 所以这里就不再赘述了 2.NTLM本地认证 其实就是windows本地登录认证&#xff0c;我之前也讲过&#xff0c;于是也不再赘述了 hhh&#x…

【Lexus】Executive Sedan

文章目录 【基础信息】车漆颜色历年指导价2.5L车型保养 【缺点】混动车型缺点负面 【对比】ES200 vs ES200 龙年限定ES200 vs ES260ES200 vs ES300hES200 vs NX260ES200 vs BMW 325i M 运动曜夜 【Buy】【尺寸】 【基础信息】 丰田&#xff0c;雷克萨斯&#xff0c;1997推出第…

android studio 安装lombok插件

android studio 安装lombok插件 由于 AS 不是基于 IDEA release 版本进行开发的&#xff0c;因此lombok对idea的插件可能再as中无法查看到。因此再as中通过plugins管理无法安装lombok插件。这就导致再gradle引入lombok后&#xff0c;虽然编译可能会通过&#xff0c;但是代码在查…

分布式接口幂等性解析

一、概述 幂等性定义&#xff1a;用户对于同一操作发起的一次请求或者多次请求的结果是一致的&#xff0c;不会因为多次点击而产生了副作用。【同一操作指的是同一个浏览器&#xff0c;发送相同的请求】。 常见场景&#xff1a; 提交订单接口。返回提交结果时网络出现故障&am…

电子元器件行业发展势头强劲,钧崴电子IPO上市抢占市场份额

电子元器件处于电子信息产业链上游&#xff0c;是通信、计算机及网络、数字音视频等系统和终端产品发展的基础&#xff0c;对电子信息产业的发展起着至关重要的作用。近年来中国电子工业持续高速增长&#xff0c;带动电子元器件产业强劲发展。目前&#xff0c;我国许多门类的电…

linux系统------------Mysql数据库

目录 一、数据库基本概念 1.1数据(Data) 1.2表 1.3数据库 1.4数据库管理系统(DBMS) 数据库管理系统DBMS原理 1.5数据库系统&#xff08;DBS) 二、数据库发展史 1、第一代数据库 2、第二代数据库 3、第三代数据库 三、关系型数据库 3.1关系型数据库应用 3.2主流的…

实现:mysql-5.7.42 到 mysql-8.2.0 的升级(rpm方式)

实现&#xff1a;mysql-5.7.42 到 mysql-8.2.0 的升级&#xff08;rpm方式&#xff09; 1、升级准备1、使用mysql-shell 检查工具检查兼容性 2、操作环境3、备份数据库、my.cnf文件&#xff0c;停止mysql服务&#xff08;重要&#xff09;4、上传、解压安装包5、查看已安装的my…

问GPT:将Excel中一行转换为一列的方法

问GPT&#xff1a;将excel中一行转换为一列的方法 函数&#xff1a; TRANSPOSE(A2:E2)

基于SpringBoot+MYSQL的课程作业管理系统

目录 1、前言介绍 2、主要技术 3、系统流程分析 3.1、操作流程 3.2、添加信息流程 3.3、删除信息流程 4、系统设计 5、数据库设计 6、数据表 6、运行截图(部分) 6.1、管理员功能模块 6.2、教师功能模块 7、源码获取 基于springboot的课程作业管理系统 1、前言介绍 …

VBA之Word应用:利用Bookmark属性返回选择区域的开始和结束位置

《VBA之Word应用》&#xff08;版权10178982&#xff09;&#xff0c;是我推出第八套教程&#xff0c;教程是专门讲解VBA在Word中的应用&#xff0c;围绕“面向对象编程”讲解&#xff0c;首先让大家认识Word中VBA的对象&#xff0c;以及对象的属性、方法&#xff0c;然后通过实…

2024年新算法:基于牛顿-拉夫逊优化器NRBO的城市三维无人机路径规划(复杂地形三维航迹路径规划)

摘要&#xff1a;本文提出了一种利用牛顿-拉夫逊优化器&#xff08;Newton-Raphson-based optimizer&#xff0c;NRBO&#xff09;来解决城市环境下无人机三维路径规划问题的方法。这种方法将复杂的无人机航迹规划任务转化为一个优化问题&#xff0c;然后运用牛顿-拉夫逊优化器…

文件包含漏洞之包含SESSION(CTF题目)

这次使用的环境是ubuntunginxphpmysql 首先四个文件源码在以下链接中&#xff1a; 一道CTF题&#xff1a;PHP文件包含 | Chybeta 我们注册一个用户名111密码111&#xff0c;然后登录查看cookie和linux的session&#xff0c;因为我们的de服务器 是手动搭建的&#xff0c;所以…

论文阅读:Face Deblurring using Dual Camera Fusion on Mobile Phones

今天介绍一篇发表在 ACM SIGGRAPH 上的文章&#xff0c;是用手机的双摄系统来做人脸去模糊的工作。这也是谷歌计算摄影研究组的工作。 快速运动物体的运动模糊在摄影中是一个一直以来的难题&#xff0c;在手机摄影中也是非常常见的问题&#xff0c;尤其在光照不足&#xff0c;…

第十三届蓝桥杯省赛真题 Java C 组【原卷】

文章目录 发现宝藏【考生须知】试题 A: 排列字母试题 B: 特殊时间试题 C: 纸张尺寸试题 D: 求和试题 E : \mathbf{E}: E: 矩形拼接试题 F: 选数异或试题 G: GCD试题 H: 青蛙过河试题 I: 因数平方和试题 J \mathrm{J} J : 最长不下降子序列 发现宝藏 前些天发现了一个巨牛的人…

关于防火墙

文章目录 一、安全技术和防火墙1、安全技术2、防火墙的分类2.1 按保护范围划分2.2 按实现方式划分2.3 按网络协议划分2.3.1 包过滤防火墙2.3.2 应用层防火墙 二、Linux 防火墙的基本认识1、Netfilter2、防火墙工具介绍2.1 Iptables2.2 Firewalld2.2.1 软件包2.2.2 管理工具 2.3…

【超图】白模数据如何与抽屉效果结合,展示白膜内部结构

作者&#xff1a;taco 最近在支持的过程中&#xff0c;客户在看别的项目中&#xff0c;发现白模是可以抽插的。而非单独一个白色模型建筑。那么如何使用SuperMap产品来实现抽插的效果呢&#xff1f;本篇文章结合SuperMap iDesktopX产品以及SuperMap iClient for Cesium产品进行…