当前位置：首页 > web >正文

【递归、搜索与回溯】专题一：递归（一）

web 2025/7/4 2:56:16

📝前言说明：

本专栏主要记录本人递归，搜索与回溯算法的学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

点击链接	开始学习
导论	递归 (一)、递归 (二)
二叉树的深搜	穷举 vs 暴搜 vs 深搜
回溯 vs 剪枝	综合练习
FloodFill算法	记忆化搜索

题目

面试题 08.06. 汉诺塔问题
- 个人解
21. 合并两个有序链表
- 优质解
总结
- 循环（迭代） vs 递归
- 递归 vs 深搜

面试题 08.06. 汉诺塔问题

题目链接：https://leetcode.cn/problems/hanota-lcci/description/
在这里插入图片描述

个人解

思路：

分析问题
- n == 1 时，直接把盘子从 A 移到 C；（递归出口）
- n > 1 时
  - 先把上面 n - 1 个盘子从 A 移到 B（子问题）；
  - 再将最大的盘子从 A 移到 C；
  - 再将 B 上 n - 1 个盘子从 B 移到 C（子问题）。
子问题确定函数头：把 n - 1个盘子从 A，借助 C，移动到 B
- move(int n, vector<int>& source, vector<int>& auxiliary, vector<int>& target)
单个子问题解决方法：即上面 n > 1的处理流程
递归出口：即：n == 1的处理流程

用时：10:00
屎山代码：

class Solution {
public:void move(int n, vector<int>& source, vector<int>& auxiliary, vector<int>& target){if(n == 1) // 当只有一个盘子，直接移动{target.emplace_back(source.back());source.pop_back();return;}// 把前 n - 1 个盘子移动到辅助柱子move(n - 1, source, target, auxiliary); // 移动第 n 个盘子target.push_back(source.back());source.pop_back();// 在把 前 n - 1 个盘子从辅助盘子移动回来move(n - 1, auxiliary, source, target);}void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {move(A.size(), A, B, C);}
};

时间复杂度：O( $2^n$ )
空间复杂度：O(n)

21. 合并两个有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/
在这里插入图片描述

优质解

思路：

分析问题：
- 每次进行两个链表的头结点比较，然后提取出较小的头结点
- 再用提出的头结点，链接两个链表（其中一个的头结点被提出）合并好后的结果
子问题：合并有序链表
- 函数头：Node* dfs(l1, l2); // 给两个链表，返回提出的头结点
单个子问题解决方法：
- 比较大小，记录小的头结点Node
- 链接，假如l1->val < l2 -> val，则l1->next = dfs(l1 -> next, l2);
- 返回合并后链表的头结点，return Node;
递归出口：链表为空
代码：

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr || list2 == nullptr)return list1 == nullptr? list2 : list1; // 返回不为空那个，把没连接的部分链上if(list1 -> val < list2 -> val){list1 -> next = mergeTwoLists(list1 -> next, list2);return list1;}else{list2 -> next = mergeTwoLists(list1, list2 -> next);return list2;}}
};