专题九_递归_算法专题详细总结

目录

递归

1.什么是递归？

2.为什么会用到递归？

3.如何理解递归？

1.递归展开的细节图

2.二叉树中的题目

3.宏观看待递归的过程

1) 不要在意细节的展开图

2) 把递归的函数当作一个黑盒

3) 相信这个黑盒一定能够完成这个任务

4.如何写好一个递归？

二、搜索 vs 深度优先遍历 vs 深度优先搜索 vs 宽度优先遍历 vs 宽度优先搜索 vs 暴搜

1.深度优先遍历 vs 深度优先搜索(dfs)​编辑

2.宽度优先遍历 vs 宽度优先搜索(bfs)​编辑

2.关系图

3.拓展搜索问题

三、回溯与剪枝

1.本质

1. 汉诺塔 （easy）

解析：

一步步拆解汉诺塔问题，了解为什么可以用递归来解决这道题目！！！ 

1.重复子问题 -> 函数头

2.只关心一个子问题在做什么 -> 函数体

3.递归的出口

总结：

2. 合并两个有序链表（easy）

解析：

1.考虑主问题 -> 寻找头函数

2.寻找子问题 -> 构造函数体

3.细节问题，返回出口

总结：

3. 反转链表（easy）

解析：

怎么用上递归？依旧是寻找子问题：第一种视角：从宏观的角度来解决问题

第二种视角：将链表看成一颗树

4. 两两交换链表中的节点（medium）

解析：

总结：

5. Pow（x, n）- 快速幂（medium）

解析：

1）暴力：就是2^10=2*2*2*2*2……，这种办法绝对会超时的

2）优化：快速幂

细节问题：

总结：

---

递归

1.什么是递归？

C语言+数据结构（二叉树、快排、归并）

函数自己调用自己的情况

2.为什么会用到递归？

本质：就是出现了相同的子问题

           主问题 -> 相同的子问题

           子问题 -> 相同的子问题

            全都可以调用f()函数

3.如何理解递归？

1.递归展开的细节图

2.二叉树中的题目

3.宏观看待递归的过程

1) 不要在意细节的展开图

2) 把递归的函数当作一个黑盒

3) 相信这个黑盒一定能够完成这个任务

eg:二叉树的后序遍历

void dfs(TreeNode* root)
{//细节--出口if(root==nullptr) return;dfs(root->left);    //不管三七21，我要先遍历我的左子树dfs(root->right);  //然后在要遍历右子树，我相信这个递归函数一定能帮我完成printf(root->val);  //最后再遍历自己
}

eg:归并 

void merge(nums,int left,int right)
{//细节问题-保证不能出现死递归if(left>=right) return;//1.先让左边排排序  2.右边排排序  3.然后合并两个数组   那么就要选取中间点int mid=(left+right)/2;merge(nums,left,mid);merge(nums,mid+1,right);//合并两个数组
}

4.如何写好一个递归？

1.先找到相同的子问题!!! -> 函数头的设计

2.只关心某一个子问题是如何解决的 -> 函数体的书写

3.注意一下递归函数的出口即可

 

二、搜索 vs 深度优先遍历 vs 深度优先搜索 vs 宽度优先遍历 vs 宽度优先搜索 vs 暴搜

1.深度优先遍历 vs 深度优先搜索(dfs)

2.宽度优先遍历 vs 宽度优先搜索(bfs)

那么遍历只是形式，目的是搜索

2.关系图

暴力枚举一遍所有的情况

搜索(暴搜) dfs

3.拓展搜索问题

全排列

决策树

三、回溯与剪枝

1.本质

就是深搜dfs

回溯：就是尝试某一种情况，但是行不通的时候，退回到上一级的操作。

剪枝：当有多个分岔路口的时候，我们已经明白或者已经走过了某一条路，我们就不用再走这一条路，那么就把这条路直接剪掉，尝试别的路径。

递归：

1. 汉诺塔 （easy）

简单的汉诺塔问题，相信大家再最初学习C语言的时候就都已经接触过汉诺塔问题，是一个很好学习递归的题目

解析：

一步步拆解汉诺塔问题，了解为什么可以用递归来解决这道题目！！！ 

可以发现该汉诺塔问题存在许多重复的子问题。

那么就可以对于重复的子问题进行细分，来一步步书写代码。

1.重复子问题 -> 函数头

将A(x)柱子上的一堆盘子，借助B(y)柱子，转移到C(z)柱子上 

void dfs(x,y,z,int n);

2.只关心一个子问题在做什么 -> 函数体

第一步：

这n-1个盘子要通过z的帮助，来转移到y上，那么函数体就是：

dfs(x,z,y,int n-1);

第二步：

将A(x)上的最后一块盘子转移到C(z)上:

x.back() -> z

第三步：

就是将这n-1块盘子通过A(x)转移到C(z)上:

dfs(y,x,z,int n-1);

3.递归的出口

当N==1 的时候，就只用放到C盘上就可以了。

class Solution {
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {dfs(A,B,C,A.size());}void dfs(vector<int>& x,vector<int>& y,vector<int>& z,int N){if(N==1){z.push_back(x.back());x.pop_back();return;}dfs(x,z,y,N-1);z.push_back(x.back());x.pop_back();dfs(y,x,z,N-1);}
};

总结：

这里唯一需要注意的就是当x上的盘子移动到z上时，唯一的不同就是要将x.back()也就是最后一个元素移动到z上，并不是首元素进行移动。

2. 合并两个有序链表（easy）

