递归与搜索算法实战：汉诺塔、链表操作及快速幂
1 汉诺塔问题
题目描述
C++算法
递归与搜索算法实战：汉诺塔、链表操作及快速幂
递归算法在汉诺塔、链表操作及快速幂计算中应用广泛。文章解析汉诺塔递归分解思路，展示有序链表合并与反转的实现逻辑，包含节点两两交换策略。同时介绍基于分治思想的快速幂算法，通过 C++ 代码示例说明递归终止条件与状态转移过程，辅助算法基础学习。
递归算法在汉诺塔、链表操作及快速幂计算中应用广泛。文章解析汉诺塔递归分解思路，展示有序链表合并与反转的实现逻辑，包含节点两两交换策略。同时介绍基于分治思想的快速幂算法，通过 C++ 代码示例说明递归终止条件与状态转移过程，辅助算法基础学习。
汉诺塔问题是一个经典的递归问题，规则如下：
n = 1 时，直接将 A 最上面的盘子移到 C。若要将 A 上的 n 个盘子移到 C，可以分解为三个步骤：
这样，规模为 n 的问题被拆分为两个规模为 n-1 的子问题。
void hanota(vector<int>& a, vector<int>& b, vector<int>& c, int n);
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);
}
};
针对笔试场景，可简化为直接赋值：
class Solution {
public:
void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
c = a;
}
};
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;
}
}
};
// 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->next->next = head;
head->next = nullptr;
// 最终返回结果
return newhead;
}
};
class Solution {
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;
}
};
class Solution {
public:
double myPow(double x, int n) {
// 主函数
// 细节问题：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; // x ^ 0 = 1
// 递归
double tmp = Pow(x, n / 2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online