面试题 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;
}
};