递归_汉诺塔_链表_快速求幂

面试题 08.06. 汉诺塔问题

把大问题分为诺干个小问题，解决每个小问题的方法一样就可以用递归。

无论盘子的个数有多少个，都可以分为3步。

1.把n-1个盘子放到中间盘子中

2.把最后的盘子放到右边的盘子中

3.再把n-1个盘子放到右边的盘子中

具体怎么移动n-1个盘子交给递归实现就可以

左边部分完成n-1盘子到中间

右边部分完成n-1盘子到右边

class Solution {
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {int n=A.size();dfs(A,  B, C,n);}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;}//从A借助C把n-1个盘子放到B中dfs(A,C,B,n-1);//把最后的盘子放到C中C.push_back(A.back());A.pop_back();//把n-1个盘子从B借助A放到C中dfs(B,A,C,n-1);}
};

21. 合并两个有序链表

不新建链表，把两个链表合并成一个并返回。

怎么合并？把两链表的较小的结点当头节点，它的下一个结点是什么？还是两个链表中较小的结点。以此类推直到有一个链表为空

一直找两链表头节点较小的节点 就可以用递归。

1.判断找到较小节点当头节点

2.头节点后面节点交给递归解决

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

206. 反转链表

方法1：宏观观察

逆转链表 最简单的子问题是什么？逆转两个节点，怎么搞？

cur->next->next=cur;cur->next=nullptr

逆序整个链表就可以分为逆转诺干个两个节点 可以用递归 dfs完成后面第一个节点后面所有节点的逆转，再把第一个 第二个节点逆转 并让第一个节点指向空就可以了。

class Solution {
public:ListNode* reverseList(ListNode* head) {// 如果链表为空或者只有一个元素，直接返回该节点if(head == nullptr || head->next == nullptr) return head;// 递归地反转剩余的链表ListNode* re = reverseList(head->next);// 反转当前节点的指针head->next->next = head;  // 将当前节点的下一个节点的 next 指向当前节点head->next = nullptr;     // 将当前节点的 next 设为 null，断开链表的连接return re;  // 返回新的头节点}
};

方法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) {return dfs(nullptr,head);}ListNode* dfs(ListNode*prve,ListNode*cur){if(cur==nullptr)return prve;ListNode*re= dfs(cur,cur->next);cur->next=prve;;return re;}
};

24. 两两交换链表中的节点

和上一道题一样 从宏观角度来看

我们只需要处理好前两个节点的交换 剩下节点交换交给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* swapPairs(ListNode* head) {if(head==nullptr||head->next==nullptr) return head;ListNode*next=head->next;ListNode*tmp=swapPairs(head->next->next);head->next=tmp;//连接后面节点next->next=head;return next;//返回头节点}
};

50. Pow(x, n)

怎么快速求一个数x的n次方？

x*x进行n次吗？没必要

如果n是偶数x^n=x^(n/2)*x^(n/2) 是奇数x^n=x^(n/2)*x^(n/2)*x

先求x^(n/2)就可以，直到n=0返回1

注意：

1.n<0 时要返回1/x^n

2.不管n是否小于0 都要求x^n。所如果n<0以我们传去的n的相反数

但-2^31 <= n <= 2^31-1 如果n==-2^31 它变为正数int会存存不下，所以n要用long long

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