算法沉淀——递归(leetcode真题剖析)

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

算法沉淀——递归(leetcode真题剖析),算法沉淀,算法,leetcode,职场和发展


递归是一种通过调用自身的方式来解决问题的算法。在递归算法中,问题被分解为更小的相似子问题,然后通过对这些子问题的解进行组合来解决原始问题。递归算法通常包含两个主要部分:
  1. 基本情况(Base Case): 定义问题的最小规模,直接解答而不再进行递归。基本情况是递归算法的出口,防止算法陷入无限递归。
  2. 递归步骤: 在问题规模较大时,将问题划分为相似但规模较小的子问题,并通过递归调用解决这些子问题。递归调用自身是递归算法的核心。

递归算法在解决许多问题上非常强大,尤其是对于那些可以通过分解为子问题并且存在重叠子问题的情况。递归通常使算法更加简洁、清晰,但需要谨慎处理基本情况,以避免无限递归。

经典的递归问题包括汉诺塔问题、阶乘计算、斐波那契数列等。递归也在许多算法和数据结构中发挥着重要的作用,例如树的遍历、图的深度优先搜索等。

如何理解递归?

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]

提示:

  1. A中盘子的数目不大于14个。

思路

对于这类问题我们可以使用数学中的归结思想,先画图分析由1到n的情况,我们可以总结出下面这三个步骤

算法沉淀——递归(leetcode真题剖析),算法沉淀,算法,leetcode,职场和发展

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

class Solution {
    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;
        }

        dfs(A,C,B,n-1);
        C.push_back(A.back());
        A.pop_back();
        dfs(B,A,C,n-1);

    }
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A,B,C,A.size());
    }
};
  1. 定义一个私有的递归函数 dfs,该函数将 A 柱上的 n 个盘子通过 B 柱移动到 C 柱。参数 ABC 分别表示三个柱子的盘子状态,n 表示要移动的盘子数量。
  2. 在递归函数中,当只有一个盘子时,直接将 A 柱的盘子移到 C 柱上,然后返回。
  3. 在递归函数中,先将 A 柱上的 n-1 个盘子通过 C 柱移动到 B 柱上,然后将 A 柱上的最后一个盘子移动到 C 柱上,最后将 B 柱上的 n-1 个盘子通过 A 柱移动到 C 柱上。
  4. 在公有函数 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 <= 100
  • l1l2 均按 非递减顺序 排列

思路

这里我们如果划分为子问题,每次就拿出最小的那个节点当做头节点,拼接剩下的当前节点尾部的节点和另一个链表的头节点相比较的更小的点,最后谁被拼接完了,就直接拼接另一条链表剩下的,这样不难看出,每次的步骤都是重复的,于是我们可以使用递归的思想来解决这道问题。

