做影视后期有哪些资源网站,佛山专业做淘宝网站,南沙区做网站公司,运营管理培训✨✨✨学习的道路很枯燥#xff0c;希望我们能并肩走下来! 目录 前言 一 深入理解递归 二 迭代VS递归 三 递归算法题目解析 3.1 汉诺塔问题 3.2 合并两个有序链表 3.3 反转链表 3.4 两两交换链表中的节点 3.5 Pow#xff08;x#xff0c;n#xff09;#xff08;快速幂)… ✨✨✨学习的道路很枯燥希望我们能并肩走下来! 目录 前言 一 深入理解递归 二 迭代VS递归 三 递归算法题目解析 3.1 汉诺塔问题 3.2 合并两个有序链表 3.3 反转链表 3.4 两两交换链表中的节点 3.5 Powxn快速幂) 四 总结 总结 前言
作为递归、搜索与回溯算法系列的第一篇本篇详细介绍了递归算法的使用让使用者了解递归运算而不是仅仅停留在表面 文章可能出现错误如有请在评论区指正让我们一起交流共同进步 一 深入理解递归 二 迭代VS递归 三 递归算法题目解析
3.1 汉诺塔问题
面试题 08.06. 汉诺塔问题 - 力扣LeetCode 我们简单取1到4个圆盘进行移动我们从宏观角度发现这是一个重复子问题 class Solution {
public:void move(vectorint A, vectorint B, vectorint C,int n){if(n 1){C.push_back(A.back());A.pop_back();return;}move(A,C,B,n-1);C.push_back(A.back());A.pop_back();move(B,A,C,n-1);}void hanota(vectorint A, vectorint B, vectorint C) {int n A.size();move(A,B,C,n);}
}; 如果我们在笔试中遇到的只需要保证能通过就行
不讲武德版
class Solution {
public:void hanota(vectorint A, vectorint B, vectorint C) {C A;}
}; 3.2 合并两个有序链表
21. 合并两个有序链表 - 力扣LeetCode 我们之前是使用迭代循环来做的
迭代
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{ListNode* l1 list1;ListNode* l2 list2;ListNode* newHead NULL;ListNode* newTail NULL;newHead newTail (ListNode*)malloc(sizeof(ListNode));if(l1NULL){return l2;}if(l2NULL){return l1;}while(l1l2){if(l1-vall2-val){newTail-nextl1;newTailnewTail-next;l1l1-next;}else{newTail-nextl2;newTailnewTail-next;l2l2-next;}}if(l1){newTail-nextl1;}else{newTail-nextl2;}ListNode* ret newHead-next;free(newHead);return ret;
}
递归 /*** 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;}}
};
3.3 反转链表
206. 反转链表 - 力扣LeetCode /*** 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* newNode reverseList(head-next);head-next-next head;head-next nullptr;return newNode;}
};
3.4 两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣LeetCode /*** 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;auto newNode swapPairs(head-next-next);auto ret head-next;head-next-next head;head-next newNode;return ret;}
};
3.5 Powxn快速幂)
50. Pow(x, n) - 力扣LeetCode class Solution {
public:double myPow(double x, int n) {return n0 ? 1.0/Pow(x,-(long long)n) : Pow(x,n);}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;}
}; 用long long避免int无法存n为2的-31次方 四 总结 1. 从题目发掘出重复的子问题 2. 只针对某一子问题考虑解决方法 3. 注意递归出口 总结
✨✨✨各位读友本篇分享到内容是否更好的让你理解递归算法如果对你有帮助给个赞鼓励一下吧 世上没有绝望的处境只有对处境绝望的人。 感谢每一位一起走到这的伙伴我们可以一起交流进步一起加油吧
