【左程云算法全讲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组件下拉选项框打开全部都是无数据,而且控制台报错,但是新添加的数据是正常显示的。对比了原因之后发现,新的数据前端传给后端的格式&#…...
HoRain云--VS Code 中使用 Jupyter Notebook
🎬 HoRain云小助手:个人主页 🔥 个人专栏: 《Linux 系列教程》《c语言教程》 ⛺️生活的理想,就是为了理想的生活! ⛳️ 推荐 前些天发现了一个超棒的服务器购买网站,性价比超高,大内存超划算!…...
零基础到量化交易专家:QuantConnect教程库的完整学习路径指南
零基础到量化交易专家:QuantConnect教程库的完整学习路径指南 【免费下载链接】Tutorials Jupyter notebook tutorials from QuantConnect website for Python, Finance and LEAN. 项目地址: https://gitcode.com/gh_mirrors/tutorials2/Tutorials 想要从金融…...
盟接之桥®制造业EDI软件:专注制造,为制造业服务,让全球供应链协同更有底气
在全球制造业数字化转型的浪潮中,供应链的协同效率已成为企业核心竞争力的关键一环。对于汽车零部件、机械制造、电子电器等领域的制造企业而言,电子数据交换(EDI)早已不是“锦上添花”的辅助工具,而是进入全球主流供应…...
YT8521/YT8531 PHY驱动源码解析:从Linux内核视角看国产网络芯片的适配
YT8521/YT8531 PHY驱动深度解析:Linux内核适配国产网络芯片的技术实践 在嵌入式系统和网络设备开发领域,PHY芯片作为物理层接口的关键组件,其驱动实现质量直接影响网络性能和稳定性。Motorcomm(裕太微电子)的YT8521和Y…...
如何3步打造电影级Minecraft画面:Revelation光影包完整配置指南
如何3步打造电影级Minecraft画面:Revelation光影包完整配置指南 【免费下载链接】Revelation An explorative shaderpack for Minecraft: Java Edition 项目地址: https://gitcode.com/gh_mirrors/re/Revelation 你是否厌倦了Minecraft中单调的光影效果&…...
Java 三维数组超详细实操(本质 + 定义 + 遍历 + 实战,可直接运行)
Java 中三维数组是二维数组的数组,可以理解为多个二维数组(表格)组成的集合(比如一个班级的多份成绩单、一个立体矩阵),日常开发中极少用到(仅特殊场景如三维建模、多层数据统计会用)…...
掌握八大网盘直链解析:LinkSwift下载助手全面解析
掌握八大网盘直链解析:LinkSwift下载助手全面解析 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 ,支持 百度网盘 / 阿里云盘 / 中国移动云盘 / 天翼云盘…...
Qwen3.5-9B-GGUF效果展示:Gated Delta Networks在长文本摘要中的优势体现
Qwen3.5-9B-GGUF效果展示:Gated Delta Networks在长文本摘要中的优势体现 1. 模型概览与技术亮点 Qwen3.5-9B-GGUF是基于阿里云通义千问3.5系列(2026年3月开源)的90亿参数稠密模型,经过GGUF格式量化后的高效推理版本。该模型采用…...
IDE Eval Resetter:JetBrains试用期无限重置终极指南
IDE Eval Resetter:JetBrains试用期无限重置终极指南 【免费下载链接】ide-eval-resetter 项目地址: https://gitcode.com/gh_mirrors/id/ide-eval-resetter 还在为JetBrains IDE试用期到期而烦恼吗?想象一下这个场景:你正在专注编码…...
Mac微信防撤回插件终极指南:完整保护你的重要对话内容
Mac微信防撤回插件终极指南:完整保护你的重要对话内容 【免费下载链接】WeChatIntercept 微信防撤回插件,一键安装,仅MAC可用,支持v3.7.0微信 项目地址: https://gitcode.com/gh_mirrors/we/WeChatIntercept 你是否曾经因为…...
