目录
题目一:汉诺塔问题
在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1:
输入:A = [2, 1, 0], B = [], C = [] 输出:C = [2, 1, 0]
示例2:
输入:A = [1, 0], B = [], C = [] 输出:C = [1, 0]
提示:
- A中盘子的数目不大于14个。
汉诺塔问题算是递归中的典型例题了,要求将A上的盘子挪到C上,在挪动过程中,只允许叠在比它大的盘子上
下面举个例子,刚开始是这样,先将小盘子挪到C上:
再将中间的盘子挪到B上,然后将C上的盘子挪到B上:
将A的大盘子挪到C上,再将B上面的小盘子挪到A上:
最后将B的盘子挪到C上,再将A的盘子挪到C上:
至此就成功将A上的盘子,借助B,挪到C上,且符合题目挪动的要求,上述就是汉诺塔问题挪动的过程
我们首先要明确一个目标,因为小盘子需要放到大盘子上面,所以挪动的首要目标就是将A中最底下的盘子挪到C上,接着挪动过程就需要借助辅助盘子B了
相当于将A上除了最大盘子外的其他盘子,挪到B这个辅助盘子上面,再将A的最大盘子挪到C上,最后将B上的盘子挪到C上
下面画图表示这个流程:
上图中 N = 1 和 N = 2 的情况不需要解释,当 N = 3 时,为了将A中最大的盘子挪动到C上,第一步就是将最大盘子上的其他盘子挪动到B上, 再将大盘子挪动到C上
而将大盘子上的两个盘子,通过借助C盘子挪动到B上,与 N = 2 的情况是完全一样的,只不过辅助盘子不同罢了,那么借助这个规律,N = 4也是一样的了:
为了将A的最大盘子挪到C上,第一步就是将A上面的3个盘子挪到B上,这一步就与 N = 3 的行为是一样的了
所以我们在解决N = 4时,出现了解决N = 3的情况,同样在解决 N = 3 时,出现了解决N = 2的情况,也就是:
大问题 -> 相同类型的子问题
子问题 -> 相同类型的子问题
编写递归的代码,有以下几步:
①重复子问题(函数头)
②只关心某一个子问题在做什么(函数体)
③递归的出口
先看第一步:重复子问题
在上述的过程中,每次都需要将一个柱子上一定数量的盘子,借助另一个柱子的帮助,挪动到第三个柱子上
即:将a柱子上的盘子,借助b柱子,转移到c柱子上
所以函数头为:void dfs(a, b, c, int n)
函数头上a、b、c柱子的顺序是有规律的,也就是与上面的话一一对应,n表示需要转移的盘子数量
第二步:只关心某一个子问题在做什么
如上面的图所示,某一子问题都是分为三步:
①先将a上的 n - 1个盘子借助 c 挪到 b
②将 a 上最大盘子挪到 c
③将 b 上所有盘子借助 a 挪到 c
所以函数体为(伪代码):
dfs(a, c, b, n - 1);
a.back() -> c; a.pop_back();
dfs(b, a, c, n - 1);
第三步:递归的出口
通过上面的图可以看出,只有 N = 1 的情况不同,直接将 a 的盘子挪到 c 上,不借助辅助柱子
if(n == 1) a.back() -> c;
代码如下:
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;
}
// a 的 n-1 个盘子借助 c 挪到 b 上
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)
{
// a 的 n 个盘子借助 b 挪到 c 上
dfs(a, b, c, a.size());
}
};
题目二:合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = [] 输出:[]
示例 3:
输入:l1 = [], l2 = [0] 输出:[0]
提示:
- 两个链表的节点数目范围是
[0, 50]
-100 <= Node.val <= 100
l1
和l2
均按 非递减顺序 排列
这道题是非常熟悉的,在链表中是完成过这道题目的,当时是尾插到新链表的方式解决此题,而这里是使用递归的方式来解决的
使用递归解决,首先就需要找到重复子问题
刚开始合并题目给的两个链表,首先需要找两个链表中较小的那个结点做新链表的头结点,而挑选出该结点作为头结点后,就需要继续合并删掉该结点后的链表以及另一个链表,这里就找到了重复子问题了
1、重复子问题(函数头的设计)
通过上面的叙述,可以发现,这道题的重复子问题就是合并两个有序链表
Node* dfs(Node* l1, Node* l2);
2、只关心某个子问题在做什么(函数体的设计)
①比两个链表中第一个结点的大小
②假设l1小,此时 l1->next = dfs(l1->next, l2);
③return l1;
3、递归的出口(边界情况)
递归出口就是两个链表谁为空,就返回另一个链表即可
代码如下:
class Solution
{
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
// 边界条件
if(list1 == nullptr) return list2;
if(list2 == nullptr) return list1;
// 重复子问题
if(list1->val < list2->val)
{
// list1小,就list1当头结点,接收下面的这两个链表合并后的结果
list1->next = mergeTwoLists(list1->next, list2);
// 合并后返回头结点即可
return list1;
}
else// 同理
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
题目三:反转链表
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2] 输出:[2,1]
示例 3:
输入:head = [] 输出:[]
反转链表我们同样使用循环的方式写过,这里采用递归的方式再解决一下,有两种视角:
第一种视角:从宏观的视角看待
想要将链表逆序,那么只需要将第一个结点后面的链表逆置,此时再将第一个节点也放入这个逆置链表中
同样的,想要将第一个结点后面的链表逆置,只需要将后面这个链表的第一个结点,它后面的链表逆置,再将这个结点节点也放入这个逆置链表中
第二种视角:将链表看成一棵树
相当于一个树,每个结点只有一个孩子,一直向下,我们要做的就是相当于后面遍历,找到最后一个节点后,将该结点作为逆置链表的头结点,后再找上面的结点,进行指针翻转,并将上面的结点的指针指向空
这两种视角的代码是完全相同的,都是每次将下面的链表逆置后,将该结点也放入这个逆置链表中,也就是改变逆置链表最后一个节点与该结点的指针指向
代码如下:
class Solution
{
public:
ListNode* reverseList(ListNode* head)
{
// 如果没有节点或是只有一个结点,直接return head
if(head == nullptr || head->next == nullptr) return head;
// 先逆置第一节点后面的链表
ListNode* newhead = reverseList(head->next);
// 逆置完成后,再将第一个节点也放入这个逆置链表中,即改变指针指向
head->next->next = head;
head->next = nullptr;
return newhead;
}
};
题目四:两两交换链表中的结点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4] 输出:[2,1,4,3]
示例 2:
输入:head = [] 输出:[]
示例 3:
输入:head = [1] 输出:[1]
同样采用宏观角度看待:
和上一题一样的思想,想要两两交换,只需要现将前两个结点后面的链表两两交换,再将前两个结点交换后,与后面交换成功的链表链接起来即可
而后面的链表与上述思想一样,都是这样解决的
代码如下:
class Solution
{
public:
ListNode* swapPairs(ListNode* head)
{
// 如果只有一个结点或是空节点,直接返回即可
if(head == nullptr || head->next == nullptr) return head;
// 将前两个结点的后面的链表先两两交换,交换后的链表的头结点返回给tmp
ListNode* tmp = swapPairs(head->next->next);
// 将前两个结点交换后,插入后面的链表中
ListNode* newhead = head->next;
head->next->next = head;
head->next = tmp;
// 最终返回前两个结点中的第二个结点,也就是上面记录的newhead结点
return newhead;
}
};
题目五:Pow(x,n)
实现 pow(x, n),即计算 x
的整数 n
次幂函数(即,x^n
)。
示例 1:
输入:x = 2.00000, n = 10 输出:1024.00000
示例 2:
输入:x = 2.10000, n = 3 输出:9.26100
示例 3:
输入:x = 2.00000, n = -2 输出:0.25000 解释:2-2 = 1/22 = 1/4 = 0.25
解法一:暴力解法
这个快速幂的题目,最先想到的肯定是暴力解法了,假设求 2^6,那就循环6次,每次都乘2,最终得到结果,但是如果次方数非常大,那就肯定会超时,所以就不考虑这种解法了
解法二:快速幂
快速幂也就是假设要求 2^6,那我只需要知道 2^3 即可,这样就可以直接 2^3 * 2^3 得到 2^6
同样 2^3 只需要知道 2^1 * 2^1 * 2,因为次方数3不能整除,所以这里再多乘一个2即可
同样想知道 2^1,只需要 2^0 * 2 就能得到,最终结束
快速幂的时间复杂度是:O(logN)
我们可以发现,上述的描述,每次求一个值时,都是相同的逻辑,也就是都是相同的子问题,此时就可以使用递归的方式了
所以只需:
1、重复子问题(函数头的设计)
int pow(x, n);
2、只关心某个子问题在做什么(函数体的设计)
tmp = pow(x, n/2);
return n%2 == 0 ? tmp * tmp : tmp * tmp * x;
3、递归的出口(边界情况)
n == 0 时return 1即可
有几个细节问题:
细节一:平方 n 有可能是负数
此时先将 n 看做正数,再用 1 除这个结果即可
细节二:n 可能是 - 2^31
如果 n 是 -2^31,此时将 n 转化为 2^31 会溢出,因为 int 类型存不下这个数据,int 类型最大值是 2^31 - 1,所以本题中我们需要将 n 的类型设置为 long long
代码如下:
class Solution
{
public:
double myPow(double x, int n)
{
// 处理n为负数的细节问题
return n < 0 ? 1 / pow(x, -(long long)n) : pow(x, n);
}
// n如果为负数,-n可能会溢出,所以这里改为long long类型的数据
double pow(double x, long long n)
{
if(n == 0) return 1.0;
double tmp = pow(x, n / 2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
};
[递归/搜索/回溯]系列之递归题目到此结束啦