这题在上一个链表专题已经写过迭代的版本，就是利用多个指针，将较大值连接在较小值的后面，然后移动指针。

解析：

依旧是考虑这题为什么能够用到递归，那么就是来寻找子问题：

1.考虑主问题 -> 寻找头函数

主问题就是合并两个有序链表，那么最后返回的就是开始头节点较小的那个指针

2.寻找子问题 -> 构造函数体

假设l1这个指针是一个较小的指针，那么就让它来连接l1->next 后面的链表跟 l2后面的链表进行结合的有序链表，那么子问题的函数体就也是合并两个有序链表。

这个函数体就总结成谁小，谁做表头，去连接剩下两个有序链表合并后的结果。  

        if(l1->val<l2->val) {l1->next=mergeTwoLists(l1->next,l2);return l1;}else {l2->next=mergeTwoLists(l1,l2->next);return l2;}

最后不要忘记的就是连接完后，要返回该位置的头节点，来给上一层的链表进行连接。

3.细节问题，返回出口

当某一个链表为空的时候，就返回另一个链表

        if(l1==nullptr) return l2;
        if(l2==nullptr) return l1;

/*** 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* l1, ListNode* l2) {if(l1==nullptr) return l2;if(l2==nullptr) return l1;if(l1->val<l2->val) {l1->next=mergeTwoLists(l1->next,l2);return l1;}else {l2->next=mergeTwoLists(l1,l2->next);return l2;}}
};

总结：

循环（迭代）vs 递归

这些都是解决重复子问题

证明他们都是可以互相转换的，那么什么时候循环舒服？什么时候递归舒服？

当这个决策树很恶心的时候，肯定就是用递归更爽，举个例子，假如只是递归一个数组，它的决策树就是只有一个左子树，很简单，那么这个递归改循环就很简单。

//对于循环
for(int i=0;i<n;i++)
{cout<<nums[i]<<" ";
}
cout<<endl;//对于递归
dfs(nums,0);void dfs(vector<int>& nums,int i)
{//递归出口if(i==nums.size()) return;cout<<nums[i]<<" ";dfs(nums,i+1);
}

3. 反转链表（easy）

简单的翻转链表，在上一个专题就已经通过指针迭代的方式完成过。

解析：

怎么用上递归？依旧是寻找子问题：
第一种视角：从宏观的角度来解决问题

1.让当前节点后面的链表先逆置，并且把头节点返回；

2.让当前节点添加到逆置后的链表后面即可。

第二种视角：将链表看成一颗树

仅需做一次dfs即可，进行后序遍历。

/*** 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(head==nullptr||head->next==nullptr) return head;ListNode* newHead=reverseList(head->next);//接受head->next 后面链表逆置的结果head->next->next=head;head->next=nullptr;return newHead;}
};

总结：

从宏观的角度上看，依旧是对递归特别好的理解，假如我从第一个头节点开始，我来进行翻转的时候，把head->next 后面的所有链表都交给我的主函数reverseList(head->next); 因为我所有的子问题都是相同的，都是要进行对链表的翻转，那么每次翻转完成，我都将翻转后的头节点存入newhead里面，那么最后翻转完成后一定返回的是newhead。

待物将第一个节点后面所有链表节点交给这个函数后，证明他已经被反转，那么我只需要注意当前我的head->next->next=head,就是让后面的被翻转完成的链表指向我自己；

head=nullptr，就保证在每一层递归内的操作都是一样的，保证最后一个节点就指向的是nullptr

4. 两两交换链表中的节点（medium）

在不创建新节点，只在原链表上进行修改节点

解析：

两两交换链表的节点，这题用递归简直跟上一题一模一样。

在宏观上：
先交换前两个节点的后面所有的链表节点

只用判断离我们最近且最开始的两个带交换的节点进行具体的详细操作就OK，然后递归函数就传入head->next->next；的值

1.函数头

        ListNode* tmp=swapPairs(head->next->next);

2.函数体

ListNode* tmp=swapPairs(head->next->next);ListNode* ret=head->next;head->next->next=head;head->next=tmp;

3.函数出口

        if(head==nullptr||head->next==nullptr) return head;

最后因为返回头节点是ret，所以要单独记录一下。

/*** 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. Pow（x, n）- 快速幂（medium）

题意很简单，相信大家都用过这个函数，pow就是求一个数的n次幂

解析：

1）暴力：
就是2^10=2*2*2*2*2……，这种办法绝对会超时的

2）优化：快速幂

实现快速幂：1.递归  2.循环

考虑了快速幂的算法问题，那么只要考虑三步即可：
1.相同子问题 -> 函数头

int pow(x,n);

2.只关心每一个子问题做了什么 -> 函数体

tmp = pow(x,n/2);

return n%2==0 ? tmp * tmp : tmp * tmp * x;

3.递归出口

 if(n==0) return 1;

细节问题：

1.n可能是负数

 那么 3^(-2) = 1/(3^2)

2.n可能是-2^31 这样int存不下，要用long long

class Solution {
public:double myPow(double x, int n) {return n<0?1/dfs(x,n):dfs(x,n);}double dfs(double x,int n){if(n==0) return 1;double tmp=dfs(x,n/2);return n%2==0?tmp*tmp:tmp*tmp*x;}
};

总结：

这里最主要的就是快速幂的算法原理，要注意考虑每一阶段中dfs传入的都是n/2，然后考虑n%2是否==0，再就是考虑到n<0时求pow幂的倒数。注意double范围。

总结一下吧~这节对我的帮助真的很大，希望对你也是！！！