递归专题刷题

递归

1. 重复的子问题+宏观看待递归问题

合并两个有序链表

题目链接

题解

1. 重复的子问题 -> 函数头的设计
合并两个有序链表，Node* dfs(l1,l2)
2. 只关心某个子问题在做什么事情 -> 函数体的设计
主问题是合并两个链表，这样可以拆成一个节点和它后面的链表，它后面的链表和另一个链表可以合并为一个链表，之后问题可以再拆成子问题
1、链表中的值比大小，选小的那个，这里随便写的 l1
2、l1->next = dfs(l1->next,l2)
3、返回 l1，把链表连起来
3. 递归的出口
只要其中一个节点为空，返回另一个节点，如果两个节点都为空，返回空

代码

/*** 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:// 递归的时候l1和2的顺序可以变ListNode* dfs(ListNode* a,ListNode* b){// 子问题// 可以分成一个头结点+剩余的链表和另一个链表合并if(a == nullptr) return b;if(b == nullptr) return a;// 不能这样写,会出现a != nullptr和b != nullptr的情况return a// if(a == nullptr) return b;// else return a;if(a->val > b->val){b->next = dfs(a,b->next);return b;}else{a->next = dfs(a->next,b);return a;}}ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {return dfs(list1,list2);}
};

反转链表

题目链接

题解

1. 宏观上看待递归
1、把第一个节点后面的链表反转，并且返回最后一个节点作为头节点返回，然后把第一个节点和链表链接起来，你就相信dfs可以完成链表的逆置并且返回最后一个节点作为头节点
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(head == nullptr || head->next == nullptr) return head;// 不用实现内部的代码,把它想象为一个黑盒// 宏观看待递归// 把head->next的一段链表逆置,返回这段链表的头节点ListNode* newhead = reverseList(head->next);head->next->next = head;head->next = nullptr;return newhead;}
};

两两交换链表中的节点

题目链接

题解

1. 宏观上使用递归
1、将前两个节点看成一个整体，后面的链表看成一个整体，相信后面的链表可以完成任务，返回头节点
2、先将head->next存为cur，防止后面找不到，
head->next = dfs(head->next->next)，cur->next = head，就完成了链表的交换

代码

/*** 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* cur = head->next;head->next = swapPairs(head->next->next);cur->next = head;return cur;}
};

Pow(x, n)（快速幂）

题目链接

题解

1. 用暴力会超时
2. 快速幂的时间复杂度是O(logN)，每次都分解为幂的一半相乘，比如 2^n = 16，如果n是偶数，tmp * tmp即为答案，n是奇数，tmp * tmp * x是答案

代码

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

汉诺塔

题目链接

题解

1. 汉诺塔可以分解为相同的子问题，
n-1个盘子通过C柱移动到B柱，A柱上的盘子移动到C柱，B柱上n-1个盘子通过A柱移动到C柱，下图中N = 2，N = 3，N = 4个盘子都是相同的子问题
2. 如何写代码？
1、重复的子问题->函数头
dfs(x,y,z,n)，x柱上的盘子借助y柱移动到z柱上
2.只关心每一个子问题怎么处理->函数体的设计
dfs(x,z,y,n-1)
x.back() -> z
dfs(y,x,z,n-1)
3.递归的出口
n == 1，只有一个盘子的时候，直接把x柱上的盘子移动到z柱上，x.back() -> z

代码

class Solution 
{
public:// void dfs(vector<int>& a,vector<int>& b,vector<int>& c,int n)// {//     if(n == 1)//     {//       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);// } void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {// int n = A.size();// dfs(A,B,C,n);C = A;}
};

总结

1.什么时候使用递归？
一个问题可以分成相同类型的子问题
2. 怎么使用递归？
1、重复的子问题->函数头的设计
2、只关心某个子问题在做什么事情->函数题的设计
3、递归的出口->返回条件