淘客网站模版,北京网站优化指导,做响应式网站多少钱,哪些网站是响应式个人主页 #xff1a; zxctscl 专栏 【C】、 【C语言】、 【Linux】、 【数据结构】、 【算法】 如有转载请先通知 文章目录 递归、搜索和回溯递归搜索VS 深度优先遍历 VS 深度优先搜索 VS 宽度优先遍历 VS 宽度优先搜索 VS 暴搜回溯与剪枝 1 面试题 08.06. 汉诺塔问题1.1 分析… 个人主页 zxctscl 专栏 【C】、 【C语言】、 【Linux】、 【数据结构】、 【算法】 如有转载请先通知 文章目录 递归、搜索和回溯递归搜索VS 深度优先遍历 VS 深度优先搜索 VS 宽度优先遍历 VS 宽度优先搜索 VS 暴搜回溯与剪枝 1 面试题 08.06. 汉诺塔问题1.1 分析1.2 代码 2 21. 合并两个有序链表2.1 分析2.2 代码2.3 总结 3 206. 反转链表3.1 分析3.2 代码 4 24. 两两交换链表中的节点4.1 分析4.2 代码 5 50. Pow(x, n)5.1 分析5.2 代码 递归、搜索和回溯
搜索是递归的一个分支回溯是搜索里面的分支。
递归 什么是递归 在数据结构二叉树、快排和归并都有提到 递归就是函数自己调用自己的情况 为什么会用到递归 二叉树的后序遍历左子树、右子树、根 在快排中先选择一个基准元素将数组分成两部分左边排一下序右边排一下序 在归并排序中选择一个中间点把数组平分先让左边排一下序再让右边排一下序再把两个有序数组合并 递归的本质 主问题-相同的子问题 子问题-相同的子问题 如何理解递归 1递归展开的细节图 2二叉树的题目 3宏观看待递归过程 一、不要在意递归细节展开图 二、把递归的函数当成一个黑盒具体里面如何操作的并不关心只要能输出结果 三、相信这个黑盒一定能完成这个任务 如何写好递归 1先找到相同的子问题-函数头的设计 2只关心某一个子问题是如何解决的-函数体的书写 3注意一下递归函数的出口即可
搜索VS 深度优先遍历 VS 深度优先搜索 VS 宽度优先遍历 VS 宽度优先搜索 VS 暴搜 深度优先遍历 VS 深度优先搜索-dfs 宽度优先遍历 VS 宽度优先搜索-bfs 一定程度上等同 遍历是形式目的是搜索 关系图 暴力枚举一遍所有的结果 搜索也叫暴搜分为两种dfs、 bfs 递归主要是dfs 拓展搜索问题 全排列 树状图
回溯与剪枝
回溯 回溯本质就是深搜
1 面试题 08.06. 汉诺塔问题 1.1 分析 题目解析 中间摆放的时候必须是小盘子在大盘子的上面 算法原理 1如何解决汉洛塔问题 当N1直接把A上面的盘子放到C上。 当N2想要把最大的盘子放到C上此时先得把上面的小盘子放到B上当把A剩下的大盘子直接移动到C上后再将B上的小盘子放到C上。 当N3时候首先把A最下面盘子移动到C前提就得将A上面的2个盘子放到B上就像N2时把上面两个盘子借助C移到B上再将A最下面的盘子放到C上最后把B上的盘子移到C上。 当N4时首先把A最下面盘子移动到C前提就得将A上面的3个盘子当做一个整体放到B上就像N3时把上面两个盘子借助C移到B上再将A最下面的盘子放到C上最后把B上的盘子移到C上。 … 当Nn也同样是首先把A最下面盘子移动到C前提就得将A上面的n-1个盘子当做一个整体放到B上就像Nn-1时把上面两个盘子借助C移到B上再将A最下面的盘子放到C上最后把B上的盘子移到C上。 2为什么用递归 大问题-相同问题的子问题 子问题-相同问题的子问题
3如何编写递归代码 一、重复子问题-函数头 先把X柱子上的盘子借助Y柱子转移到Z柱子上 需要三个柱子还有盘子的数量就需要传四个参数
void dfs(X,Y,Z,int n)二、只关心某一个子问题在做什么-函数体 1将X上面n-1盘子借助Z转移到Y上dfs(X,Z,Y,n-1) 2把A最下面盘子移到Z上 3再将Y上n-1个盘子借助X移到Z上dfs(Y,X,Z,n-1)
三、递归出口 当N1时把X上盘子放到Z上 编写代码 递归的细节展开图
1.2 代码
class Solution {
public:void hanota(vectorint A, vectorint B, vectorint C) { dfs(A,B,C,A.size()); }void dfs(vectorint A, vectorint B, vectorint C,int n){if(n1){C.push_back(A.back());A.pop_back();return;}dfs(A,C,B,n-1);C.push_back(A.back());A.pop_back();dfs(B,A,C,n-1);}
};2 21. 合并两个有序链表 2.1 分析
算法原理 解法递归
两个链表都是升序找两个链表头结点中较小的节点作为返回的头节点。 当选择头节点之后就是将剩下的两个链表合并
1重复子问题-函数头 合并两个有序链表 Node*dfs(l1,l2)
2只关心某一个子问题在做什么事情-函数体的设计 一、比大小 二、如果l1较小 l1-nextdfs(l1-next,l2) 三、return l1
3递归出口
谁为空返回另一个 2.2 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){if(list1nullptr)return list2;if(list2nullptr)return list1;if(list1-vallist2-val){list1-nextmergeTwoLists(list1-next,list2);return list1;}else{list2-nextmergeTwoLists(list1,list2-next);return list2;}}};2.3 总结
递归VS循环 什么时候用循环舒服什么时候用递归舒服 递归和循环都是重复子问题递归和循环之间可以相互转换
递归图越复杂递归就越舒服
递归VS深搜 递归展开图其实就是对一棵树做一次深度优先搜索遍历dfs
3 206. 反转链表 3.1 分析
解法递归
第一个视角从宏观角度
把当前节点后面链表先逆置并且把头结点返回把当前节点添加到逆置链表的后面当遇到null就返回
第二个视角将链表看成一棵树 先找到叶子结点再返回 3.2 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(headnullptr||head-nextnullptr)return head;ListNode* newheadreverseList(head-next);head-next-nexthead;head-nextnullptr;return newhead;}
};4 24. 两两交换链表中的节点 4.1 分析
解法递归 视角从宏观角度看待递归
想要两两逆置把后面的那堆先两两逆置一下后面的调用完dfs后再返回后面部分的头结点再把前面两个交换一下把交换后的连起来。 4.2 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head nullptr || head-next nullptr)return head;ListNode* tmp swapPairs(head-next-next);ListNode* ret head-next;head-next-next head;head-next tmp;return ret;}
};5 50. Pow(x, n) 5.1 分析
解法一、暴力循环 对于太大的幂是会超时的
二、快速幂 实现快速幂1递归2循环
这里用递归
如果快速得到3的16次方得到3的8次方就行要3的8次方得到3的4次方就行要得到3的4次方得到3的2次方就行要得到3就直接3乘1就行。这里时间复杂度就是logN
那么如果除不进时21/2除不进就能可以分为3的10次方乘3的10次方再乘3就行一直这样
1重复子问题-函数头
int pow(x,n)2只关心某一个子问题在做什么事情-函数体的设计 先求出n/2的次方是多少: tmppow(x,n/2) 再判断一下n/2能不能整除不能整除再成上xreturn n%20?tmp*tmp*x
3递归出口 如果n等于0就返回1
细节问题 n可能是负数 要提前把负数转成正数再用1除一下 n可能是-2^31 -2^31负数太大转成正数会存不下int正整数最大是2^31-1 可以提前把n的类型强转为long long
5.2 代码
class Solution {
public:double myPow(double x, int n) {return n0?1.0/pow(x,-(long long)n):pow(x,n);}double pow(double x, int n){if(n0)return 1.0;double tmppow(x,n/2);return n%20?tmp*tmp:tmp*tmp*x; }
};有问题请指出大家一起进步
