【算法专题】递归算法

这篇具有很好参考价值的文章主要介绍了【算法专题】递归算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

递归

在解决⼀个规模为 n 的问题时,如果满足以下条件,我们可以使用递归来解决:

  1. 问题可以被划分为规模更小的子问题,并且这些子问题具有与原问题相同的解决⽅法。
  2. 当我们知道规模更小的子问题(规模为 n - 1)的解时,我们可以直接计算出规模为 n 的问题的解。
  3. 存在⼀种简单情况,或者说当问题的规模足够小时,我们可以直接求解问题。⼀般的递归求解过程如下:
    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 中最后处理的是最大的盘子,所以在移动过程中不存在大盘子在小盘子上面的情况。
则本题可以被解释为:

  1. 对于规模为 n 的问题,我们需要将 A 柱上的 n 个盘子移动到C柱上。
  2. 规模为 n 的问题可以被拆分为规模为 n-1 的子问题:
    a. 将 A 柱上的上面 n-1 个盘子移动到B柱上。
    b. 将 A 柱上的最大盘子移动到 C 柱上,然后将 B 柱上的 n-1 个盘子移动到C柱上。
  3. 当问题的规模变为 n=1 时,即只有一个盘子时,我们可以直接将其从 A 柱移动到 C 柱。
  • 需要注意的是,步骤 2.b 考虑的是总体问题中的子问题 b 情况。在处理子问题的子问题 b 时,我们应该将 A 柱中的最上面的盘子移动到 C 柱,然后再将 B 柱上的盘子移动到 C 柱。在处理总体问题的子问题 b 时,A 柱中的最大盘子仍然是最上面的盘子,因此这种做法是通用的。

代码如下:文章来源地址https://www.toymoban.com/news/detail-772296.html

		class Solution {
		public:
		    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
		    {   
		        // 将 A 上的 A.size() 个盘子借助 B 移到 C 上
		        dfs(A, B, C, A.size());
		    }
		
		    void dfs(vector<int>& A, vector<int>& B, vector<int>& 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 <= 100
  • l1 和 l2 均按 非递减顺序 排列

思路:

  1. 递归函数的含义:交给你两个链表的头结点,把它们合并起来,并且返回合并后的头结点;
  2. 函数体:选择两个头结点中较小的结点作为最终合并后的头结点,然后将剩下的链表交给递归函数去处理;
  3. 递归出口:当某一个链表为空的时候,返回另外一个链表。

代码如下:

		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

思路:

  1. 递归函数的含义:交给你一个链表的头指针,逆序之后,返回逆序后的头结点;
  2. 函数体:先把当前结点之后的链表逆序,逆序完之后,把当前结点添加到逆序后的链表后面即可;
  3. 递归出口:当前结点为空或者当前只有一个结点的时候,不用逆序,直接返回。

代码如下:

		/**
		 * 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

思路:

  1. 递归函数的含义:交给你一个链表,将这个链表两两交换一下,然后返回交换后的头结点;
  2. 函数体:先去处理一下第二个结点往后的链表,然后再把当前的两个结点交换一下,连接上后面处理后的链表;
  3. 递归出口:当前结点为空或者当前只有一个结点的时候,不用交换,直接返回。

代码如下:

		/**
		 * 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.0
  • 2^31 <= n <= 2^31 - 1
  • n 是一个整数
  • 要么 x 不为零,要么 n > 0 。
  • -10^4 <= x^n <= 10^4

思路:

  1. 递归函数的含义:求出 x 的 n 次方是多少,然后返回;
  2. 函数体:先求出 x 的 n / 2 次方是多少,然后根据 n 的奇偶,得出 x 的 n 次方是多少;
  3. 递归出口:当 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));
		    }
		};

到了这里,关于【算法专题】递归算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【优选算法专栏】专题九:链表--------两数之和

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:算法从入门到精通 🚚代码仓库:小小unicorn的代码仓库

    2024年02月21日
    浏览(49)
  • DFS:从递归去理解深度优先搜索

    . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode)  1、迭代 2、递归  

    2024年04月17日
    浏览(55)
  • 递归、搜索与回溯算法(专题一:递归)

    往期文章(希望小伙伴们在看这篇文章之前,看一下往期文章) (1)递归、搜索与回溯算法(专题零:解释回溯算法中涉及到的名词)【回溯算法入门必看】-CSDN博客 接下来我会用几道题,来让同学们利用我在专题零中提到的 递归的宏观思想 来解决这些题目。 目录 1. 汉诺

    2024年01月25日
    浏览(43)
  • 【算法专题】递归算法

    在解决⼀个规模为 n 的问题时,如果满足以下条件,我们可以使用递归来解决: 问题可以被划分为规模更小的子问题,并且这些子问题具有与原问题相同的解决⽅法。 当我们知道规模更小的子问题(规模为 n - 1)的解时,我们可以直接计算出规模为 n 的问题的解。 存在⼀种

    2024年02月03日
    浏览(37)
  • C++斩题录|递归专题 | leetcode50. Pow(x, n)

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(30)
  • 【优选算法专栏】专题十六:BFS解决最短路问题---前言

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:算法从入门到精通 🚚代码仓库:小小unicorn的代码仓库

    2024年04月15日
    浏览(50)
  • 【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs(8)

    目录 写在前面: 题目:1114. 棋盘问题 - AcWing题库 题目描述: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要, 所以,为了学好深度优先搜

    2023年04月09日
    浏览(38)
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(5)

    目录 写在前面: 题目:P2036 [COCI2008-2009#2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要,

    2023年04月13日
    浏览(49)
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)

    目录 写在前面: 题目:P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤

    2023年04月08日
    浏览(45)
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(1)

    目录 写在前面: 题目:P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要

    2024年01月23日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包