免费网站建设价格费用,正规app开发价格表,系统软件,网站开发公司建站源码系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于左程云算法课程进行的#xff0c;每个知识点的修正和深入主要参考… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于左程云算法课程进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 前缀树前缀树 参考博客 点此到文末惊喜↩︎
前缀树
每个结点 int pass表示当前结点通过的次数int end表示该节点作为字符串结尾次数 作用 空间换时间通过字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。高效地存储和检索字符串数据集中的键可用于自动补完和拼写检查。 效率上 哈希表时间效率高但是前缀树可以进行动态查询即查询一个单词可以只查询一部分即可返回结果支持查询以x字符作为前缀的数量 前缀树的基本结构
struct Node{int pass; // 该结点的通过数int end; // 以该结点为结尾的结尾数vectorint *nexts; // 如果字符过多可使用unordered_mapchar, Node nexts Node(){pass 0;end 0;next new vectorNode(26);}
};class Trie{
public:Trie(){root new Node();}void insert(string str) {// 健壮性检查if (str.empty()) return ;// 初始化Node *node root; // 获得根节点的引用node-pass; // 根节点被经过了passint 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全系列视频 待定引用 待定引用 待定引用
