当前位置: 首页 > news >正文

【递归、搜索与回溯算法】导论

📝前言说明:

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

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

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

暂时没有暂时没有

目录

  • 一,名词解释
    • 1, 递归
      • 1.1 什么是递归
      • 1.2 为什么会用到递归
      • 1.3 如何理解递归
        • 1.3.1 理解递归展开的细节图
        • 1.3.2 利用部分基础二叉树题目来感受
        • 1.3.3 宏观看待递归过程
      • 4. 如何写好一个递归
  • 二,搜索 vs 深度优先遍历 vs 深度优先搜索 vs 宽度优先遍历 vs 宽度优先搜索 vs 暴搜
    • 1. 深度优先遍历 vs 深度优先搜索
    • 2. 广度优先遍历 vs 广度优先搜索
    • 3. 暴搜
    • 4 扩展搜索问题
  • 三,回溯与剪枝
  • 四,本专栏介绍

一,名词解释

递归和搜素与回溯的关系是:递归包含搜索,搜索包含回溯

1, 递归

1.1 什么是递归

  • 函数自己调用自己。

1.2 为什么会用到递归

  • 以,二叉树的遍历,快排,归并为例:
  • 解决主问题 → 遇到相同子问题
  • 解决子问题 → 遇到相同子问题

在这里插入图片描述

1.3 如何理解递归

1.3.1 理解递归展开的细节图

以前序遍历为例:
在这里插入图片描述

1.3.2 利用部分基础二叉树题目来感受

因为二叉树本身就具有非常强的递归特性,这里给三道题目:

  • 单值二叉树
  • 相同的数
  • 另一棵树的子树
1.3.3 宏观看待递归过程

当我们对递归有一定的感知以后,我们写递归题目的时候,不要过度关心细节,应该宏观看待递归过程
怎么宏观:

  • 不要关系递归的细节展开图(不要题题都想着展开搞明白调用流程)
  • 把递归函数当做一个黑盒子(我们只管用就行了)
  • 相信这个黑盒子一定能返回我们要的结果

4. 如何写好一个递归

  • 先找到相同的子问题 → 函数头的设计
  • 只关心一个子问题是如何解决的 → 函数体的设计
  • 子问题不能再分时 → 注意递归函数的出口(结束条件)

以后续遍历为例:

  • 父问题:对对应根节点的树进行后续遍历。子问题:对子树也后续遍历 → 函数头(传入根节点)
  • 子问题如何解决: 先访问左子树和右子树(我们相信递归函数一定能完成),然后再访问根节点printf
  • 递归出口:当节点为NULL

在这里插入图片描述

二,搜索 vs 深度优先遍历 vs 深度优先搜索 vs 宽度优先遍历 vs 宽度优先搜索 vs 暴搜

1. 深度优先遍历 vs 深度优先搜索

  • 前序遍历就是一种深度优先遍历(dfs),即:一条路走到头,不能再走了才返回去走其他路
  • 深度优先搜索:本质和深度优先遍历一样,只是目的是搜索
  • 关系:遍历是形式,目的是搜索

2. 广度优先遍历 vs 广度优先搜索

  • 如层序遍历,就是广度优先遍历(bfs)
  • 两者关系与 深度优先遍历 vs 深度优先搜索之间的关系一样

3. 暴搜

