北京建站推广,给静态网站加后台,如果在工商局网站上做股权质押,石景山网站开发算法沉淀——递归 01.汉诺塔问题02.合并两个有序链表03.反转链表04.两两交换链表中的节点05.Pow(x, n) 递归是一种通过调用自身的方式来解决问题的算法。在递归算法中#xff0c;问题被分解为更小的相似子问题#xff0c;然后通过对这些子问题的解进行组合来解决原始问题。递… 算法沉淀——递归 01.汉诺塔问题02.合并两个有序链表03.反转链表04.两两交换链表中的节点05.Pow(x, n) 递归是一种通过调用自身的方式来解决问题的算法。在递归算法中问题被分解为更小的相似子问题然后通过对这些子问题的解进行组合来解决原始问题。递归算法通常包含两个主要部分 基本情况Base Case 定义问题的最小规模直接解答而不再进行递归。基本情况是递归算法的出口防止算法陷入无限递归。递归步骤 在问题规模较大时将问题划分为相似但规模较小的子问题并通过递归调用解决这些子问题。递归调用自身是递归算法的核心。
递归算法在解决许多问题上非常强大尤其是对于那些可以通过分解为子问题并且存在重叠子问题的情况。递归通常使算法更加简洁、清晰但需要谨慎处理基本情况以避免无限递归。
经典的递归问题包括汉诺塔问题、阶乘计算、斐波那契数列等。递归也在许多算法和数据结构中发挥着重要的作用例如树的遍历、图的深度优先搜索等。
如何理解递归
1.递归展开的细节图 2.二叉树中的题目 3.宏观看待递归的过程 1.不要在意递归的细节展开图 2.把递归的函数当成一个黑盒 3.相信这个黑盒一定能完成这个任务 如何写好递归
1.先找到相同的子问题!!!-函数头的设计 2.只关心某一个子问题是如何解决的 -函数体的书写 3.注意一下递归函数的出口即可
01.汉诺塔问题
题目链接https://leetcode.cn/problems/hanota-lcci/
在经典汉诺塔问题中有 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个。
思路
对于这类问题我们可以使用数学中的归结思想先画图分析由1到n的情况我们可以总结出下面这三个步骤 代码
class Solution {void dfs(vectorint A, vectorint B, vectorint C,int n){if(n1){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);}
public:void hanota(vectorint A, vectorint B, vectorint C) {dfs(A,B,C,A.size());}
};定义一个私有的递归函数 dfs该函数将 A 柱上的 n 个盘子通过 B 柱移动到 C 柱。参数 A、B 和 C 分别表示三个柱子的盘子状态n 表示要移动的盘子数量。在递归函数中当只有一个盘子时直接将 A 柱的盘子移到 C 柱上然后返回。在递归函数中先将 A 柱上的 n-1 个盘子通过 C 柱移动到 B 柱上然后将 A 柱上的最后一个盘子移动到 C 柱上最后将 B 柱上的 n-1 个盘子通过 A 柱移动到 C 柱上。在公有函数 hanota 中调用递归函数 dfs传入 A、B、C 三个柱子的状态和盘子数量。
02.合并两个有序链表
题目链接https://leetcode.cn/problems/merge-two-sorted-lists/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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) return list2;if(!list2) return list1;if(list1-vallist2-val){list1-nextmergeTwoLists(list1-next,list2);return list1;}else{list2-nextmergeTwoLists(list2-next,list1);return list2;}}
};如果 list1 为空说明第一个链表为空直接返回 list2。如果 list2 为空说明第二个链表为空直接返回 list1。接下来比较 list1 和 list2 的头节点的值选择较小的节点作为新链表的头节点。如果 list1 的头节点值小于等于 list2 的头节点值将 list1 的下一个节点与 list2 合并并返回 list1 作为新链表的头节点。如果 list2 的头节点值小于 list1 的头节点值将 list2 的下一个节点与 list1 合并并返回 list2 作为新链表的头节点。
03.反转链表
题目链接https://leetcode.cn/problems/reverse-linked-list/
给你单链表的头节点 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
**进阶**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题
思路
若我们直接遍历到最后的节点再逐个向前改变指向在每次接入前一个节点时将它的next指向空最终返回头节点即可。
递归函数的含义交给你⼀个链表的头指针你帮我逆序之后返回逆序后的头结点函数体先把当前结点之后的链表逆序逆序完之后把当前结点添加到逆序后的链表后面即可递归出口当前结点为空或者当前只有⼀个结点的时候不用逆序直接返回
代码
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head||!head-next) return head;ListNode* newhead reverseList(head-next);head-next-nexthead;head-nextnullptr;return newhead;}
};04.两两交换链表中的节点
题目链接https://leetcode.cn/problems/swap-nodes-in-pairs/
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1
输入head [1,2,3,4]
输出[2,1,4,3]示例 2
输入head []
输出[]示例 3
输入head [1]
输出[1] 提示
链表中节点的数目在范围 [0, 100] 内0 Node.val 100
思路
我们将问题划分为子问题先交换当前节点的下两个节点将当前节点的下一个节点作为新的头节点将当前节点的下一个节点指向递归操作的结果返回新的头节点。
代码
class Solution {
public:ListNode* swapPairs(ListNode* head) {// 如果链表为空或者只有一个节点无需交换直接返回原链表头指针if (!head || !head-next)return head;// 递归调用交换当前节点的下两个节点ListNode* tmp swapPairs(head-next-next);// 将当前节点的下一个节点作为新的头节点ListNode* ret head-next;// 将当前节点的下一个节点指向当前节点实现交换head-next-next head;// 将当前节点的下一个节点指向递归操作的结果head-next tmp;// 返回新的头节点return ret;}
};if (!head || !head-next)检查链表是否为空或者只有一个节点。如果是直接返回原链表头指针因为不需要进行交换。ListNode* tmp swapPairs(head-next-next);递归调用swapPairs函数传入当前节点的下两个节点。这样就会从链表的末尾开始每次交换两个相邻的节点然后返回新的头节点。ListNode* ret head-next;将当前节点的下一个节点作为新的头节点因为在交换过程中它会变成新的头节点。head-next-next head;将当前节点的下一个节点指向当前节点实现交换操作。head-next tmp;将当前节点的下一个节点指向递归操作的结果即当前节点的下两个节点交换后的头节点。return ret;返回新的头节点作为上层递归调用的结果。
05.Pow(x, n)
题目链接https://leetcode.cn/problems/powx-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.0-231 n 231-1n 是一个整数要么 x 不为零要么 n 0 。-104 xn 104
思路
这里我们可以使用二分的思想可以快速提高效率例如将3的32次方分为两个3的16次方相乘不断向下递归最终返回相乘结果只不过这里需要注意负数和奇偶次方问题需要单独判断。
代码
class Solution {
public:double myPow(double x, int n) {// 如果指数n为负数将问题转化为计算 x^(-n)即取倒数return n 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);}double Pow(double x, long long n) {// 递归终止条件n为0时任何数的0次方都为1if (n 0) return 1.0;// 递归调用计算 x^(n/2)double tmp Pow(x, n / 2);// 如果n为奇数返回 tmp * tmp * xif (n % 2)return tmp * tmp * x;else // 如果n为偶数返回 tmp * tmpreturn tmp * tmp;}
};return n 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);根据指数n的正负情况决定调用正指数或者取倒数的递归函数。当n为负数时将其转化为正数计算并返回结果的倒数。double Pow(double x, long long n)递归函数用于计算 x^n。if (n 0) return 1.0;递归终止条件。当指数n为0时任何数的0次方都为1。double tmp Pow(x, n / 2);递归调用计算 x^(n/2)。这里利用了指数幂的性质将问题规模减半减少了计算量。if (n % 2)判断n是否为奇数。return tmp * tmp * x;如果n为奇数返回 tmp * tmp * x这是因为 x^n (x(n/2))2 * x。 n) : Pow(x, n);根据指数n的正负情况决定调用正指数或者取倒数的递归函数。当n为负数时将其转化为正数计算并返回结果的倒数。double Pow(double x, long long n)递归函数用于计算 x^n。if (n 0) return 1.0;递归终止条件。当指数n为0时任何数的0次方都为1。double tmp Pow(x, n / 2);递归调用计算 x^(n/2)。这里利用了指数幂的性质将问题规模减半减少了计算量。if (n % 2)判断n是否为奇数。return tmp * tmp * x;如果n为奇数返回 tmp * tmp * x这是因为 x^n (x(n/2))2 * x。return tmp * tmp;如果n为偶数返回 tmp * tmp这是因为 x^n (x(n/2))2。
