欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 财经 > 金融 > 算法专题十一: 基础递归

算法专题十一: 基础递归

2024/11/29 17:18:58 来源:https://blog.csdn.net/2201_75644377/article/details/143973652  浏览:    关键词:算法专题十一: 基础递归

目录

  • 1. 汉诺塔
  • 2. 合并两个有序链表
  • 3. 反转链表
  • 4. 两两交换链表中的节点
  • 5. Pow(x, n)

1. 汉诺塔

题目链接: Leetcode汉诺塔

在这里插入图片描述

算法原理:

递归:宏观视角理解递归
本道题为什么能用递归? 让我们逐一分析
首先思考我们如何来解决汉诺塔问题:

  1. 当N = 1 时, 我们仅需将A上的盘子直接挪到C即可

在这里插入图片描述

  1. 当N = 2时, 把A上的盘子转移到B上,再把A的最后一个盘子转移到C上,最后再把B上的盘子转移到C上。

在这里插入图片描述
3. 当N = 3时跟N = 2的思路一样, 先把B上的n-1个盘子转移到B上(借助C),再把A上的最后一个盘子转移到C上, 最后将B上的盘子转移到C上(借助A),

在这里插入图片描述
4. 当N = 4时,
在这里插入图片描述

解决大问题时具有相同的子问题时,解决子问题又出现相同类型的子问题时就可以使用递归。
根据重复的子问题,设计函数头
只根据某一个具体的子问题在做什么,设计函数体

编写代码:

class Solution {
public:void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {int n = a.size();dfs(a, b, c, n);}void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n){//递归出口,当n == 1时就可以直接转移,无需借助其他柱子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);}
};

2. 合并两个有序链表

题目链接:合并两个有序链表

在这里插入图片描述

算法原理:

先比大小,让小的那个节点连上后面合并好的链表。

在这里插入图片描述

/*** 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* l1, ListNode* l2) {if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;if(l1->val < l2->val){l1->next = mergeTwoLists(l1->next, l2);return l1;}else{l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};

3. 反转链表

在这里插入图片描述
算法原理:

从宏观角度看待问题:

  1. 让当前节点后面的节点先逆置, 并且把新的头节点返回
  2. 让当前节点添加到新的节点后面即可。

边界情况:
当链表为空或者只有一个节点, 返回当前节点即可,即为递归出口。

在这里插入图片描述

编写代码:

/*** 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* newhaed = reverseList(head->next);head->next->next = head;head->next = nullptr;return newhaed;}
};

4. 两两交换链表中的节点

题目链接: 两两交换链表中的节点

在这里插入图片描述
算法原理:

  1. 先将当前两个节点之后的节点进行交换, 然后在交换当前节点
  2. 如果当前节点为空或者只有一个节点就不用交换了, 直接返回即可
  3. 让当前节点的下一个节点的next指向当前节点, 并且让当前节点指向tmp即上一层已经交换好的链表,并且返回当前节点的下一个节点。

在这里插入图片描述

编写代码:

/*** 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* next = head->next;head->next->next = head;head->next = tmp;return next;}
};

5. Pow(x, n)

题目链接: Pow(x, n)

在这里插入图片描述

算法原理:这个就是求x的n次方, 如果使用暴力解法, 当n特别大时是会超时的, ,那么我们采用第二种思路, 递归的思想

  1. 如果求3的16次方, 我们可以先算出3的8次方*3的8次方, 按照下面的图进行求解
  2. 求解子问题设计函数头 就转化为定义一个函数, 你给我返回它的一半的值,
    如果是奇数就再乘以当前的数, 如果是偶数就直接tmp*tmp即为结果
  3. 递归的出口就是当n == 0时, 返回1即可。注意处理负数的情况。
    在这里插入图片描述

编写代码:

class Solution {
public:double myPow(double x, int n) {return n < 0 ? 1 / 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;}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com