Offer必备算法07_递归_五道力扣题详解（由易到难）

目录

递归算法原理

①力扣面试题 08.06. 汉诺塔问题

解析代码

②力扣21. 合并两个有序链表

解析代码

③力扣206. 反转链表

解析代码

④力扣24. 两两交换链表中的节点

解析代码

⑤力扣50. Pow(x, n)

解析代码

本篇完。

---

递归算法原理

        递归算法个人经验：给定一个任务，相信递归函数一定能解决这个任务，根据任务所需的东西，给出函数参数，然后实现函数内容，最后找出口。

        递归算法是指在解决问题的过程中，不断地调用自身来解决子问题的一种算法。其基本思想是将原问题转化为同类更小的子问题，直到达到最小可解问题的情况，然后再将子问题的答案合并起来解决原问题。递归算法基本设计原理是分而治之，即将问题分成小问题分别解决，最终将所有小问题的答案合并成原问题的答案。

        递归算法适用于问题具有递归性质的场景。这些问题通常可以分解为一些同样类型但规模更小的子问题，递归算法可以通过递归调用来解决这些子问题，再将子问题的答案组合成原问题的答案。例如，计算斐波那契数列，求解汉诺塔问题等等都可以用递归算法来解决。

        在使用递归算法中，首先要注意递归终止条件的设置。如果没有正确的终止条件，递归算法将会无限循环，导致程序崩溃。其次，注意递归调用时的参数传递问题，要确保每次递归调用时传递的参数和问题规模正确。此外，在递归算法中，可能会出现栈溢出的问题，特别是问题规模很大的情况下，应注意算法的时间和空间复杂度，以避免因内存不足而引起的程序异常。

递归 VS 迭代（循环）：

递归和迭代本质都是解决重复的子问题，所以代码可以相互转换。

递归 VS 深搜（dfs）：

递归的展开图，其实就是对一颗树做一次深度优先遍历。

什么时候用递归方便，什么时候用迭代方便：

当递归展开图复杂时用递归（多叉树等），当递归展开图简单时用迭代（一条路径等）。

---

①力扣面试题 08.06. 汉诺塔问题

面试题 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]

提示:

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

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {

};

---

解析代码

 一道递归方法的经典题目，看看图：

假设 n = 1,只有一个盘子，很简单，直接把它从 A 中拿出来，移到 C 上；

如果 n = 2 呢？这时候我们就要借助 B 了，因为小盘子必须时刻都在大盘子上面，共需要 4 步。

如果 n > 2 呢？思路和上面是一样的，我们把 n 个盘子也看成两个部分，一部分有 1 个盘子，另一部分有 n - 1 个盘子。

        在思考这个问题的时候，就将最初的 n 个盘子从 A 移到 C 的问题，转化成了将 n - 1 个盘子从 A 移到 C 的问题， 依次类推，直至转化成 1 个盘子的问题时，问题也就解决了。这就是分治的思想。

        而实现分治思想的常用方法就是递归。不难发现，如果原问题可以分解成若干个与原问题结构相同但规模较小的子问题时，往往可以用递归的方法解决。具体解决办法如下：

n = 1 时，直接把盘子从 A 移到 C；
n > 1 时，
先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
再将最大的盘子从 A 移到 C；
再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。

递归法：给定一个任务，相信递归一定能解决这个任务，然后找出口：

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());
    }

    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
    {   // 递归：A盘 借助 B盘 转移A最上面n-1个盘 到C盘
        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);
    }
};

---

②力扣21. 合并两个有序链表

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 均按 非递减顺序 排列

/**
 * 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) {
    
    }
};

---

解析代码

        以前C语言用迭代（循环）写过了，递归的思路就是把小结点链接到这个小结点的下一个和另一条结点链接好的链表（递归），然后返回小的结点，出口就是有一个链表为空，返回另一个。

 

上图就是让①链接到绿色链接好的链表上。

/**
 * 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) {
        return  _mergeTwoLists(list1, list2);
    }

    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(list2->next, list1);
            return list2;
        }
    }
};

---

③力扣206. 反转链表

206. 反转链表

LCR 024. 反转链表

难度 简单

给你单链表的头节点 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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

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

    }
};

---

解析代码

这次循环迭代也写过了，且用循环更好，但练下递归：

左图就是把紫矿里的链表反转后链接到head，head再指向空，右图就是把链表看成一棵树。

/**
 * 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* newHead = reverseList(head->next); // 把head后面的都递归好
        head->next->next = head; // 让叶子结点指回去
        head->next = nullptr; // 为了统一步骤
        return newHead;

        /*ListNode *newHead = nullptr, *cur = head;
        while(cur)
        {
            ListNode *curNext = cur->next;
            cur->next = newHead; // 头插
            newHead = cur; // 往后走
            cur = curNext;
        }
        return newHead;*/
    }
};

---

④力扣24. 两两交换链表中的节点

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

难度 中等

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

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

    }
};

---

解析代码

递归是和反转链表一样的思路：

把下图紫框中链表两两交换，然后再把剩下的两个结点交换。

/**
 * 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); // 把两个结点之外的看成另一部分
        head->next->next = head;
        auto ret = head->next; // 保存一下要返回的结点
        head->next = tmp;
        return ret;
    }
};

---

⑤力扣50. Pow(x, n)

50. Pow(x, n)

难度 中等

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。

示例 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/2^2 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• n 是一个整数
• 要么 x 不为零，要么 n > 0 。
• -10^4 <= xn <= 10^4

class Solution {
public:
    double myPow(double x, int n) {

    }
};

---

解析代码

循环迭代会超时，递归就是先求n/2次方，然后分情况讨论，要注意边界情况：

class Solution {
public:
    double myPow(double x, int n) { // long long 防-2^31变成正数溢出
        return n < 0 ? 1 / _myPow(x, -(long long)n) : _myPow(x, n);
    }

    double _myPow(double x, long long n)
    {
        if(n == 0)
            return 1;
        double tmp = myPow(x, n / 2);
        return n % 2 == 0 ? tmp*tmp : tmp*tmp*x;
    }
};

---

本篇完。

下一部分是二叉树的深搜dfs。