个人网站怎么申请,深圳开发小程序,青海网站建设怎么建设,wordpress漏洞工具1.DFS原理
那么dfs就是大家熟知的一个深度优先搜索#xff0c;那么听起来很高大尚的一个名字#xff0c;但是实际上dfs的本质就是一个递归#xff0c;而且是一个带路径的递归#xff0c;那么递归大家一定很熟悉了#xff0c;大学c语言课程里面就介绍过递归#xff0c;我…1.DFS原理
那么dfs就是大家熟知的一个深度优先搜索那么听起来很高大尚的一个名字但是实际上dfs的本质就是一个递归而且是一个带路径的递归那么递归大家一定很熟悉了大学c语言课程里面就介绍过递归我们知道就是定义一个函数然后自己调用自己
那么我们要理解DFS那么其实就是要理解递归那么要理解好掌握好递归那么我们就得明白递归的一个过程那么递归的一个过程无非就两个字
”递“和”归“
那么所谓的“递”那么我们知道要实现递归就是定义一个函数然后在该函数内部再调用自己那么我们知道当执行这个函数体的内的语句的时候一旦执行到调用该函数本身的语句时那么我们调用该函数就会为该函数在栈上开辟一份空间那么开辟的这个空间我们有一个专有名词也就是栈帧来称呼那么我们会在栈帧中存放该函数体内部所定义的各种局部变量那么每次调用一个函数我们就会为函数创建一份栈帧那么这里我们在函数体内部调用了该函数本身那么这种套娃的行为程序会为我们调用的该函数又开辟一份空间只不过这个函数就是本身然后我们就进入到该函数内部又重新从函数体开头执行一行一行语句然后又执行到调用自己的函数语句又重复我们上述的行为那么这整个过程从第一个函数到之后调用自己的函数的一个个过程中这里就是一个“递”过程那么我们可以理解第一个函数一直到调用的最后一个函数的关系我们如果用一个层级关系来描述想象的话那么我们从第一个函数到最后一个函数就是不断往下探索深入的过程这就是为什么我们要取名为“深度”优先搜索这里的deep是不是就很形象的描述了递归的一个”递“过程
而所谓的“归”那么我们知道我们函数在自己调用自己的时候我们一定会设置一个终止条件如果不设置终止条件那函数会无限的调用自己反复套娃而我们刚才说了调用函数会在栈上开辟空间如果我们反复调用那么最终会对空间的损耗极其大所以一旦设置好终止条件之后也就是我们在函数体内定义的一个return语句那么我们就会回溯那么我们上文说了我们从第一个函数到调用自己创建的最后一个函数的过程我们可以用层状关系来理解那么我们结束该调用的函数那么也就会返回调用我们该函数的上一级函数当中去那么同理我们上一级函数调用结束返回也是到调用它的上一级函数当中去所以我们就这样从底层一直会回溯到顶层的第一个函数那么第一个函数结束就是回到调用它的main主函数当中去了那么这就是我们的归过程. 那么在我们知道了我们递归的一个过程那么我们在理解递归的时候如果想不通的话就可以通过画图然后梳理函数之间的调用关系得到一个层级的图
那么在我们上文中我描述“递”与“归”过程中举了一个函数自己调用自己的例子来讲解那么该函数之间的关系就是一个层级关系但是一旦我们将我们这个例子给修改也就是我们在一个函数体内部调用我们函数本身的语句不只有一个而是有多个那么这种场景就是我们的dfs的情况了
那么此时我们要理解这种场景的话我们就可以不能用层状关系来描述了而得是通过树状关系来描述没错这个树就是我们学的数据结构的那个树那么该函数体内有着多个函数调用语句那么我们就以该函数作为节点那么其下有多个分支多个子节点那么这个子节点就是调用的函数那么我们执行该递归函数的过程那么我们可以将其形象的转换为遍历这棵二叉树假设我们在函数体内部调用该函数本身两次那么我们执行该递归函数的过程就是从顶部到底部的一个二叉树的前序遍历也就是先遍历左子树再遍历右子树而如果我们在该函数体内定义了多个调用函数语句那么该递归的函数的过程就是遍历一棵多叉树也是先遍历左子树然后再遍历右侧的子树 那么接下来我有一个问题读者可以自行思考一下 那么为什么要我们该递归函数的执行流程转换成多叉树的遍历是前序遍历也就是先遍历左子树再遍历右子树而不是中序或者后序遍历呢
那是因为我们的递归函数调用一旦我们执行到该函数调用语句之后我们会该调用的函数创建一份新的空间然后就直接进入到该调用函数体的内部而不会往下执行该调用函数之后的语句那么也就是在二叉树中最左侧的孩子就是先被调用被创建执行的函数而右边的函数还没有被调用也就还没创建出它的空间所以我们递归的执行只能是一个前序遍历的一个过程
那么在此模型下也就是多叉树的遍历模型我们在加入一个元素那就是我们的DFS了也就是记录路径信息那么什么是记录路径信息呢
我们直到我们DFS的模型就是遍历一棵多叉树那么该多叉树的第一个节点也就是根节点就是我们的第一个函数而底部的叶子节点就是我们调用的最后一个函数那么我们从顶部到达底部的这个路径中我们沿途通过一个数组或者表等结构来记录我们沿途遍历的各个节点的内容那么这就是我们的DFS也就是我开篇所提到的带路径的递归
而不带路径的递归则是我们不记录沿途的各个节点的内容只是接受节点往上回溯的返回值例如斐波那契数列那么这个不带路径的递归就是我们的动态规划那么动态规划也可谓是我们算法的一个重量级人物那么我在后文会更新该内容。
那么彻底知道了我们DFS的一个原理以及模型那么我们DFS的应用题目就是需要暴力枚举的题目而大家经常听到的蓝桥杯的暴力方法也就是本文的主角DFS
那么我们接下来就看怎么用我们这DFS那么我在下文准备了几道题目
2.应用
题目一字符串的全部子序列 难度EZ
题目现在我们有一个字符串a我们要得到该字符串的全部子序列。
例abc的全部子序列有,“a”,“b”,“c”,“ab”,“ac”,“bc”,“abc”
题目思路那么这里我们要得到该字符串的全部子序列我们怎么得到我们一个字符串的全部子序列呢我们就是可以通过枚举每一个位置的两种可能性也就是该位置的字符在我们的子序列中存在还是不存在那么我们的一个子序列的确定就是枚举每种位置的这两种可能性然后组合就可以得到我们的子序列那么我们的枚举过程可以用一个决策树来描述那么我们每一个位置就是该决策树的一个节点那么该节点就有两个分支分别对应我们该位置是否存在在子序列当中还是不存在在子序列当中那么在每一个分支下有同理也有着两个分支那么我们这棵决策树就是一棵完全展开的二叉树那么我们从二叉树的顶部也就是根节点到底部的叶子节点的每一个路径就是我们一个子序列那么我们就从根节点往下遍历那么在遍历的过程中同时用一个变量来记录我们遍历的节点的内容那么一旦到达底部我们从根节点沿途记录的内容就是我们的其中一个答案
所以只要理解了DFS的一个多叉树遍历模型那么这题的理解以及DFS的递归的实现就很轻松
代码实现
class solution
{public:void dfs(string a,vectorstring ans,string temp,int i){if(ia.size()){ans.push_back(temp);return;}dfs(a,ans,tempa[i],i1)//当前字符存在在子序列中dfs(a,ans,temp,i1);//当前字符不存在在子序列当中return;}void allsubstring(string a,vectorstring ans){string temp;dfs(a,ans,temp,0);return;}
}题目二字符串的全部不重复的子序列 难度EZ
题目现在我们有一个字符串a我们要求该字符串的全部且不重复的子序列
例abcc的全部不重复子序列,“a”,“b”,“c”,“ab”,“ac”,“bc”,“cc”,“abc”,“abcc”
这里的c以及abc会有重复
题目思路那么这个题我们就得在上一个题的思路下进行一个优化那么我们知道我们上一个题就是暴力枚举出所有的全部子序列那么我们这个枚举的过程就是一棵二叉树我们从顶部到底部进行遍历而这里我们只不过在添加一个哈希表的结构然后我们会将从顶部到底部的沿途的所有节点的记录加入到哈希表中去重即可.
代码实现
class solution
{public:void dfs(string a,vectorstring ans,string temp,int i,unordered_mapstring,int value){if(ia.size()){if(value.find(temp)value.end()){ans.push_back(temp);value[temp];}return ;}dfs(a,ans,tempa[i],i1)dfs(a,ans,temp,i1);return;}void allsubstring(string a,vectorstring ans){string temp;unordered_mapstring,int value;dfs(a,ans,temp,0,value);return;}
}题目三子集 难度MID
题目:现在有一个数组那么数组中每个元素可以组成一个集合请返回所有且不重复的集合。
例[1,2,3,4]的子集有[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],
[1,3,4],[2,3,4],[1,2,3,4]
注意[1,2,3]和[3,2,1]以及[2,1,3]是一个集合
题目思路那么这里我们解决该题的一个思路还是一个枚举那么我们按照每个位置是否在这个集合中存在来作为枚举那么每一个位置都有两种可能也就是存在在这个集合当中或者不存在在这个集合当中那么这里我们就枚举每一个位置的可能性然后每个位置的可能性所组合就是我们的子集了那么我们枚举的过程就是一棵决策树那么在当前每个位置的当前所做的决策就是二叉树的一个节点那么我们现在有两种决策要么存在在集合中要么不存在在集合中那么在二叉树的该节点中就对应就会有两个分支那么同理这两个分支下有对应着两个分支那么我们从顶部到达底部的路径的沿途的各个节点组合就是我们的子集那么我们就遍历我们这棵二叉树然后我们定义一个变量来记录沿途的路径上的节点内容即可。
class solution
{public:void dfs(vectorint a,vectorvectorint ans,int index,vectorint current,unordered_mapstring,int value){if(indexa.size()){for(int i0;icurrent.size();i){ato_string(current[i]);}if(value.find(a)value.end()){ans.push_back(current);value[a];}return;}current.push_back(a[index]);dfs(a,ans,index1,current);current.pop_back();dfs(a,ans,index1,current);}void all(vectorint a,vectorvectorint ans){vectorint current;unordered_mapstring,int value;dfs(a,ans,0,current,value);return;}
}但是我们可以优化一下因为我们知道这题存在重复的子集那么所谓的重复的子集就是集合的各个值的数量一样但是顺序不一样那么就是重复的子集那么我们就可以按照集合的特定的值的数量来进行一个枚举那么首先我们可以先对数组进行一个排序这样相同大小的数会在相邻位置然后我们按照这样的方式来枚举那么我们枚举集合中值为k的数在集合的数量为0的子集然后再枚举为值为k数量为1的子集有几个那么同理对于其他值也是这样那么我们将每个值在当前集合的数量的可能给组合就是我们的子集那么按照这样枚举的话我们就能够优化很多重复子集的枚举实现剪枝
而所谓的剪枝就跟园丁修建树木的花花草草一样我们这里的剪枝则是要修剪掉重复计算过的分支这样减少树的遍历从而优化时间复杂度并且也优化了空间复杂度因为减少了递归函数的调用从而不用为函数创建栈帧而在上一个题中我们用哈希表的方式来去重注意那个不是剪枝我们还是会从树的顶部走到底部然后将记录的结果加进哈希表中去重树的分支其实并没有减少
代码实现
class Solution {
public:void dfs(const vectorint nums, vectorvectorint subsets, vectorint current, int index) {if(indexnums.size()){ans.push_back(current);return;}int iindex1;while(inums.size()nums[i]nums[i-1]){i;}for(int j0;ji-index;j){current.push_back(nums[index]);dfs(nums,subsets.current,i);}}vectorvectorint subsets(vectorint nums) {vectorvectorint result;vectorint current;sort(nums.begin(), nums.end()); // 对数组进行排序dfs(nums, result, current, 0);return result;}
};题目四全排列 难度MID
题目那么现在有一个数组我们要得到该数组的所有全排列
例[1,2,3]的全排列有[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]
题目思路那么这里我们要枚举我们的所有全排列那么这里我们的枚举思路就是我们假设我们的数组长度为n那么意味着有n个数那么我们分别来枚举每一个位置的数的情况比如第一个位置有n种情况那么第二个位置有n-1种情况以此类推那么我们每个位置的情况组合就得到了我们的全排列那么我们这个枚举过程就是每一个数的决策就是该多叉树的一个节点那么我们其中从顶部到底部的各个路径就是我们其中一个全排列那么我们定义一个变量来记录我们从顶部到达底部的路径沿途的各个节点内容然后该记录就是我们的一个答案
代码实现
class solution
{public:void dfs(vectorint a,vectorvectorint ans,vetcorint temp,vectorint check){if(temp.size()a.size()){ans.push_back(temp);return;}for(int i0;ia.size();i){if(check[i]0){check[i]1;temp.push_back(a[i]);dfs(a,ans,temp,check);check[i]0;temp.pop_back();}}}void all(vectorint a,vectorvectorint ans){vectorint temp;vectorint check(a.size(),0);dfs(a,ans,temp,check);return;}
}3.结语
那么这就是我们DFS的全部内容那么我们DFS的应用场景就是那些需要我们去暴力枚举尝试的题目那么每一次枚举也就是每一次所做的要做的决策就是我们树当中的节点而其中枚举的可能性就是这个节点所对应的分支那么我们就沿途遍历这些所有的从顶部到达底部的所有分支并将沿途的节点内容给记录即可那么这就是我们的DFS本质上就是带路径的递归那么要掌握DFS只要熟悉我们的递归其实DFS的算法原理与思想其实很简单挺无脑的并且知道了DFS的算法模型就是一棵多叉树的话那么通过递归来实现的难度就减小很多
那么最后感谢你能够耐心的看完本文那么希望本文能够让你有所收获我会持续更新希望你能够多多关注那么如果我的文章有帮组到你那还请你多多三连支持哦你的支持就是我创作的最大的动力
