【递归、搜索与回溯算法必刷42题：专题一】从汉诺塔问题到快速幂
🎬 个人主页：艾莉丝努力练剑
❄专栏传送门：《C语言》《数据结构与算法》《C/C++干货分享&学习过程记录》
《Linux操作系统编程详解》《笔试/面试常见算法：从基础到进阶》《Python干货分享》
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬 艾莉丝的简介：
🎬艾莉丝的算法专栏简介：
文章目录
本文设计专题一算法题链接
1 汉诺塔问题
题目描述
接下来，我们就来介绍一下这道题的算法原理。
汉诺塔问题（递归解法）
1. 问题描述
汉诺塔问题是一个经典的递归问题，规则如下：
- 有三根柱子，记为 A（起始柱）、B（辅助柱）、C（目标柱）。
- A 柱上有 n 个盘子，从小到大叠放（从上到下编号为 1 到 n）。
- 目标是将所有盘子从 A 移到 C，每次只能移动一个盘子，并且大盘子不能放在小盘子上面。
2. 递归思想
基本情况（递归终止条件）
- 当
n = 1时，直接将 A 最上面的盘子移到 C。
递归分解（n ≥ 2）
若要将 A 上的 n 个盘子移到 C，可以分解为三个步骤：
- 将 A 上除了最底下的盘子（即上面 n-1 个盘子）移到 B（借助 C 作为辅助柱）。
- 将 A 最底下的最大盘子移到 C。
- 将 B 上的 n-1 个盘子移到 C（借助 A 作为辅助柱）。
这样，规模为 n 的问题被拆分为两个规模为 n-1 的子问题。
3. 递归算法流程（函数设计）
函数头
voidhanoi(vector<int>& A, vector<int>& B, vector<int>& C,int n);- 1、返回值：无;
- 2、参数：三个柱子上的盘子，当前需要处理的盘子个数（当前问题规模）。
- 3、函数作用：将A中的上面n个盘子挪到C中。
递归函数流程：
- 1、当前问题规模为n=1时，直接将A中的最上面盘子挪到C中并返回；
- 2、递归将A中最上面的n-1个盘子挪到B中；
- 3、将A中最上面的一个盘子挪到C中;
- 4、将B中上面n-1个盘子挪到C中。
解题过程
算法实现（C++）
classSolution{public:voidhanota(vector<int>& a, vector<int>& b, vector<int>& c){dfs(a,b,c,a.size());}voiddfs(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);}// void dfs(x,y,z,int n)// void dfs(x,y,z,n - 1)// z = x.back();// dfs(y,x,z,n - 1);};上面是面试题的处理，如果是笔试题，就可以不讲武德了——
classSolution{public:voidhanota(vector<int>& a, vector<int>& b, vector<int>& c){ c = a;}};2 合并两个有序链表
题目描述
接下来，我们就来介绍一下这道题的算法原理。
解题过程
算法实现（C++）
classSolution{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 反转链表
题目描述
接下来，我们就来介绍一下这道题的算法原理。
解题过程
算法实现（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) {} * }; */classSolution{public: ListNode*reverseList(ListNode* head){// 细节问题:找出口if(head ==nullptr|| head->next ==nullptr)return head;// 主逻辑 ListNode* newhead =reverseList(head->next); head->next->next = head; head->next =nullptr;// 最终返回结果return newhead;}};4 两两交换链表中的节点
题目描述
接下来，我们就来介绍一下这道题的算法原理。
解题过程
算法实现（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) {} * }; */classSolution{public: ListNode*swapPairs(ListNode* head){// 出口if(head ==nullptr|| head->next ==nullptr)return head;// 节点为空或者是个尾节点，就不能交换// 宏观角度看待auto tmp =swapPairs(head->next->next);auto ret = head->next; head->next->next = head; head->next = tmp;// 返回最终结果return ret;}};5 Pow(x, n)
题目描述
接下来，我们就来介绍一下这道题的算法原理。
解题过程
算法实现（C++）
classSolution{public:doublemyPow(double x,int n)// 主函数{// 细节问题：n可能是负数return n <0?1.0/Pow(x,-(longlong)n):Pow(x,n);}doublePow(double x,longlong n)// 快速幂{// 递归出口if(n ==0)return1.0;// x ^ 0 = 1// 递归double tmp =Pow(x,n /2);return n %2==0? tmp * tmp : tmp * tmp * x;}};结尾
uu们，本文的内容到这里就全部结束了，艾莉丝再次感谢您的阅读！
结语：希望对学习递归、搜索与回溯算法相关内容的uu有所帮助，不要忘记给博主“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡૮₍ ˶ ˊ ᴥ ˋ˶₎ა
