网站建设电子合同模板,深圳龙华区租房,网站服务器架设,网站设计动图怎么建设递归 递归1. 汉诺塔问题2. 合并两个有序链表3. 反转链表4. 两两交换链表中的节点5. Pow(x, n) --- 快速幂 递归
在解决⼀个规模为 n 的问题时#xff0c;如果满足以下条件#xff0c;我们可以使用递归来解决#xff1a;
问题可以被划分为规模更小的子问题#xff0c;并且… 递归 递归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柱上。当问题的规模变为 n1 时即只有一个盘子时我们可以直接将其从 A 柱移动到 C 柱。
需要注意的是步骤 2.b 考虑的是总体问题中的子问题 b 情况。在处理子问题的子问题 b 时我们应该将 A 柱中的最上面的盘子移动到 C 柱然后再将 B 柱上的盘子移动到 C 柱。在处理总体问题的子问题 b 时A 柱中的最大盘子仍然是最上面的盘子因此这种做法是通用的。
代码如下 class Solution {public:void hanota(vectorint A, vectorint B, vectorint C) { // 将 A 上的 A.size() 个盘子借助 B 移到 C 上dfs(A, B, C, A.size());}void dfs(vectorint A, vectorint B, vectorint 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 Node.val 100l1 和 l2 均按 非递减顺序 排列
思路
递归函数的含义交给你两个链表的头结点把它们合并起来并且返回合并后的头结点函数体选择两个头结点中较小的结点作为最终合并后的头结点然后将剩下的链表交给递归函数去处理递归出口当某一个链表为空的时候返回另外一个链表。
代码如下 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;}}};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 Node.val 5000
思路
递归函数的含义交给你一个链表的头指针逆序之后返回逆序后的头结点函数体先把当前结点之后的链表逆序逆序完之后把当前结点添加到逆序后的链表后面即可递归出口当前结点为空或者当前只有一个结点的时候不用逆序直接返回。
代码如下 /*** 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) {if(head nullptr || head-next nullptr) return head;ListNode* ret reverseList(head-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 Node.val 100
思路
递归函数的含义交给你一个链表将这个链表两两交换一下然后返回交换后的头结点函数体先去处理一下第二个结点往后的链表然后再把当前的两个结点交换一下连接上后面处理后的链表递归出口当前结点为空或者当前只有一个结点的时候不用交换直接返回。
代码如下 /*** 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* tmp swapPairs(head-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 x 100.02^31 n 2^31 - 1n 是一个整数要么 x 不为零要么 n 0 。-10^4 x^n 10^4
思路
递归函数的含义求出 x 的 n 次方是多少然后返回函数体先求出 x 的 n / 2 次方是多少然后根据 n 的奇偶得出 x 的 n 次方是多少递归出口当 n 为 0 的时候返回 1 即可。
代码如下 class Solution {public:// 2^10 2^5 * 2^5 (2^2 * 2^2 * 2) * (2^2 * 2^2 * 2) ...double _pow(double x, int n) {if(n 0) return 1.0;double tmp _pow(x, n / 2);return n % 2 0? tmp * tmp : tmp * tmp * x;}double myPow(double x, int n){return n 0? _pow(x, n) : 1.0 / _pow(x, abs(n));}};
