【算法学习计划】回溯 -- 递归
目录
leetcode 面试题08.06.汉诺塔问题
leetcode 21.合并两个有序链表
leetcode 206.反转链表
leetcode 24.两两交换链表中的节点
leetcode 50. Pow(x, n)
本篇文章将是我们回溯专题的第一篇文章,在这里我先浅浅讲一下什么是回溯
其实就是递归,只不过递归的时候还有一个搜索的目的,也叫做深度优先遍历,dfs
所以大家对于递归不用太过于害怕,因为各位害怕的其实是递归展开图的复杂,至于递归本身,如果将其看做一个黑盒,从宏观角度去看待这个问题的话,那么递归其实清晰特别逻辑
接下来我们就用 5 道题目来带各位初识一下递归
(下文中的标题都是leedcode对应题目的链接)
leetcode 面试题08.06.汉诺塔问题
这道题目非常的简单
首先我们先从宏观看一下这道问题,我们要从A柱移动到C柱,那么我们就应该是将最后一个盘上面的所有盘都当成一个整体,然后就是将上面所有的盘移动到B柱,最后一个盘移动到C柱,最后再将一刚开始移动到B柱的盘全部移动到C柱
这其实就是重复子问题了,因为我们每一种情况都是将最下面上面的所有和最下面
所以代码就是:
class Solution {
public:void dfs(vector<int>& begin, vector<int>& mid, vector<int>& end, int n){if(n == 1){end.push_back(begin.back());begin.pop_back();return;}dfs(begin, end, mid, n-1);end.push_back(begin.back());begin.pop_back();dfs(mid, begin, end, n-1);}void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {dfs(A, B, C, A.size());}
};
我们来细细解析一下:
首先,if 是递归出口,也就是递归到这个条件的时候,就没有办法再进行递归了
放在这道题目上面就是,当A柱上面只有一个盘子的时候,我们就直接将这个盘放到C柱上面
接着第一个dfs代表将最下面那个盘上面的所有盘,将这些盘放到B柱上面
接着就是将最后一个盘移动到C柱上的工作
最后一个dfs就是将那 n-1 个盘全部递归式地放到C柱上面
leetcode 21.合并两个有序链表
这道题其实有更简单的解法,也就是一个一个节点的对比,设两个指针分别指向两个链表的头节点
对比完之后,再看两个指针还有哪个没有到结尾的,再将那一段结尾全部加进返回的结果里就可以了
但是这题也是可以用递归来做的,我们可以用这道题目锻炼以下我们的递归思维
首先我们要先找到重复子问题,因为只有找到了我们才知道怎么递归
假设上面那个链表节点的第一个小一点,那么我们就把这个节点先屏蔽
那么除开这个节点之后,我们的任务就变成了将剩下的所有节点全部合并
再拿开一个节点,还是将剩下的全部节点合并,我们的重复子问题就出现了
由于这是两个升序链表,所以我们可以直接改变原链表的指向
代码如下:
/*** 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* l1, ListNode* l2) {if(!l1)return l2;if(!l2)return l1;if(l1->val < l2->val) l1->next = mergeTwoLists(l1->next, l2);else l2->next = mergeTwoLists(l1, l2->next);return l1->val < l2->val ? l1 : l2;}
};
最上面两个 if 是递归出口
下来的递归,就是,如果第一个小,那么我们就将第一个作为头节点,然后后面的递归函数会帮我们将后面的所有节点合并为有序的,然后我们第一个节点和他链接起来,最后返回第一个节点即可
第二个小的情况同理
leetcode 206.反转链表
这道反转链表我们可以用递归的方式完成
首先是重复子问题,当我们第一个节点排除的时候,我们剩下的任务就是将除了第一个之外的所有节点反转
那我们可以将第一个节点单独拿出来,让head->next放进递归中
接着这个递归函数过后,后面的链表肯定被反转好了,那么我们要做的其实就是让第二个节点的next指针指向第一个,接着第一个的指针指向空这样我们的数组就被反转了
最后我们要一直返回最后一个元素的指针,所以我们可以再碰到最后一个节点的时候,返回他自己,接着剩下所有的情况我们都那一个指针接受返回值,然后将这个指针一路返回回去
或可以搞一个全局指针,当碰到最后一个节点的时候赋值给这个指针,最后返回这个节点即可
代码如下:
/*** 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* ret = reverseList(head->next);//将head之后的链表全部反转head->next->next = head;// 将head放到反转后链表的最后面head->next = nullptr;return ret;}
};
leetcode 24.两两交换链表中的节点
这道题目和反转链表差不多,但是我们是将当前节点的下下个节点放入递归中,然后我们执行当前两个节点的交换逻辑
然后递归出口就是,当我们当前节点的下一个节点为空(只有一个,不是一对),或者当前节点就是空(刚好都是成双成对)
代码如下:
/*** 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* ret = swapPairs(head->next->next);ListNode* n1 = head;ListNode* n2 = head->next;n1->next = ret;n2->next = n1;return n2;}
};
leetcode 50. Pow(x, n)
题意很简单,其实就是求一个数的多少次方而已
但是我们直接遍历 n 次的话,一定会超时,因为这道题目的 n 最大是非常大的,包超时的
所以我们需要想一个对策
试想一下,我们需要求出 3^8,正常是直接乘 8 次,但是我们可以先将 3^4 求出来,这样我们只用循环 4 次,接下来就是结果乘两边就行了
而 3^4 可以再分为 3^2,这样循环下去
所以我们的重复子问题就出来了
因为我们可以判断以下当前数是否是奇数,如果是的话那就乘 待平方数(假设是3),然后再拿一个数来接收返回值,假设是ret
那么结果就是ret * ret * 3,而如果是偶数的话,就是 ret * ret
代码如下:
class Solution {
public:double dfs(double x, long n){if(n == 0) return 1;if(n == 1) return x;double ret = dfs(x, n/2);if(n % 2 == 1) return ret*ret*x;return ret*ret;}double myPow(double x, int n) {int flag = 0;long n1 = (long)n;if(n < 0){flag = 1;n1 = -n1;}double ret = dfs(x, n1);if(flag == 1) return 1/ret;return ret;}
};
这篇文章到这里就结束了
我们这篇文章主要是讲一讲简单的递归,用一些简单递归来帮助大家消除恐惧的
接下来我们还会有更多递归系列的博客,如果觉得对你有帮助的可以关注一下!!~( ̄▽ ̄)~*
相关文章:
【算法学习计划】回溯 -- 递归
目录 leetcode 面试题08.06.汉诺塔问题 leetcode 21.合并两个有序链表 leetcode 206.反转链表 leetcode 24.两两交换链表中的节点 leetcode 50. Pow(x, n) 本篇文章将是我们回溯专题的第一篇文章,在这里我先浅浅讲一下什么是回溯 其实就是递归,只不…...
Unity中 JobSystem使用整理
Unity 的JobSystem允许创建多线程代码,以便应用程序可以使用所有可用的 CPU 内核来执行代码,这提供了更高的性能,因为您的应用程序可以更高效地使用运行它的所有 CPU 内核的容量,而不是在一个 CPU 内核上运行所有代码。 可以单独使…...
【从零实现Json-Rpc框架】- 项目实现 - 服务端主题实现及整体封装
📢博客主页:https://blog.csdn.net/2301_779549673 📢博客仓库:https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! &…...
JavaScript基础-移动端常用开发框架
随着移动互联网的发展,越来越多的应用和服务需要支持移动设备。为了提高开发效率和用户体验,开发者们依赖于一些成熟的JavaScript框架来构建响应迅速、功能丰富的移动Web应用。本文将介绍几款广泛使用的移动端开发框架,并通过具体的示例展示它…...
Tree - Shaking
Vue 3 的 Tree - Shaking 技术详解 Tree - Shaking 是一种在打包时移除未使用代码的优化技术,在 Vue 3 中,Tree - Shaking 发挥了重要作用,有效减少了打包后的代码体积,提高了应用的加载性能。以下是对 Vue 3 中 Tree - Shaking …...
VSCode历史版本的下载安装
VSCode历史版本的下载安装 文章目录 VSCode历史版本的下载安装VSCode安装下载历史版本地址查询VSCode历史版本的 commit id 安装参考资料 VSCode安装 Windows版本:Windows10VSCode版本:VScode1.65.0(64位User版本)本文编写时间&a…...
Websoft9分享:在数字化转型中选择开源软件可能遇到的难题
引言:中小企业数字化转型的必由之路 全球94.57%的企业已采用开源软件(数据来源:OpenLogic 2024报告),开源生态估值达8.8万亿美元。中小企业通过开源软件构建EPR系统、企业官网、数据分析平台等,可节省80%软件采购成本。…...
【无人机】无人机PX4飞控系统高级软件架构
目录 1、概述(图解) 一、数据存储层(Storage) 二、外部通信层(External Connectivity) 三、核心通信枢纽(Message Bus) 四、硬件驱动层(Drivers) 五、飞…...
新版本Xmind结合DeepSeek快速生成美丽的思维导图
前言 我的上一篇博客(https://quickrubber.blog.csdn.net/article/details/146518898)中讲到采用Python编程可以实现和Xmind的互动,并让DeepSeek来生成相应的代码从而实现对内容的任意修改。但是,那篇博客中提到的Xmind有版本的限…...
Windows查重工具,强烈推荐大家收藏!
我大家在用电脑的时候,是不是发现用得越久,电脑里的软件和文件就越多? 今天我给大家带来的这两款重复文件查找神器,简直就是电脑里的“清洁小能手”,能帮你把那些重复的文件和文件夹找出来。 Easy DupLicate Finder 重…...
数字孪生技术之争:UE、Unity还是飞渡DTS数字孪生平台?
作为深耕数字孪生内容创作的B站UP主,我们创作的内容广受数十万粉丝喜爱。后台私信经常提及两个问题:“这质感绝了!如此丝滑流畅是UE做的吗?”VS “请问用Unity能实现这个效果吗?” Unreal Engine凭借影视级渲染&#…...
【GCC警告报错4】warning: format not a string literal and no format arguments
文章主本文根据笔者个人工作/学习经验整理而成,如有错误请留言。 文章为付费内容,已加入原创保护,禁止私自转载。 文章发布于:《C语言编译报错&警告合集》 如图所示: 原因: snprintf的函数原型&#x…...
【Tauri2】013——前端Window Event与创建Window
前言 【Tauri2】012——on_window_event函数-CSDN博客https://blog.csdn.net/qq_63401240/article/details/146909801?spm1001.2014.3001.5501 前面介绍了on_window_event,这个在Builder中的方法,里面有许多事件,比如Moved,Res…...
修复SSL证书链不完整问题certificate verify failed unable to get local issuer certificate
文章目录 前言排查过程怀疑文章平台图片转存问题尝试使用 Python 代码下载图片使用 SSL Labs Server Test 验证猜想回顾 SSL 安装命令ACME 生成的证书 验证使用 [SSL Labs Server Test](https://www.ssllabs.com/ssltest/index.html) 验证文章发布平台转存验证 个人简介 前言 …...
管家婆财贸ERP BB102.采购销售订金管理
低适用版本: 财贸系列 23.8 插件简要功能说明: 采购订单/销售订单支持查询订金付款情况,联查下游付款/收款信息更多细节描述见下方详细文档 插件操作视频: 进销存类定制插件--采购销售订金管理 插件详细功能文档: …...
前端对接下载文件接口、对接dart app
嵌套在dart app里面的前端项目 1.前端调下载接口 ->后端返回 application/pdf格式的文件 ->前端将pdf处理为blob ->blob转base64 ->调用dart app的 sdk saveFile ->保存成功 async download() {try {// 调用封装的 downloadEContract 方法获取 Blob 数据const …...
牛客 简写单词
简写单词_牛客题霸_牛客网 主要是如何输入 #include <iostream> #include <string>using namespace std;int main() {string str;while(cin>>str){if(str[0]>a&&str[0]<z){cout<<char(str[0]-32);}else cout<<str[0];str.clear(…...
解决STM32CubeMX中文注释乱码
本人采用【修改系统环境变量】的方法 1. 使用快捷键 win X,打开【系统R】,点击【高级系统设置】 2. 点击【环境变量】 3. 点击【新建】 4.按图中输入【JAVA_TOOL_OPTIONS】和【-Dfile.encodingUTF-8】,新建环境变量后重启CubeMX即可。 解释…...
若依——基于AI+若依框架的实战项目(实战篇(下))
目录 前言 6. 设备管理 6.1 需求说明 6.2 生成基础代码 6.2.1 需求 6.2.2 步骤 ①创建目录菜单 ②添加数据字典 ③配置代码生成信息 ④下载代码并导入项目 6.3 设备类型改造 6.3.1 基础页面 需求 代码实现 6.4 设备管理改造 6.4.1 基础页面 需求 代码实现 …...
SpringBoot项目瘦身指南:从臃肿到高效的优化实践
精心整理了最新的面试资料和简历模板,有需要的可以自行获取 点击前往百度网盘获取 点击前往夸克网盘获取 一、问题背景 SpringBoot的"约定优于配置"特性极大提升了开发效率,但默认配置可能导致项目逐渐臃肿。典型的症状包括: 打…...
运筹帷幄:制胜软件开发
运筹学在软件开发项目中的作用主要体现在复杂系统建模、资源优化和决策支持中。通过数学建模、算法设计和数据分析,运筹学能够帮助开发团队更高效地实现软件需求,尤其是在涉及资源分配、路径规划、调度优化等场景时。 案例:电商物流配送系统的…...
代码随想录|动态规划|18完全背包理论基础
leetcode:52. 携带研究材料(第七期模拟笔试) 题目 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些…...
52.个人健康管理系统小程序(基于springbootvue)
目录 1.系统的受众说明 2.开发环境与技术 2.1 MYSQL数据库 2.2 Java语言 2.3 微信小程序技术 2.4 SpringBoot框架 2.5 B/S架构 2.6 Tomcat 介绍 2.7 HTML简介 2.8 MyEclipse开发工具 3.系统分析 3.1 可行性分析 3.1.1 技术可行性 3.1.2 经济可行性 3.1.3 操作…...
大语言模型中的嵌入模型
本教程将拆解什么是嵌入模型、为什么它们在NLP中如此重要,并提供一个简单的Python实战示例。 分词器将原始文本转换为token和ID,而嵌入模型则将这些ID映射为密集向量表示。二者合力为LLMs的语义理解提供动力。图片来源:[https://tzamtzis.gr/2024/coding/tokenization-by-an…...
运维之 Centos7 防火墙(CentOS 7 Firewall for Operations and Maintenance)
运维之 Centos7 防火墙 1.介绍 Linux CentOS 7 防火墙/端口设置: 基础概念: 防火墙是一种网络安全设备,用于监控和控制网络流量,以保护计算机系统免受未经授权的访问和恶意攻击。Linux CentOS 7操作系统自带了一个名为iptables的…...
Ubuntu 20.04 出现问号图标且无法联网 修复
在 Ubuntu 中遇到网络连接问题(如出现问号图标且无法联网),可以通过以下命令尝试重启网络服务: 1. 推荐先修改DNS 编辑 -> 虚拟机网络编辑器-> VMnet8 ->NAT 设置 -> DNS 设置 -> 设置DNS 服务器 DNS填什么 取决…...
联想M7400打印机怎么清零
一(粉盒加粉后清零): 开机,打开前盖; 按下 “清除返回” 键,屏幕显示 “更换硒鼓?是否”; 按 “开始” 键,屏幕无显示; 按下 “” 号键 11 次,…...
AIGC7——AIGC驱动的视听内容定制化革命:从Sora到商业化落地
引言:个性化视听时代的到来 2024年,OpenAI发布视频生成模型Sora,可生成60秒高清视频;中国团队推出的Vidu模型实现16秒镜头连贯生成。这些突破标志着AIGC正式进入高质量视听内容定制化阶段。据Gartner预测,到2027年&am…...
Git Restore 命令详解与实用示例
文章目录 Git Restore 命令详解与实用示例1. 恢复工作区文件到最后一次提交的状态基本命令示例恢复所有更改 2. 恢复某个文件到特定提交的状态基本命令示例 3. 恢复暂存区的文件基本命令示例恢复所有暂存的文件 git restore 的常见选项git restore 与 git checkout 比较总结 Gi…...
Sentinel全面解析与实战教程
Sentinel全面解析与实战教程 一、引言 在现代分布式系统中,随着业务的不断发展和流量的日益增长,保障系统的稳定性成为了重中之重。Sentinel作为一款优秀的高可用流量防护组件,为解决系统中的流量控制、熔断降级等问题提供了有效方案。本文…...
考研总结(初试篇)--双非勇闯985
考研终于告一段落了,也是被湖南大学拟录取了,写下这篇总结,回顾一下我的经历吧。 我是2024年3月开学的时候,正式确定考研的。当时纠结于定学校,长理和湖大。最后还是选择湖大,因为反正都是要好好准备的&am…...
【电路笔记】-触发器的转换
触发器的转换 文章目录 触发器的转换1、概述2、置位-复位SR触发器3、门控置位-复位(SR)触发器4、数据(D型)触发器5、JK触发器6、使用主从触发器的触发器转换7、(切换)T型触发器8、总结触发器是时序电路的基本构建模块,可以从一种形式转换到另一种形式,能够存储单个数据…...
QT 中的元对象系统(五):QMetaObject::invokeMethod的使用和实现原理
目录 1.简介 2.原理概述 3.实现分析 3.1.通过方法名调用方法的实现分析 3.2.通过可调用对象调用方法的实现分析 4.使用场景 5.总结 1.简介 QMetaObject::invokeMethod 是 Qt 框架中的一个静态方法,用于在运行时调用对象的成员函数。这个方法提供了一种动态调…...
基数排序算法解析与TypeScript实现
基数排序(Radix Sort)是一种高效的非比较型整数排序算法,通过逐位分配与收集的方式实现排序。本文将深入解析其工作原理,并给出完整的TypeScript实现。 一、算法原理 1. 核心思想 多关键字排序:将整数按位数切割成不同…...
oracle asm 相关命令和查询视图
有关asm磁盘的命令 添加磁盘 alter diskgroup data1 add disk /devices/diska*;---runs with a rebalance power of 5 , and dose not return until the rebalance operation is completealter diskgroup data1 add disk /devices/diskd* rebalance power 5 wait;查询 select …...
THUNLP_Multimodal_Excercise
背景 多模态大模型(Multimodal Large Language Models, MLLM)的构建过程中,模型结构、模型预测、指令微调以及偏好对齐训练是其中重要的组成部分。本次任务中,将提供一个不完整的多模态大模型结构及微调代码,请根据要求…...
AIGC6——AI的哲学困境:主体性、认知边界与“天人智一“的再思考
引言:当机器开始"思考" 2023年,Google工程师Blake Lemoine声称对话AI LaMDA具有"自我意识",引发轩然大波。这一事件将古老的哲学问题重新抛回公众视野:**机器能否拥有主体性?**从东方"天人…...
主题(topic)中使用键(key)来区分同一主题下的多个数据实例
在Fast DDS中,通过在主题(topic)中使用键(key)来区分同一主题下的多个数据实例,具体含义如下: 1. **主题(Topic)**:在DDS中,主题是数据的类型或类…...
[王阳明代数讲义]琴语言类型系统工程特性
琴语言类型系统工程特性 层展物理学组织实务与艺术与琴生生.物机.械科.技工.业研究.所软凝聚态物理开发工具包社会科学气质砥砺学人生意气场社群成员魅力场与心气微积分社会关系力学 意气实体过程图论信息编码,如来码导引 注意力机制道装Transformer架构的发展标度律…...
蜜蜡是什么?蜜蜡与琥珀的区别以及蜜蜡的收藏价值一览
蜜蜡是琥珀的一种,在物理成分和化学成分上都和琥珀没有区别,只是因其“色如蜜,光如蜡”而得名。蜜蜡形成于白垩纪时期,因形成时间较长,形成过程比较复杂等原因,种类较其他产地要多。 蜜蜡是有机矿物&#x…...
第五课:高清修复和放大算法
文章目录 Part.01 高清修复(Hi-Res Fix)Part.02 SD放大(SD Upscale)Part.03 附加功能放大Part.01 高清修复(Hi-Res Fix) 文生图中的高清修复/高分辨率修复/超分辨率修复先低分辨率抽卡,再高分辨率修复。不能突破显存限制放大重绘幅度安全范围是0.3-0.5,如果想让AI更有想象力0…...
SpringSecurity6.0 通过JWTtoken进行认证授权
之前写过一个文章,从SpringSecurity 5.x升级到6.0,当时是为了配合公司的大版本升级做的,里面的各项配置都是前人留下来的,其实没有花时间进行研究SpringSecurity的工作机制。现在新东家有一个简单的系统要搭建,用户的认…...
TypeScript工程集成
以下是关于 TypeScript 工程集成 的系统梳理,涵盖基础配置、进阶优化、开发规范及实际场景的注意事项,帮助我们构建高效可靠的企业级 TypeScript 项目: 一、基础知识点 1. 项目初始化与配置 tsconfig.json 核心配置:{"compilerOptions": {"target": &…...
网络空间安全(51)邮件函数漏洞
前言 邮件函数漏洞,特别是在PHP环境中使用mail()函数时,是一个重要的安全问题。 一、概述 在PHP中,mail()函数是一个用于发送电子邮件的内置函数。其函数原型为: bool mail ( string $to , string $subject , string $message [, …...
怎么让一台云IPPBX实现多家酒店相同分机号码一起使用
下面用到的IPPBX是我们二次开发后的成品,支持各种云服务器一键安装,已经写好了一键安装包,自动识别系统环境,安装教程这里就不再陈述了! 前言需求 今天又遇到了一个客户咨询,关于部署一台云IPPBX…...
qt tcpsocket编程遇到的并发问题
1. 单个socket中接收消息的方法要使用局部变量而非全局,避免消息频发时产生脏数据 优化后的关键代码 recieveInfo() 方法通过返回内部处理后的 msg 进行传递if (data.indexOf("0103") -1) { 这里增加了判断, 对数据(非注册和心跳࿰…...
U盘实现——BOT 常用命令
文章目录 U盘实现——BOT 常用命令命令格式CBWCSW数据传输条件命令传输数据传输状态传输命令汇总INQUIRY Command:12h数据格式抓包READ FORMAT CAPACITIES Command: 23h数据格式抓包READ CAPACITY Command: 25h数据格式抓包TEST UNIT READY Command: 00h数据格式抓包WRITE(10) …...
JavaScript DOM 节点操作
目录 一、DOM 节点 节点类型(Node Types) 二、查找节点 1.查找父节点 1. parentNode 2. parentElement 2.查找子节点 1. childNodes 2. children 3. firstChild / lastChild 4. firstElementChild / lastElementChild 3.查找兄弟节点 1. pre…...
JDBC常用的接口
一、什么是JDBC JDBC是Java语言连接数据库的接口规范。 二、JDBC的体系 1、Java官方提供一个操作数据库的抽象接口 抽象接口有很多的接口和抽象类。 例如:Driver、Connection、Statement。 2、各个数据库厂商提供各自的Java实现类 需要各自实现具体的细节。 例如&am…...
【DLI】Generative AI with Diffusion Models通关秘籍
Generative AI with Diffusion Models,加载时间在20分钟左右,耐心等待。 6.2TODO 这里是在设置扩散模型的参数,代码里的FIXME部分需要根据上下文进行替换。以下是各个FIXME的替换说明: 1.a_bar 是 a 的累积乘积,在 …...