【算法专题】递归算法
递归
- 递归
- 1. 汉诺塔问题
- 2. 合并两个有序链表
- 3. 反转链表
- 4. 两两交换链表中的节点
- 5. Pow(x, n) --- 快速幂
递归
在解决⼀个规模为 n 的问题时，如果满足以下条件，我们可以使用递归来解决：
（图片来源网络，侵删）- 问题可以被划分为规模更小的子问题，并且这些子问题具有与原问题相同的解决⽅法。
- 当我们知道规模更小的子问题（规模为 n - 1）的解时，我们可以直接计算出规模为 n 的问题的解。
- 存在⼀种简单情况，或者说当问题的规模足够小时，我们可以直接求解问题。⼀般的递归求解过程如下：
a. 验证是否满足简单情况。
b. 假设较小规模的问题已经解决，解决当前问题
1. 汉诺塔问题
题目链接 -> Leetcode 面试题 08.06.汉诺塔问题
Leetcode 面试题 08.06.汉诺塔问题
题目：在经典汉诺塔问题中，有 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 柱中的最大盘子仍然是最上面的盘子，因此这种做法是通用的。
代码如下：
class Solution { public: void hanota(vector& A, vector& B, vector& C) { // 将 A 上的 A.size() 个盘子借助 B 移到 C 上 dfs(A, B, C, A.size()); } void dfs(vector& A, vector& B, vector& 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(); // 将 B 上的 n - 1 个盘子借助 A 移到 C 上 dfs(B, A, C, n - 1); } };2. 合并两个有序链表
题目链接 - > Leetcode -21.合并两个有序链表
Leetcode -21.合并两个有序链表
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 val)
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
3. 反转链表
题目链接 -> Leetcode -206.反转链表
Leetcode -206.反转链表
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]
示例 2：
输入：head = [1, 2]
输出：[2, 1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是[0, 5000]
- 5000 next);
head->next->next = head;
head->next = nullptr;
return ret;
}
};
4. 两两交换链表中的节点
题目链接 -> Leetcode -24.两两交换链表中的节点
Leetcode -24.两两交换链表中的节点
题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1, 2, 3, 4]
输出：[2, 1, 4, 3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
- 链表中节点的数目在范围[0, 100] 内
- 0 next->next);
ListNode* ret = head->next; // 先存一下返回的头节点
head->next->next = head;
head->next = tmp;
return ret;
}
};
5. Pow(x, n) — 快速幂
题目链接 -> Leetcode -50.Pow(x, n)
Leetcode -50.Pow(x, n)
题目：实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 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
提示：
- 100.0
- 2^31
