【左程云算法全讲4】前缀树、非比较排序
系列综述:
💞目的:本系列是个人整理为了秋招面试的,整理期间苛求每个知识点,平衡理解简易度与深入程度。
🥰来源:材料主要源于左程云算法课程进行的,每个知识点的修正和深入主要参考各平台大佬的文章,其中也可能含有少量的个人实验自证。
🤭结语:如果有帮到你的地方,就点个赞和关注一下呗,谢谢🎈🎄🌷!!!
🌈【C++】秋招&实习面经汇总篇
文章目录
- 前缀树
- 前缀树
- 参考博客
😊点此到文末惊喜↩︎
前缀树
- 每个结点
- int pass:表示当前结点通过的次数
- int end:表示该节点作为字符串结尾次数
- 作用
- 空间换时间,通过字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
- 高效地存储和检索字符串数据集中的键
- 可用于自动补完和拼写检查。
- 效率上
- 哈希表时间效率高,但是前缀树可以进行动态查询,即查询一个单词可以只查询一部分即可返回结果
- 支持查询以
x字符作为前缀的数量
- 前缀树的基本结构
struct Node{int pass; // 该结点的通过数int end; // 以该结点为结尾的结尾数vector<int> *nexts; // 如果字符过多可使用unordered_map<char, Node> nexts Node(){pass = 0;end = 0;next = new vector<Node>(26);}
};class Trie{
public:Trie(){root = new Node();}void insert(string str) {// 健壮性检查if (str.empty()) return ;// 初始化Node *node = root; // 获得根节点的引用node->pass++; // 根节点被经过了,pass++int path = 0; // 表示要走的路径// 算法部分for (int i = 0; i < str.size(); ++i) { // 遍历字符串path = str[i] - 'a'; // 求出nexts中的下一个路径// 无结点建立,有结点复用if (node->nexts[path] == nullptr) {node->nexts[path] = new Node();}node = node->nexts[path]; // 访问下一个node->pass++; // 访问数+1}node->end++; // 结尾结点结尾数end++}int Search(string str) {if (str.size() == 0) return 0;Node *node = root;int path = 0;for (int i = 0; i < str.size(); ++i) {// doingpath = str[i] - 'a';if (node->nexts[path] == nullptr) return 0;// 迭代node = node->next[path];}return node->end;}int TrieNumber(string prev) {if (prev.empty()) return 0;Node *node = root;int path = 0; for (int i = 0; i < prev.size(); ++i) {path = prev[i] - 'a';if (node->nexts[path] == nullptr) return 0;node = node->nexts[path];}return node->pass;}// java会自动释放,但是cpp有内存泄漏问题,需要使用shared_ptr进行处理void DeleteTrie(string str) {if (search(word) != 0) { // 有该字符串才能删除Node *node = root;int path = 0;for (int i = 0; i < str.size(); ++i) {if (--node->nexts[path].pass == 0) {node.nexts[path] = nullptr;// releasereturn ;}node = node->nexts[path];}node->end--;}}private:Node root;};
前缀树
- 【排序相关】
🚩点此跳转到首行↩︎
参考博客
- 对数器
- 单调队列
- 快速链表quicklist
- 《深入理解计算机系统》
- 侯捷C++全系列视频
- 待定引用
- 待定引用
- 待定引用
相关文章:
【左程云算法全讲4】前缀树、非比较排序
系列综述: 💞目的:本系列是个人整理为了秋招面试的,整理期间苛求每个知识点,平衡理解简易度与深入程度。 🥰来源:材料主要源于左程云算法课程进行的,每个知识点的修正和深入主要参考…...
微头条项目实战:新增RequestHeader注解
1、RequestHeader package com.csdn.mymvc.annotation; import java.lang.annotation.*; Target(ElementType.PARAMETER) Retention(RetentionPolicy.RUNTIME) Inherited public interface RequestHeader { }2、DispatcherServlet package com.csdn.mymvc.core; import com.csd…...
E云管家个微协议框架--新版本的利器
在互联网时代,高效、可靠的互联网协议对于实现稳定、安全的数据传输至关重要。E云管家作为一项创新性的IPAD协议构建工具,基于IPAD8.0.37协议为开发者提供了强大而灵活的功能,使他们能够轻松构建高效的通信协议。本文将介绍E云管家的主要特点…...
百度上线“文心一言”付费版本,AI聊天机器人市场竞争加剧
原创 | 文 BFT机器人 百度不愧是我国AI技术领域的先行者,每年致力于人工智能领域取得技术产品的突破和创新。据爆料称,百度的文心一言有突破了新境界,开创了文心大模型4.0会员版本。从线上的to C产品到试水商业化,百度都是争先走…...
代码随想录算法训练营第四十七天丨 动态规划part10
121. 买卖股票的最佳时机 思路 动态规划 动规五部曲分析如下: 确定dp数组(dp table)以及下标的含义 dp[i][0] 表示第i天持有股票所得最多现金 ,这里可能有疑惑,本题中只能买卖一次,持有股票之后哪还有…...
微前端:quankun
零: 前言 微前端可以将大应用拆分功能独立的微应用,可独立开发部署, 每个微应用可以采用自己的技术栈,这样更好维护和拓展。微前端也会存在跨域 权限控制 数据共享 性能(页面加载时间) 安全 多团队协作(一个团队负责一个页面或模…...
CSDN每日一题学习训练——Java版(克隆图、最接近的三数之和、求公式的值)
版本说明 当前版本号[20231109]。 版本修改说明20231109初版 目录 文章目录 版本说明目录克隆图题目解题思路代码思路参考代码 最接近的三数之和题目解题思路代码思路参考代码 求公式的值题目解题思路代码思路参考代码 克隆图 题目 给你无向 连通(https://baike.baidu.com…...
XOR Construction
思路: 通过题目可以得出结论 b1^b2a1 b2^b3a2 ....... bn-1^bnan-1 所以就可以得出 (b1^b2)^(b2^b3)a1^a2 b1^b3a1^a2 有因为当确定一个数的时候就可以通过异或得到其他所有的数,且题目所求的是一个n-1的全排列 那么求出a的前缀异或和arr之后…...
K8S容器持续Terminating无法正常关闭(sider-car容器异常,微服务容器正常)
问题 K8S上出现大量持续terminating的Pod,无法通过常规命令删除。需要编写脚本批量强制删除持续temminating的Pod:contribution-xxxxxxx。 解决 获取terminating状态的pod名称的命令: # 获取media命名空间下,名称带contributi…...
Spring 循环依赖
文章目录 内容总结循环依赖 内容总结 循环依赖 循环依赖只存在于 Spring 中, 是因为 Spring 创建 Bean 的流程中, 依赖注入阶段, 会先从单例池中找, 没有再从定义池中找, 针对定义池中找到的候选项会通过 getBean 创建其单例并缓存到单例池, 此机制导致了存在循环依赖的问题.…...
MySQL 8.0.13升级到8.0.35记录 .NET
1、修改表结构的字符集 utf8 修改成 utf8mb4 utf8_general_ci 修改成 utf8mb4_0900_ai_ci 注:所有地方都要替换。 否则会报错误提示:Character set utf8mb3 is not supported 下面是.NET环境升级遇到的问题 2、MySQL Connector Net 8.0.13 在程…...
flink udtaf 常年不能用
[FLINK-32807] when i use emitUpdateWithRetract of udtagg,bug error - ASF JIRA flink1.18发布的时候 他都显示未解决 但是文档上一直有udtaf...
路由汇总的四要点
1.是基于链路级的还是进程级的? RIP和eigrp都是基于接口的链路级汇总,而OSPF是基于进程的 2.汇总路由什么时候消失? 最后一条明细路由消失的时候,汇总路由消失。 3.汇总之后,汇总路由被通告,本地是否会产生一条指向NULL接口的…...
HashMap存值、取值及哈希碰撞原理分析
HashMap中的put()和get()的实现原理: map.put(k,v)实现原理 首先将k,v封装到Node对象当中(节点)。 然后它的底层会调用K的hashCode()方法得出hash值。 通过哈希表函数/哈希算法,将hash值转换成数组的下标,下标位置上…...
【SVN】
SVN 1 svn使用1.1 主干合并到分支1.2 分支合并到主干1.3 分支建立1.4 创建分支1.5 切换分支1.6 合并分支1.7 删除分支 2 概念理解 1 svn使用 1.1 主干合并到分支 首先,在本地trunk中先update一下,有冲突的解决冲突,保证trunk和repository已…...
编程语言,脚本语言
脚本语言上手快,快速实现一个小应用如python;编程语言重型,需复杂的设计和较长时间的开发,如java、c...
探索双十一:从技术角度剖析电商狂欢节
每年的11月11日,全球最大的在线购物狂欢节“双十一”在中国掀起了一场规模空前的消费风暴。以阿里巴巴为代表的电商平台和众多品牌商家,不仅为消费者提供了数以亿计的优惠商品,同时也将这一活动打造成了一个科技与商业完美结合的标志事件。本…...
Ubuntu LTS 坚持 10 年更新不动摇
Linux 内核开发者 Jonathan Corbet 此前在欧洲开源峰会上宣布,LTS 内核的支持时间将从六年缩短至两年,原因在于缺乏使用和缺乏支持。稳定版内核维护者 Greg Kroah-Hartman 也表示 “没人用 LTS 内核”。 近日,Ubuntu 开发商 Canonical 发表博…...
Python将多个相同格式的变量存储到列表中
在日常写代码过程中往往会遇到多个相同格式名称的变量需要存储到一个list。 怎么优雅地写出来呢 首先定义变量,然后使用列表推导式存储到列表中 # 定义变量 a_1, a_2 , # 列表推导式完成 a_list [globals()[fa_{i}] for i in range(1, 3)]...
前端字符串转数组对象实现方式-开发bug总结6
问题描述: 后台管理系统,这次投产完线上出现了个问题!element-ui组件下拉选项框打开全部都是无数据,而且控制台报错,但是新添加的数据是正常显示的。对比了原因之后发现,新的数据前端传给后端的格式&#…...
告别命令行恐惧!用VSCode图形化搞定树莓派Pico开发(Windows保姆级教程)
告别命令行恐惧!用VSCode图形化搞定树莓派Pico开发(Windows保姆级教程) 嵌入式开发向来以门槛高著称,尤其是面对复杂的命令行工具链时,许多初学者望而却步。树莓派Pico作为一款性价比极高的微控制器,其开发…...
Docker健康检查假阳性泛滥,5个systemd+healthcheck组合误判案例,附自动化验证脚本
第一章:Docker健康检查假阳性泛滥,5个systemdhealthcheck组合误判案例,附自动化验证脚本Docker容器健康检查(HEALTHCHECK)与systemd服务管理深度集成时,常因信号传递延迟、进程状态竞态、cgroup资源隔离偏差…...
医疗AI项目实战:手把手教你用pydicom库为PNG图像注入DICOM‘灵魂’(含完整元数据配置)
医疗AI数据工程实战:用Python构建符合临床标准的DICOM元数据体系 在医疗AI项目的开发流程中,数据工程环节往往决定着模型的成败。当我们使用公开的PNG/JPG医学图像数据集时,如何将其转化为具有完整临床元数据的DICOM文件,是每个医…...
WinBtrfs:Windows平台原生读写Btrfs文件系统的完整指南
WinBtrfs:Windows平台原生读写Btrfs文件系统的完整指南 【免费下载链接】btrfs WinBtrfs - an open-source btrfs driver for Windows 项目地址: https://gitcode.com/gh_mirrors/bt/btrfs 你是否曾经遇到过这样的烦恼?在Windows系统上无法直接访…...
nRF24L01模块性能调优笔记:基于STC8H的SPI通信,如何突破700包/秒的传输瓶颈?
nRF24L01模块性能调优实战:从SPI优化到硬件设计的全方位突破 在嵌入式无线通信领域,nRF24L01凭借其优异的性价比和稳定的2.4GHz传输性能,成为众多开发者的首选。但当我们需要将其性能推向极限时,单纯的驱动实现远远不够。本文将分…...
数据资产盘点与治理全景指南:从概念厘清到落地实战的完整方法论(PPT)
我在做数字化咨询这些年,遇到最多的一类问题是这样的:企业IT部门买了大数据平台,用了两三年,系统里存了海量的数据,但业务部门一要报表,还是要手工汇总;老板问一个经营指标,下面给出…...
每日热门skill:让你的AI告别被动等待:AgentAutonomyKit实现智能体自主工作
当Claude Max每月给你几十万token额度,你的AI却每天只用了不到20%——不是它不够聪明,是它一直在等你"喂饭"。 这个Skill,让你的AI从"等指令"变成"自己找事干"。 文末有下载链接。 一、问题:你的AI正在大规模浪费资源 先问自己一个问题: …...
ComfyUI-Manager:AI绘画工作流的高效管理解决方案
ComfyUI-Manager:AI绘画工作流的高效管理解决方案 【免费下载链接】ComfyUI-Manager ComfyUI-Manager is an extension designed to enhance the usability of ComfyUI. It offers management functions to install, remove, disable, and enable various custom no…...
炒股入门完全指南:2026年零基础用AI工具辅助新手,从看不懂到会分析只需这几步
第一次打开炒股软件,满屏红绿K线、各种指标缩写,脑子完全空白——这是大多数炒股入门新手的第一反应。 好消息是,现在炒股入门的门槛已经比5年前低很多了。AI工具的出现,让"看不懂就问AI"变成了真实可行的学习路径。本…...
LFM2-2.6B-GGUF实战案例:DevOps团队CI/CD日志智能归因分析应用
LFM2-2.6B-GGUF实战案例:DevOps团队CI/CD日志智能归因分析应用 1. 项目背景与价值 在DevOps实践中,CI/CD流水线的日志分析一直是个痛点。当构建失败或测试不通过时,工程师往往需要花费大量时间在冗长的日志中寻找问题根源。LFM2-2.6B-GGUF模…...
