【递归，搜索与回溯算法篇】专题（一） - 递归

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

提示：

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

题目解析：

• 小规模问题分析

当N = 1时：直接移动

//将盘子直接从a移动到c
a -> c

当N = 2时:先将最小的盘子从a移到b,再将大盘从a移到c,再将小盘从b移到c。

//先把小盘子从a移动到b
a -> b
//再把大盘子从a移动到c
a -> c
//最后把小盘子从b移动到c
b -> c

当N = 3时：先将前两个盘子借助c从a移动到b,再将最大的盘子移动到c，将前两个盘子借助a从b移动到c。

//将前两个盘子从a移动到b(借助c)
a -> c
a -> b
c -> b
//将最大的盘子从a移动到c
a -> c
//将b上面的两个盘子从b移动到c(借助a)
b -> a
b -> c
a -> c

• 这道题为什么可以使用递归？ 解决大问题时出现了相同的子问题，在解决子问题时又出现了相同的子问题。
• 如何编写递归代码？ 1.重复子问题 -> 函数头 函数头：将x柱子上的一堆盘子，借助y柱子，转移到z柱子上。n代表盘子的数量 void dfs(x , y , z , int n ) 2.只关心某一个子问题在做什么 -> 函数体 函数体： 将x柱子上的n-1个盘子借助z柱子放到y柱子上 dfs(x , z , y , n-1) 将x柱子最大的盘子放到z柱子上 x.back() -> z 将y柱子上的n-1个盘子借助x盘子放到z柱子上 dfs(y , x , z , n-1) 当剩最后一个盘子时，直接从a柱子移动到c柱子 x.back -> z

代码实现：

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

题目解析： 这道题让我们将两个升序链表合并为一个新的升序链表，我们用递归的解法就是先找出l1和l2头节点小的那一个，让它作为新的链表的头节点。然后在剩下的两个链表中继续去找小的那个作为链表的头节点。此时就出现了相同的子问题。

• 相同的子问题 -> 函数头的设计 Node* dfs(Node* l1,Node* l2)
• 某个子问题在干什么 -> 函数体的设计 先判断两个头指针的大小，谁小谁当最后的头指针 ①比大小 ②让小的那个连接剩下的两个链表合并后的结果 小->next = dfs(小->next,大) return 小；
• 递归的出口 谁为空返回另一个

代码实现：

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;
        }
    }
};

206. 反转链表

题目链接： 206. 反转链表 题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

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

示例 3：

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

题目解析： 这道题给了我们一个单链表的头节点，让我们反转链表，然后返回反转后的链表。 第一种视角：从宏观的角度来看待这个问题 将head的next的next指向head，将head的next置为空。 如此我们会发现这将会导致结点丢失

比如上述操作会使得3这个结点丢失。 我们用递归的方法来解决这道问题 1.我们先让当前结点后面的链表先逆置，并且把头节点返回。 2.把当前结点添加到逆置后的结点的后面即可。 第二种视角：将链表看成一棵树 链表其实是一种特殊的树形结构，仅需对链表做一次深度优先遍历即可。

我们定义一个newhead对链表做一次深度优先遍历，当newhead的next为空时说明此结点就是将来要返回的头节点

• 重复子问题 -> 函数头的设计 传入一个头节点，从后向前反转链表
• 子问题在干什么 -> 函数体的设计 将此结点的next的next指向此节点，此节点的next置为空
• 返回值 返回next为空的结点

代码实现：

class Solution {
public:
    ListNode* newhead; //定义一个newhead记录要返回的新的头节点
    ListNode* reverseList(ListNode* head) 
    {
        if(head == nullptr || head -> next == nullptr) return head;
        auto newhead = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = nullptr;
        
        return newhead;
    }
};

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

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

示例 1：

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

示例 2：

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

示例 3：

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

题目解析： 这道题目让我们两两交换相邻的节点，并返回交换后链表的头节点，前提是在不修改节点中的值的情况下，即只能进行节点交换。这道题我们可以用递归的思路来求解。首先定义一个ret来用来接收交换后链表的头节点。然后把相邻节点进行两两交换。

代码实现：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;//如果链表为空或者链表的下一个节点为空，直接返回头节点
        ListNode* r = swapPairs(head->next->next);
        ListNode* ret = head->next;
        head->next->next = head;
        head->next = r;

    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/22 = 1/4 = 0.25

题目解析： 这道题让我们计算x的n次方。 解法一： 暴力解法 我们可以用一个循环进行暴力求解，但是对这道题而言暴力求解会超出时间限制。 解法二： 快速幂 实现快速幂的方法有两种，第一种是递归，第二种是循环。本题我们就来用递归的方式实现快速幂。 例如：我们要求3的16次方，我们可以先求出3的8次方，要求3的8次方，我们可以先求出3的4次方，要求3的4次方，我们可以先求出3的平方。

当n为奇数时，我们可以先求出x的二分之n次方，最后再乘上x。

• 相同的的子问题 -> 函数头的设计 给一个数和一个指数，求出x的n次幂是多少 int Pow( x , n )
• 只关心某一层在干什么 -> 函数体的设计 给一个数和一个指数，求出x的n/2次幂是多少 tmp = Pow( x , n / 2 )
• 返回值 分类讨论 如果n为偶数，返回tmp*tmp 如果n为奇数，返回tmp*tmp*x

代码实现：

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