系列綜述：
💞目的：本系列是個人整理為了秋招面試的，整理期間苛求每個知識點，平衡理解簡易度與深入程度。
🥰來源：材料主要源于左程云算法課程進行的，每個知識點的修正和深入主要參考各平臺大佬的文章，其中也可能含有少量的個人實驗自證。
🤭結語：如果有幫到你的地方，就點個贊和關注一下唄，謝謝🎈🎄🌷！！！
🌈【C++】秋招&實習面經匯總篇

---

---

😊點此到文末驚喜??

前綴樹

1. 每個結點
   • int pass：表示當前結點通過的次數
   • int end：表示該節(jié)點作為字符串結尾次數
2. 作用
   • 空間換時間，通過字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
   • 高效地存儲和檢索字符串數據集中的鍵
   • 可用于自動補完和拼寫檢查。
3. 效率上
   • 哈希表時間效率高，但是前綴樹可以進行動態(tài)查詢，即查詢一個單詞可以只查詢一部分即可返回結果
   • 支持查詢以x字符作為前綴的數量
4. 前綴樹的基本結構

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;	// 獲得根節(jié)點的引用node->pass++;		// 根節(jié)點被經過了，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;};

前綴樹

1. 【排序相關】

---

少年，我觀你骨骼清奇，穎悟絕倫，必成人中龍鳳。 不如點贊·收藏·關注一波

---

🚩點此跳轉到首行??

參考博客

1. 對數器
2. 單調隊列
3. 快速鏈表quicklist
4. 《深入理解計算機系統(tǒng)》
5. 侯捷C++全系列視頻
6. 待定引用
7. 待定引用
8. 待定引用