暴搜,即:暴力枚举一遍所有结果(如:dfsbfs

4 扩展搜索问题

除了与二叉树有关的问题,其他问题我们能否用递归呢?
下面以求1、2、3全排列的所有结果 举例:
我们把问题画成树状图:
在这里插入图片描述
上面就是一颗决策树,一样可以用dfs得到所有结果

三,回溯与剪枝

回溯:

  • 回溯的本质就是深度搜索
  • 在深搜过程中,发现一条路走到头了,进行回溯

剪枝:

  • 发现一条路肯定是错的,没必要再走时,剪枝

在这里插入图片描述
红色部分就是回溯
剪枝:

  • 如,橙色的①和②
  • 先走了①,发现走不通于是回溯到分叉口位置,然后走②,发现也走不通,也回到分叉口位置
  • 此时,可以选择往上走和往下走,但是①必然是不正确的选择(因为之前已经得出结论了),所以直接剪枝,不走上面

四,本专栏介绍

本专栏会有以下专题:

  • 专题一:递归
  • 专题二:二叉树的深搜
  • 专题三:穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝
  • 专题四:综合练习
  • 专题五:FloodFill算法
  • 专题六:记忆化搜索

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助,那简直是太酷啦!
若有不足,还请大家多多指正,我们一起学习交流!
📢公主,王子:点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持!祝大家都能得偿所愿,天天开心!!!

相关文章:

【递归、搜索与回溯算法】导论

📝前言说明: 本专栏主要记录本人递归、搜索与回溯算法的学习以及LeetCode刷题记录,按专题划分每题主要记录:(1)本人解法 本人屎山代码;(2)优质解法 优质代码&#xff…...

《智能网联汽车 自动驾驶功能道路试验方法及要求》 GB/T 44719-2024——解读

目录 1. 适用范围 2. 关键术语 3. 试验条件 3.1 试验道路 3.2 试验车辆 3.3 试验设备 3.4 试验时间 4. 试验方法及要求 4.1 功能激活 4.2 动态驾驶任务执行 4.3 动态驾驶任务后援 4.4 状态提示 5. 附录A(核心环境要素) 6. 实施要点 原文链接…...

path环境变量满了如何处理,分割 PATH 到 Path1 和 Path2

要正确设置 Path1 的值,你需要将现有的 PATH 环境变量 中的部分路径复制到 Path1 和 Path2 中。以下是详细步骤: 步骤 1:获取当前 PATH 的值 打开环境变量窗口: 按 Win R,输入 sysdm.cpl,点击 确定。在 系…...

实战项目1(02)

目录 任务场景一 【sw1和sw2的配置如下】 任务场景二 【sw3的配置】 【sw4-6的配置】 任务场景一 某公司有生产、销售、研发、人事、财务等多个部门,这些部门分别连接在两台交换机(SW1和SW2)上,现要求给每个部门划分相应的V…...

m1 安装 Elasticsearch、ik、kibana

一、下载安装ES 1、下载地址 ES|download 2、安装 将下载的安装包解压到 要安装的文件目录 关闭 ES 的安全模式 本地文本编辑器打开elasticsearch.yml配置文件,将红箭头指的地方 改为 false3、启动 ES 启动命令 进入 ES 的安装目录,进入bin文件目…...

游戏引擎学习第273天:动画预览

回顾并为一天的内容定下基调 。目前我们正在编写角色的移动代码,实际上,我们已经在昨天完成了一个简单的角色跳跃的例子。所以今天的重点是,开始更广泛地讨论动画,因为我们希望对现有的动画进行调整,让它看起来更加令…...

JVM中的安全点是什么,作用又是什么?

JVM中的安全点(Safepoint) 是Java虚拟机设计中的一个关键机制,主要用于协调所有线程的执行状态,以便进行全局操作(如垃圾回收、代码反优化等)。它的核心目标是确保在需要暂停所有线程时,每个线程…...

游戏引擎学习第271天:生成可行走的点

回顾并为今天的内容设定背景 我们昨天开始编写一些游戏逻辑相关的内容,虽然这部分不是最喜欢的领域,更偏好底层引擎开发,但如果要独立完成一款游戏,游戏逻辑也必须亲自处理。所以我们继续完善这部分内容。事实上,接下…...

FlySecAgent:——MCP全自动AI Agent的实战利器

最近,出于对人工智能在网络安全领域应用潜力的浓厚兴趣,我利用闲暇时间进行了深入研究,并成功开发了一款小型轻量化的AI Agent安全客户端FlySecAgent。 什么是 FlySecAgent? 这是一个基于大语言模型和MCP(Model-Contr…...

DAMA车轮图

DAMA车轮图是国际数据管理协会(DAMA International)提出的数据管理知识体系(DMBOK)的图形化表示,它以车轮(同心圆)的形式展示了数据管理的核心领域及其相互关系。以下是基于用户提供的关键词对D…...

使用vue3-seamless-scroll实现列表自动滚动播放

vue3-seamless-scroll组件支持上下左右无缝滚动,单步滚动,并且支持复杂图标的无缝滚动。 核心特性 多方向无缝滚动 支持上下、左右四个方向的自动滚动,通过 direction 参数控制(默认 up),适用于新闻轮播、…...

Scrapyd 详解:分布式爬虫部署与管理利器

Scrapyd 是 Scrapy 官方提供的爬虫部署与管理平台,支持分布式爬虫部署、定时任务调度、远程管理爬虫等功能。本文将深入讲解 Scrapyd 的核心功能、安装配置、爬虫部署流程、API 接口使用,以及如何结合 Scrapy-Redis 实现分布式爬虫管理。通过本文&#x…...

mac环境配置(homebrew版)

文章目录 【环境配置】HomebrewGitJavaMavenMySQLRedisNacosNode.js 【拓展-mac常见问题】mac文件损坏问题mac必装软件(Java开发版)zsh和bash配置文件区别 【参考资料】 查看每个版本可以用命令brew info xxx ps:每一个环境安装完之后都要关掉…...

19、DeepSeek LLM论文笔记

DeepSeek LLM 1. **引言**2、架构3、多步学习率调度器4、缩放定律1.超参数的缩放定律2. 估计最优模型和数据缩放 5、GQA分组查询注意力汇总deepseekDeepSeek LLM 技术文档总结1. **引言**2. **预训练**3. **扩展法则**4. **对齐(Alignment)**5. **评估*…...

基于LLM的6G空天地一体化网络自进化安全框架

摘要 最近出现的6G空天地一体化网络(SAGINs)整合了卫星、空中网络和地面通信,为各种移动应用提供普遍覆盖。然而,SAGINs的高度动态、开放和异构的性质带来了严重的安全问题。构建SAGINs的防御体系面临两个初步挑战:1)…...

【Mac 从 0 到 1 保姆级配置教程 12】- 安装配置万能的编辑器 VSCode 以及常用插件

文章目录 前言安装 VSCode基础配置常用插件1. 通用开发工具2. 编程语言支持3. 数据库工具4. 主题与界面美化5. 效率工具6. Markdown 工具7. 容器开发8. AI 辅助编程9. 团队协作 最后系列教程 Mac 从 0 到 1 保姆级配置教程目录,点击即可跳转对应文章: 【…...

数据库与SQL核心技术解析:从基础到JDBC编程实战

数据库技术作为现代信息系统的核心,贯穿于数据存储、查询优化、事务管理等关键环节。本文将系统讲解数据库基础知识、SQL语言核心操作、索引与事务机制,并结合Java数据库编程(JDBC)实践,助你构建完整的数据库技术体系。…...

JUC并发编程(上)

一、JUC学习准备 核心知识点:进程、线程、并发(共享模型、非共享模型)、并行 预备知识: 基于JDK8,对函数式编程、lambda有一定了解 采用了slf4j打印日志 采用了lombok简化java bean编写 二、进程与线程 进程和线程概念 两者对比…...

postgres--MVCC

PostgreSQL 的 MVCC(Multi-Version Concurrency Control,多版本并发控制) 是其实现高并发和高性能的核心机制,支持多个事务同时读写数据库而无需加锁阻塞。它的核心思想是通过保留数据的多个版本来避免读写冲突,从而提…...

nanodet配置文件分析

以下是针对 NanoDet-Plus-M-1.5x_416 配置文件的逐模块解析,以及调整参数的作用和影响范围: 1. 模型架构(model) Backbone(骨干网络) backbone:name: ShuffleNetV2model_size: 1.5x # 控制网络宽度&…...

【Linux网络】HTTP

应用层协议 HTTP 前置知识 我们上网的所有行为都是在做IO,(我的数据给别人,别人的数据给我)图片。视频,音频,文本等等,都是资源答复前需要先确认我要的资源在哪台服务器上(网络IP&…...

Unity中AssetBundle使用整理(一)

一、AssetBundle 概述 AssetBundle 是 Unity 用于存储和加载游戏资源(如模型、纹理、预制体、音频等)的一种文件格式。它允许开发者将游戏资源打包成独立的文件,在运行时动态加载,从而实现资源的按需加载、更新以及减小初始安装包…...

CMOS内存的地址空间在主内存空间中吗?

CMOS内存(即CMOS RAM)的地址空间不位于主内存地址空间(如0x00000-0xFFFFF)内,而是通过独立的I/O端口地址进行访问,具体如下: ​1. CMOS内存的物理存储与地址机制​ CMOS RAM芯片通常集成在主板…...

大模型应用中常说的Rerank是什么技术?

Rerank技术详解 一、定义与基本原理 Rerank(重排序)是一种在信息检索系统中用于优化搜索结果排序的技术,其核心目标是通过二次评估和排序候选文档,提升结果的相关性和准确性。其运作机制通常分为两阶段: 初步检索:使用传统方法(如BM25关键词匹配或Embedding向量检索)…...

Python-MCPInspector调试

Python-MCPInspector调试 使用FastMCP开发MCPServer,熟悉【McpServer编码过程】【MCPInspector调试方法】-> 可以这样理解:只编写一个McpServer,然后使用MCPInspector作为McpClient进行McpServer的调试 1-核心知识点 1-熟悉【McpServer编…...

C 语言数据结构基石:揭开数组名的面纱与计算数组大小

各类资料学习下载合集 ​​https://pan.quark.cn/s/8c91ccb5a474​​ 在前面的文章中,我们已经学习了 C 语言一维数组的定义和初始化。我们知道数组是用来存储一系列相同类型数据的集合,并通过下标来访问每个元素。但是,除了通过下标访问单个元素,数组名本身在 C 语言中也…...

Java高频面试之并发编程-15

hello啊,各位观众姥爷们!!!本baby今天又来报道了!哈哈哈哈哈嗝🐶 面试官:as-if-serial 是什么?单线程的程序一定是顺序执行的吗? as-if-serial 规则 定义: …...

MySQL数据库迁移SQL语句指南

MySQL数据库迁移SQL语句指南 一、基础迁移方法 1. 使用mysqldump进行全量迁移 -- 导出源数据库(在命令行执行) mysqldump -u [源用户名] -p[源密码] --single-transaction --routines --triggers --events --master-data2 [数据库名] > migration…...

Vue:生命周期钩子

深入理解 Vue 的钩子函数(生命周期函数) Vue 的钩子函数(生命周期函数)是 Vue 实例在不同阶段自动调用的函数。可以在 Vue 实例的创建、更新、销毁等阶段插入自己的逻辑。 钩子函数的作用 想象一下,Vue 实例的生命周…...

深入理解设计模式之原型模式(Prototype Pattern)

一、为什么需要原型模式? 在传统对象创建方式中,我们通过new关键字直接调用构造函数创建实例。但当遇到以下场景时: 对象初始化需要消耗大量资源(如数据库连接)需要创建的对象与现有实例高度相似希望屏蔽对象创建的复…...

K8S cgroups详解

以下是 Kubernetes 中 cgroups(Control Groups) 的详细解析,涵盖其核心原理、在 Kubernetes 中的具体应用及实践操作: 一、cgroups 基础概念 1. 是什么? cgroups 是 Linux 内核提供的 资源隔离与控制机制&#xff0c…...

ARMV8 RK3399 u-boot TPL启动流程分析 --start.S

上电后运行的第一支文件&#xff1a;arch/arm/cpu/armv8/start.S CONFIG_ENABLE_ARM_SOC_BOOT0_HOOK1 #include <asm/arch/boot0.h> 跳转到 arch/arm/include/asm/arch-rockchip/boot0.h CONFIG_SPL_BUILD1 b 1f ROCKCHIP_EARLYRETURN_TO_BROMno TINY_FRAMEWORKno …...

【网络原理】数据链路层

目录 一. 以太网 二. 以太网数据帧 三. MAC地址 四. MTU 五. ARP协议 六. DNS 一. 以太网 以太网是一种基于有线或无线介质的计算机网络技术&#xff0c;定义了物理层和数据链路层的协议&#xff0c;用于在局域网中传输数据帧。 二. 以太网数据帧 1&#xff09;目标地址 …...

保姆级教程|YOLO11改进】【卷积篇】【4】使用RFAConv感受野注意力卷积,重塑空间特征提取,助力高效提点

《------往期经典推荐------》 一、AI应用软件开发实战专栏【链接】 项目名称项目名称1.【人脸识别与管理系统开发】2.【车牌识别与自动收费管理系统开发】3.【手势识别系统开发】4.【人脸面部活体检测系统开发】5.【图片风格快速迁移软件开发】6.【人脸表表情识别系统】7.【…...

虚幻引擎5-Unreal Engine笔记之常用核心类的继承关系

虚幻引擎5-Unreal Engine笔记之常用核心类的继承关系 code review! 文章目录 虚幻引擎5-Unreal Engine笔记之常用核心类的继承关系1.UE5中常用核心类的继承关系1.1.简化版1.2.plantuml图1.3.plantuml代码1.4.关于大写字母U和A2.1.组件和类的关系&#xff0c;组件也是类吗&…...

力扣2680题解

记录 2025.5.9 题目&#xff1a; 思路&#xff1a; 1.计算初始或值&#xff1a;首先计算数组中所有元素的按位或结果 allOr&#xff0c;这表示在不进行任何左移操作时数组的或值。 2.计算固定或值&#xff1a;在计算 allOr 的同时&#xff0c;计算一个 fixed 值&#xff0c;…...

搭建基于chrony+OpenSSL(NTS协议)多层级可信时间同步服务

1、时间同步服务的层级概念 在绝大多数IT工程师实际工作过程中&#xff0c;针对于局域网的时间同步&#xff0c;遇到最多的场景是根据实际的需求&#xff0c;搭建一个简单的NTP时间同步服务以时间对局域网中的服务器、网络设备、个人电脑等基础设施实现同步授时功能。虽然这样…...

虚拟内存:深入解析与性能优化

文章目录 虚拟内存的概念虚拟内存的实现方式虚拟内存的页面置换算法虚拟内存的性能影响结论 在现代计算机系统中&#xff0c;虚拟内存&#xff08;Virtual Memory&#xff09;是一种至关重要的技术&#xff0c;它极大地提高了系统的多任务处理能力和内存利用率。本文将深入探讨…...

元数据和主数据

元数据和主数据是数据管理中的两个关键概念&#xff0c;其核心区别如下&#xff1a; 1. 定义与本质 元数据&#xff08;Metadata&#xff09; “关于数据的数据”&#xff0c;用于描述数据的属性、结构、来源、用途等上下文信息。 示例&#xff1a;数据库表的字段名称、数据类型…...

JavaScript事件处理全解析:从基础到最佳实践

在现代Web开发中&#xff0c;事件处理是构建交互式应用的核心技术。JavaScript提供了多种事件绑定方式&#xff0c;每种方法都有其适用场景和特点。本文将深入探讨7种主流的事件绑定方法&#xff0c;通过代码示例和原理分析&#xff0c;帮助开发者选择最合适的解决方案。 一、…...

高级数据结构:线段树

线段树概述 线段树是一种处理区间问题的优越算法&#xff0c;也是算法竞赛的常客。 线段树的特点是&#xff0c;类似于一棵二叉树&#xff0c;将一个序列分解成多个区间并储存在二叉树上。 例如&#xff0c;把区间 [ 1 , 10 ] [1,10] [1,10]作为树的根节点&#xff0c;然后把…...

精讲C++四大核心特性:内联函数加速原理、auto智能推导、范围for循环与空指针进阶

前引&#xff1a;在C语言长达三十余年的演进历程中&#xff0c;每一次标准更新都在试图平衡性能与抽象、控制与安全之间的微妙关系。从C11引入的"现代C"范式开始&#xff0c;开发者得以在保留底层控制能力的同时&#xff0c;借助语言特性大幅提升代码的可维护性与安全…...

用ffmpeg压缩视频参数建议

注意:代码中的斜杠\可以删除 一、基础压缩命令&#xff08;画质优先) ffmpeg -i input.mp4 \-c:v libx264 -preset slow -crf 23 \ # H.264编码&#xff0c;平衡速度与质量-c:a aac -b:a 128k \ # 音频压缩-vf "scaleif(gt(a,16/9),1920,-2):if(…...

uni-app学习笔记(二)--vue页面代码的构成和新建页面

vue页面的构成 一.template 模板区&#xff0c;主要放html布局&#xff0c;注意&#xff0c;如果是开发uni-app&#xff0c;模板区不要放div,h1等标签了&#xff0c;用了在小程序和app端起不到作用。具体应该使用哪些组件&#xff0c;可在uni-app官网上查看&#xff1a;组件-…...

机器语言程序、汇编语言程序、硬件描述语言程序、编译程序、解释程序和链接程序

程序类型定义与核心特征处理对象 / 输入输出结果所属领域典型例子 / 作用机器语言程序由二进制指令&#xff08;0/1 序列&#xff09;构成&#xff0c;可被 CPU 直接执行&#xff0c;与硬件架构强绑定。无&#xff08;直接执行&#xff09;无&#xff08;直接运行&#xff09;低…...

智能语音助手的未来:从交互到融合

摘要 随着人工智能技术的不断进步&#xff0c;智能语音助手已经成为我们生活中不可或缺的一部分。从简单的语音指令到复杂的多模态交互&#xff0c;语音助手正在经历一场深刻的变革。本文将探讨智能语音助手的发展历程、当前的技术瓶颈以及未来的发展方向&#xff0c;特别是其在…...

Redis从基础到高阶应用:核心命令解析与延迟队列、事务消息实战设计

Redis基础知识 #切换数据库 bd:0>select 2 "OK" bd:2>dbsize "0" #清空数据库 bd:0>flushdb "OK" #设置值 bd:0>set name "lyt" "OK" #查看所有key bd:0>keys *1) "name" #获取key bd:0>get …...

操作系统原理实验报告

操作系统原理课程的实验报告汇总 实验三&#xff1a;线程的创建与撤销 实验环境&#xff1a;计算机一台&#xff0c;内装有VC、office等软件 实验日期&#xff1a;2024.4.11 实验要求&#xff1a; 1.理解&#xff1a;Windows系统调用的基本概念&#xff0c;进程与线程的基…...

Python爬虫实战:研究nodejs aes加密

1. 引言 1.1 研究背景与意义 在当今数字化时代,Web 数据的价值日益凸显。通过爬虫技术获取公开数据并进行分析,能够为企业决策、学术研究等提供有力支持。然而,为了保护数据安全和隐私,许多网站采用了加密技术对数据进行保护,其中 AES 加密是一种常见且安全的加密算法。…...

线程的一些事(2)

在java中&#xff0c;线程的终止&#xff0c;是一种“软性”操作&#xff0c;必须要对应的线程配合&#xff0c;才能把终止落实下去 然而&#xff0c;系统原生的api其实还提供了&#xff0c;强制终止线程的操作&#xff0c;无论线程执行到哪&#xff0c;都能强行把这个线程干掉…...