递归搜索与回溯算法
递归搜索与回溯算法
名词解释
递归
在解决⼀个规模为n的问题时，如果满⾜以下条件，我们可以使⽤递归来解决：
a. 问题可以被划分为规模更⼩的⼦问题，并且这些⼦问题具有与原问题相同的解决⽅法。
b. 当我们知道规模更⼩的⼦问题（规模为n-1）的解时，我们可以直接计算出规模为n的问题 的解。
c. 存在⼀种简单情况，或者说当问题的规模⾜够⼩时，我们可以直接求解问题。
⼀般的递归求解过程如下：
a. 验证是否满⾜简单情况。
b. 假设较⼩规模的问题已经解决，解决当前问题。
汉诺塔问题
在经典汉诺塔问题中，有 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个。
解法（递归）：
算法思路：
这是⼀道递归⽅法的经典题⽬，我们可以先从最简单的情况考虑：
- 假设n=1，只有⼀个盘⼦，很简单，直接把它从A中拿出来，移到C上；
- 如果n=2呢？这时候我们就要借助B了，因为⼩盘⼦必须时刻都在⼤盘⼦上⾯，共需要3步（为 了⽅便叙述，记A中的盘⼦从上到下为1号，2号）：
a. 1号盘⼦放到B上；
b. 2号盘⼦放到C上；
c. 1号盘⼦放到C上。
⾄此，C中的盘⼦从上到下为1号，2号。
- 如果n>2呢？这是我们需要⽤到n=2时的策略，将A上⾯的两个盘⼦挪到B上，再将最⼤的盘 ⼦挪到C上，最后将B上的⼩盘⼦挪到C上就完成了所有步骤。
因为A中最后处理的是最⼤的盘⼦，所以在移动过程中不存在⼤盘⼦在⼩盘⼦上⾯的情况。
则本题可以被解释为：
-
对于规模为n的问题，我们需要将A柱上的n个盘⼦移动到C柱上。
-
规模为n的问题可以被拆分为规模为n-1的⼦问题：
a. 将A柱上的上⾯n-1个盘⼦移动到B柱上。
b. 将A柱上的最⼤盘⼦移动到C柱上，然后将B柱上的n-1个盘⼦移动到C柱上。
-
当问题的规模变为n=1时，即只有⼀个盘⼦时，我们可以直接将其从A柱移动到C柱.
- 需要注意的是，步骤2.b考虑的是总体问题中的⼦问题b情况。在处理⼦问题的⼦问题b时，我们 应该将A柱中的最上⾯的盘⼦移动到C柱，然后再将B柱上的盘⼦移动到C柱。在处理总体问题 的⼦问题b时，A柱中的最⼤盘⼦仍然是最上⾯的盘⼦，因此这种做法是通⽤的。
算法流程：
递归函数设计：void dfs(vector&A,vector&B,vector&C,int n)
- 返回值：⽆；
- 参数：三个柱⼦上的盘⼦，当前需要处理的盘⼦个数（当前问题规模）。
- 函数作⽤：将A中的上⾯n个盘⼦挪到C中。
递归函数流程：
- 当前问题规模为n=1时，直接将A中的最上⾯盘⼦挪到C中并返回；
- 递归将A中最上⾯的n-1个盘⼦挪到B中；
- 将A中最上⾯的⼀个盘⼦挪到C中；
- 将B中上⾯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>&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);
}
};
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
解法（递归）：
算法思路：
-
递归函数的含义：交给你两个链表的头结点，你帮我把它们合并起来，并且返回合并后的头结点；
-
函数体：选择两个头结点中较⼩的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数 去处理；
-
递归出⼝：当某⼀个链表为空的时候，返回另外⼀个链表。
代码如下：
/**
* 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* list1, ListNode* list2)
{
if(list1==nullptr) return list2;
if(list2==nullptr) return list1;
if(list1->val<list2->val)
{
list1->next=mergeTwoLists(list1->next,list2);
return list1;
}
else
{
list2->next=mergeTwoLists(list1,list2->next);
return list2;
}
}
};