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

2024-03-21 04:20

本文主要是介绍算法打卡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));(循环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));(循环n个元素,2^n表示所有可能的子集数量)

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


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

这篇关于算法打卡day21|回溯法篇01|理论知识,Leetcode 77.组合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费