代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;

        if(list1->val<=list2->val){
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }else{
            list2->next=mergeTwoLists(list2->next,list1);
            return list2;
        }
    }
};
  1. 如果 list1 为空,说明第一个链表为空,直接返回 list2
  2. 如果 list2 为空,说明第二个链表为空,直接返回 list1
  3. 接下来比较 list1list2 的头节点的值,选择较小的节点作为新链表的头节点。
  4. 如果 list1 的头节点值小于等于 list2 的头节点值,将 list1 的下一个节点与 list2 合并,并返回 list1 作为新链表的头节点。
  5. 如果 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指向空,最终返回头节点即可。

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

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next) return head;

        ListNode* newhead = reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;

        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;
    }
};
  1. if (!head || !head->next):检查链表是否为空或者只有一个节点。如果是,直接返回原链表头指针,因为不需要进行交换。
  2. ListNode* tmp = swapPairs(head->next->next);:递归调用swapPairs函数,传入当前节点的下两个节点。这样就会从链表的末尾开始,每次交换两个相邻的节点,然后返回新的头节点。
  3. ListNode* ret = head->next;:将当前节点的下一个节点作为新的头节点,因为在交换过程中,它会变成新的头节点。
  4. head->next->next = head;:将当前节点的下一个节点指向当前节点,实现交换操作。
  5. head->next = tmp;:将当前节点的下一个节点指向递归操作的结果,即当前节点的下两个节点交换后的头节点。
  6. 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-1
  • n 是一个整数
  • 要么 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次方都为1
        if (n == 0) 
            return 1.0;
        
        // 递归调用,计算 x^(n/2)
        double tmp = Pow(x, n / 2);
        
        // 如果n为奇数,返回 tmp * tmp * x
        if (n % 2)
            return tmp * tmp * x;
        else // 如果n为偶数,返回 tmp * tmp
            return tmp * tmp;
    }
};
  1. return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);:根据指数n的正负情况,决定调用正指数或者取倒数的递归函数。当n为负数时,将其转化为正数计算,并返回结果的倒数。
  2. double Pow(double x, long long n):递归函数,用于计算 x^n。
  3. if (n == 0) return 1.0;:递归终止条件。当指数n为0时,任何数的0次方都为1。
  4. double tmp = Pow(x, n / 2);:递归调用,计算 x^(n/2)。这里利用了指数幂的性质,将问题规模减半,减少了计算量。
  5. if (n % 2):判断n是否为奇数。
  6. return tmp * tmp * x;:如果n为奇数,返回 tmp * tmp * x,这是因为 x^n = (x(n/2))2 * x。
    n) : Pow(x, n);`:根据指数n的正负情况,决定调用正指数或者取倒数的递归函数。当n为负数时,将其转化为正数计算,并返回结果的倒数。
  7. double Pow(double x, long long n):递归函数,用于计算 x^n。
  8. if (n == 0) return 1.0;:递归终止条件。当指数n为0时,任何数的0次方都为1。
  9. double tmp = Pow(x, n / 2);:递归调用,计算 x^(n/2)。这里利用了指数幂的性质,将问题规模减半,减少了计算量。
  10. if (n % 2):判断n是否为奇数。
  11. return tmp * tmp * x;:如果n为奇数,返回 tmp * tmp * x,这是因为 x^n = (x(n/2))2 * x。
  12. return tmp * tmp;:如果n为偶数,返回 tmp * tmp,这是因为 x^n = (x(n/2))2。

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

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

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

相关文章

  • 算法沉淀——贪心算法五(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/jump-game-ii/ 给定一个长度为 n 的 0 索引 整数数组 nums 。初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处: 0 = j = nums[i] i + j n 返回到达 nums[n - 1] 的最小跳跃次

    2024年04月11日
    浏览(49)
  • 算法沉淀——贪心算法二(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 示

    2024年03月19日
    浏览(50)
  • 算法沉淀——贪心算法七(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/integer-replacement/ 给定一个正整数 n ,你可以做如下操作: 如果 n 是偶数,则用 n / 2 替换 n 。 如果 n 是奇数,则可以用 n + 1 或 n - 1 替换 n 。 返回 n 变为 1 所需的 最小替换次数 。 示例 1: 示例 2: 示例 3: 提示: 1 = n = 2^31 - 1 思路 这里我们

    2024年03月23日
    浏览(48)
  • 算法沉淀——多源 BFS(leetcode真题剖析)

    多源 BFS 是指从多个源点同时进行广度优先搜索的算法。在传统的 BFS 中,我们通常从一个起始点开始,逐层遍历所有的相邻节点。而在多源 BFS 中,我们可以同时从多个源点开始,从这些源点出发,逐层向外扩展,直到达到目标或者遍历完整个图。 多源 BFS 可以用于解决一些

    2024年02月19日
    浏览(44)
  • 算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

    BFS(广度优先搜索)解决 Flood Fill 算法的基本思想是通过从起始点开始,逐层向外扩展,访问所有与起始点相连且具有相同特性(颜色等)的区域。在 Flood Fill 中,通常是通过修改图像的像素颜色。 下面是 BFS 解决 Flood Fill 算法的步骤: 初始化: 将起始点的颜色修改为新的

    2024年02月20日
    浏览(38)
  • 算法沉淀——优先级队列(堆)(leetcode真题剖析)

    优先队列(Priority Queue)是一种抽象数据类型,它类似于队列(Queue),但是每个元素都有一个关联的优先级。在优先队列中,元素按照优先级从高到低(或从低到高)排列,高优先级的元素先出队。这种数据结构可以用堆(Heap)来实现。 堆是一种二叉树结构,有两种主要类

    2024年02月22日
    浏览(47)
  • 算法沉淀——BFS 解决拓扑排序(leetcode真题剖析)

    Breadth-First Search (BFS) 在拓扑排序中的应用主要是用来解决有向无环图(DAG)的拓扑排序问题。拓扑排序是对有向图中所有节点的一种线性排序,使得对于每一条有向边 (u, v),节点 u 在排序中都出现在节点 v 的前面。如果图中存在环路,则无法进行拓扑排序。 BFS 解决拓扑排序

    2024年02月21日
    浏览(40)
  • 算法沉淀——BFS 解决最短路问题(leetcode真题剖析)

    BFS (广度优先搜索)是解决最短路径问题的一种常见算法。在这种情况下,我们通常使用BFS来查找从一个起始点到目标点的最短路径。 具体步骤如下: 初始化: 从起始点开始,将其放入队列中,并标记为已访问。 BFS遍历: 不断从队列中取出顶点,然后探索与该顶点相邻且

    2024年02月20日
    浏览(39)
  • 算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/permutations/ 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 6 -10 = nums[i] = 10 nums 中的所有整数 互不相同 思路 这是一个典型的回溯问题,需要在每

    2024年02月21日
    浏览(61)
  • [职场] 会计学专业学什么 #其他#知识分享#职场发展

    会计学专业学什么 会计学专业属于工商管理学科下的一个二级学科,本专业培养具备财务、管理、经济、法律等方面的知识和能力,具有分析和解决财务、金融问题的基本能力,能在企、事业单位及政府部门从事会计实务以及教学、科研方面工作的工商管理学科高级专门人才

    2024年02月20日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包