网站全局参数设置,网站建设贰金手指下拉,室内设计网站国外,企业简介模板文字作者简介#xff1a;大家好#xff0c;我是未央#xff1b; 博客首页#xff1a;未央.303 系列专栏#xff1a;递归、搜索与回溯算法 每日一句#xff1a;人的一生#xff0c;可以有所作为的时机只有一次#xff0c;那就是现在#xff01;#xff01;#xff01;大家好我是未央 博客首页未央.303 系列专栏递归、搜索与回溯算法 每日一句人的一生可以有所作为的时机只有一次那就是现在 文章目录
前言
一、递归算法
1.1 什么是递归
1.2 为什么会用到递归
1.3 如何理解递归
1.4 如何写好一个递归
二、搜索算法
2.1 深度优先遍历vs深度优先搜索
2.2 宽度优先遍历vs宽度优先搜索
2.3 扩展搜索问题
三、回溯算法
总结 前言
今天我们将进入到递归搜索回溯算法这些算法在我们笔试中非常重要必须要熟练掌握本节内容主要带着认识一下这些算法了解其本质后面会有很多例题来巩固这些算法 一、递归算法
1.1 什么是递归
我们要学会递归算法的使用首先要了解它是什么才能更好的掌握和使用它。 简而言之递归函数自己调用自己的情况直到碰到终止条件返回结果的过程。 递归可以看作两个过程分别是递和归。 递就是原问题把要计算的结果传给子问题 归则是子问题求出结果后把结果层层返回原问题的过程。 1.2 为什么会用到递归 递归的本质 即主问题可以推出与主问题相同的子问题 而子问题又可以继续推出与子问题相同的子子问题 实例图示说明 1二叉树的遍历 2快速排序算法 3归并排序算法 1.3 如何理解递归
第一步递归展开细节图 归并排序举例 递归展开图int arr[] { 7,5,6,3,9,8,2,1,4,5 }; 第二步二叉树的递归 二叉树递归举例 先简单的定义一个 二叉树 像这样的二叉树 第三步宏观看待递归过程重要 1不要在意递归的细节展开图 2把递归当成一个黑盒 3相信这个黑盒一定能完成这个任务 1.4 如何写好一个递归 第一步 先找一下是否有和主问题相同的子问题----- 关系到函数头的设计 第二步 只需要关心某一个子问题是如何解决即可----- 关系到函数体的书写 第三步 最后再注意一下递归函数的出口即可 代码示例说明 1二叉树的递归 代码实现 //二叉树的后续遍历
void dfs(TreeNode* root){//递归的返回条件
if(root null)
return;//先递归遍历左子树
dfs(root.left);
//再递归遍历右子树
dfs(root.right);
//最后遍历根结点
printf(root.value);} 2归并排序 代码实现 void merge(nums,int left,int right){
//细节出口
if(left right){int mid (leftright)/2;
merge(nums,left,mid);
merge(nums,mid1,right);
//合并两个有序数组
}二、搜索算法
2.1 深度优先遍历vs深度优先搜索 深度优先遍历深度优先搜索一条路走到黑走到不能继续走的时候就返回 两者实际是一样的概念而不同的是 遍历是形式搜索是目的 图示说明 2.2 宽度优先遍历vs宽度优先搜索 宽度优先遍历深度优先搜索又叫层次遍历从上往下对每一层依次访问在每一层中从左往右也可以从右往左访问结点访问完一层就进入下一层直到没有结点可以访问为止。 两者实际是一样的概念而不同的是 遍历是形式搜索是目的 图示说明 2.3 扩展搜索问题 搜索方式不仅仅局限于二叉树图类等还可以对于一些全排列如果列举问题能用决策树的图示表示出来依然可以用搜索来解决问题 三、回溯算法 回溯算法定义 回溯算法也叫试探法它是一种系统地搜索问题的解的方法。一个典型的应用是走迷宫问题当我们走一个迷宫时如果无路可走了那么我们就可以退一步再在其他的路上尝试一步如果还是无路可走那么就再退一步尝试新的路直到走到终点或者退回到原点。 回溯的本质回溯的本质就是深搜 图示说明 总结
