C++常用數(shù)據(jù)結(jié)構(gòu)
鏈表內(nèi)存的申請與釋放滑動窗口前綴和/積與后綴和/積差分數(shù)組線段樹前綴樹/字典樹（Trie）單調(diào)棧單調(diào)隊列并查集二叉樹創(chuàng)建二叉樹二叉樹的遍歷二叉樹遍歷的變體平衡二叉樹（AVL）與二叉搜索樹N叉樹圖拓撲排序鏈表鏈表（單鏈表）的基本操作及C語言實現(xiàn)鏈表中存放的不是基本數(shù)據(jù)類型，需要用結(jié)構(gòu)體實現(xiàn)自定義：typedef struct Link{ char elem;//代表數(shù)據(jù)域 struct Link * next;//代表指針域，指向直接后繼元素}link;12345next的值實際上就是下一個節(jié)點的地址，當前節(jié)點為末節(jié)點時，next的值設(shè)為空指針。像上面這種只包含一個指針域、由n個節(jié)點鏈接形成的鏈表，就稱為線型鏈表或者單向鏈表，鏈表只能順序訪問，不能隨機訪問，鏈表這種存儲方式最大缺點就是容易出現(xiàn)斷鏈。頭結(jié)點和頭指針的區(qū)別：頭指針是一個指針，頭指針指向鏈表的頭結(jié)點或者首元結(jié)點；頭結(jié)點是一個實際存在的結(jié)點，它包含有數(shù)據(jù)域和指針域。兩者在程序中的直接體現(xiàn)就是：頭指針只聲明而沒有分配存儲空間，頭結(jié)點進行了聲明并分配了一個結(jié)點的實際物理內(nèi)存。單鏈表中可以沒有頭結(jié)點，但是不能沒有頭指針！單向鏈表+頭指針+尾指針：struct ListNode { int val; ListNode next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode next) : val(x), next(next) {} };ListNode head = nullptr, tail = nullptr;//從尾部插入結(jié)點head = tail = new ListNode(num1);tail->next = new ListNode(num2);tail = tail->next;123456789101112注意：nullptr在C++11中就是代表空指針，不能被轉(zhuǎn)換成數(shù)字。在編譯器進行解釋程序時，NULL會被直接解釋成0。鏈表的題通常需要注意幾點：舍得用變量，千萬別想著節(jié)省變量，否則容易被邏輯繞暈head 有可能需要改動時，先增加一個 假head，返回的時候直接取 假head.next，這樣就不需要為修改 head 增加一大堆邏輯了。while(p->next&&p->next->next)while(p->next&&p->next->val==x)p->next必須要寫在前面ListNode k=new ListNode(0,head);//不要省建立頭結(jié)點的功夫此外還需要注意，能用f作為判定條件，就盡量不要以f->next作為判定條件，若f直接為空指針，會直接炸掉。這里涉及到短路或、短路與的概念。//盡量不要以f->next作為判定條件，若f直接為空指針，會直接炸掉下面這個方法不好 while(f->next&&i<index-1) { f=f->next; i++; } //改成下面的樣子比較好NodeList f =head;int i=0;while(f&&i<index-1){ f=f->next; i++;}if(!f)//超出鏈表范圍則退出{ return;}if(f->next){ NodeList m=f->next; f->next=m->next; delete m;//delete與new匹配}1234567891011121314151617181920212223242526單向鏈表常用的初始化：//單向鏈表常用的初始化class MyLinkedList {private: struct NodeList { int val; NodeList next; NodeList():val(0),next(nullptr){}//{} NodeList(int n):val(n),next(nullptr){} };//; NodeList * head;public: MyLinkedList():head(nullptr) {}//默認構(gòu)造函數(shù)，調(diào)用時不用加（） Main函數(shù)調(diào)用MyLinkedList list;//不需要（），加括號會被誤認為調(diào)用函數(shù)123456789101112131415C++雙向鏈表模板：//C++雙向鏈表模板class MyList{private: struct ListNode { int val; ListNode next,prev; ListNode(int x):val(x),next(nullptr),prev(nullptr){} };private: //頭節(jié)點尾節(jié)點都為空，表示為空鏈表 ListNode head,tail; int size=0;public: MyList():size(0),head(nullptr),tail(nullptr){}12345678910111213141516反轉(zhuǎn)鏈表：從前往后挨著元素反轉(zhuǎn)，并記錄反轉(zhuǎn)頭prev，剩下未反轉(zhuǎn)部分的頭curr，以及下一個元素next。直到剩下未反轉(zhuǎn)頭curr為空。Prev初始值也為空，curr初始值為head。ListNode reverseList(ListNode head) { ListNode pre = nullptr; ListNode cur = head; ListNode nex ; while(cur) { nex = cur->next;//提前該語句 cur->next=pre; pre=cur; cur=nex; // nex = cur->next;//當cur為空指針時該語句會報錯，運行超時，需要將該語句提前 } return pre; }123456789101112131415易錯點是while判定條件里next需要提前寫，將實際遍歷的結(jié)點作為判定條件，否則容易runtime error。內(nèi)存的申請與釋放free和delete區(qū)別_prerfect_cat的博客free和mall匹配：釋放malloc出來動態(tài)內(nèi)存;delete和new匹配：釋放new出來的動態(tài)內(nèi)存空間。在類和對象的時候會有很大區(qū)別。在使用malloc和free來處理動態(tài)內(nèi)存的時候，僅僅是釋放了這個對象所占的內(nèi)存，而不會調(diào)用這個對象的析構(gòu)函數(shù)；使用new和delete就可以既釋放對象的內(nèi)存的同時，調(diào)用這個對象的析構(gòu)函數(shù)。delete釋放對象數(shù)組時：千萬不能丟失”[]”
如果用new 創(chuàng)建對象數(shù)組，那么只能使用對象的無參數(shù)構(gòu)造函數(shù)。例如Obj objects = new Obj[100];
// 創(chuàng)建100 個動態(tài)對象1在用delete 釋放對象數(shù)組時，留意不要丟了符號‘[ ]’。
例如delete []objects; // 正確的用法delete objects; // 錯誤的用法12后者相當于delete objects[0]，漏掉了另外99 個對象。new出來的是一段空間的首地址。所以一般需要用指針來存放這段地址。 //可以在new后面直接賦值 int p = new int(3); //也可以單獨賦值 //p = 3; //如果不想使用指針，可以定義一個變量，在new之前用“”表示new出來的內(nèi)容 int q = new int; //當new一個數(shù)組時，同樣用一個指針接住數(shù)組的首地址 int q = new int[3];12345678//這里是用一個結(jié)構(gòu)體指針接住結(jié)構(gòu)體數(shù)組的首地址//對于結(jié)構(gòu)體指針，個人認為目前這種賦值方法比較方便struct student{ string name; int score;};student stlist = new student[3]{{“abc”, 90}, {“bac”, 78}, {“ccd”, 93}};12345678滑動窗口什么是滑動窗口？其實就是一個隊列,比如下面例題中的字符串 abcabcbb，進入這個隊列（窗口）為 abc 滿足題目要求，當再進入 a，隊列變成了 abca，這時候不滿足要求。所以，我們要移動這個隊列！如何移動？我們只要把隊列的左邊的元素移出就行了，直到滿足題目要求！一直維持這樣的隊列，找出隊列出現(xiàn)最長的長度時候，求出解！時間復(fù)雜度：O(n)3. 無重復(fù)字符的最長子串給定一個字符串 s ，請你找出其中不含有重復(fù)字符的 最長子串 的長度。示例：輸入: s = “pwwkew”輸出: 3解釋: 因為無重復(fù)字符的最長子串是 “wke”，所以其長度為 3。請注意，你的答案必須是 子串 的長度，“pwke” 是一個子序列，不是子串?！痉治觥坑没瑒哟翱?#xff0c;固定最左邊 l，每次都從最右邊 r 開始擴張，出現(xiàn)重復(fù)元素時，刪除哈希集合中從 l 到重復(fù)元素下標之間的元素，將 l 進行更新，并繼續(xù)向右擴張 r 。關(guān)鍵點：如果依次遞增地枚舉子串的起始位置，那么子串的結(jié)束位置也是遞增的！因為當前結(jié)束位置前面都是無重復(fù)子串了，刪掉最左邊起始位置后，剩下的這一截更是無重復(fù)子串，所以每次移動右窗口指針時候只需要從上次結(jié)束位置開始就行。用哈希集合判斷重復(fù)。 int lengthOfLongestSubstring(string s) { if(s.empty()) return 0; int n = s.size(); unordered_set st; int l = 0, maxlen = 0; for(int r = 0; r < n; ++r){ //刪除哈希集合中從 l 到重復(fù)元素下標之間的元素，將 l 進行更新 while(st.find(s[r]) != st.end()){ st.erase(s[l]); ++l; } //每次右移r時，就更新一下最長長度， //以免出現(xiàn)整個字符串都無重復(fù)，遍歷到頭一直沒更新長度的情況 maxlen = max(r - l + 1, maxlen); st.insert(s[r]); } return maxlen; }123456789101112131415161718也可以用哈希表實現(xiàn)，用哈希表記錄每個元素出現(xiàn)的下標，可以精確知道刪除重復(fù)元素時的循環(huán)次數(shù)。 int lengthOfLongestSubstring(string s) { if(s.empty()) return 0; int n = s.size(); unordered_map<char, int> mp; //每次固定l, 右移r，出現(xiàn)重復(fù)元素時再更新l int l = 0, maxlen = 0; for(int r = 0; r < n; ++r){ //若發(fā)現(xiàn)重復(fù)字符，則通過哈希表找到第一個重復(fù)下標 //刪除從l到重復(fù)下標之間的哈希表元素，并將l重置為重復(fù)下標的下一個位置 if(mp.find(s[r]) != mp.end()){ int newl = mp[s[r]] + 1; for(int i = l; i < newl; i++){ mp.erase(s[i]); } l = newl; } //每次右移r時，就更新一下最長長度， //以免出現(xiàn)整個字符串都無重復(fù)，遍歷到頭一直沒更新長度的情況 maxlen = max(r - l + 1, maxlen); mp[s[r]] = r;; } return maxlen; }123456789101112131415161718192021222376. 最小覆蓋子串給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 “” 。注意：對于 t 中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。如果 s 中存在這樣的子串，我們保證它是唯一的答案。示例 1：輸入：s = “ADOBECODEBANC”, t = “ABC”輸出：“BANC”【分析】滑動窗口我們可以用滑動窗口的思想解決這個問題。在滑動窗口類型的問題中都會有兩個指針，一個用于「延伸」現(xiàn)有窗口的 r 指針，和一個用于「收縮」窗口的 l 指針。在任意時刻，只有一個指針運動，而另一個保持靜止。我們在 s 上滑動窗口，通過移動 r 指針不斷擴張窗口。當窗口包含 t 全部所需的字符后，如果能收縮，我們就收縮窗口直到得到最小窗口。如何判斷當前的窗口包含所有 t 所需的字符呢？我們可以用一個哈希表表示 t 中所有的字符以及它們的個數(shù)，用一個哈希表動態(tài)維護窗口中所有的字符以及它們的個數(shù)，如果這個動態(tài)表中包含 t 的哈希表中的所有字符，并且對應(yīng)的個數(shù)都不小于 t 的哈希表中各個字符的個數(shù)，那么當前的窗口是「可行」的。注意：這里 t 中可能出現(xiàn)重復(fù)的字符，所以我們要記錄字符的個數(shù)。舉個例子：如果 s = X X ? X A B C X X X X s = {\rm XX \cdots XABCXXXX}s=XX?XABCXXXX，t = A B C t = {\rm ABC}t=ABC，那么顯然 [ X X ? X A B C ] {\rm [XX \cdots XABC]}[XX?XABC] 是第一個得到的「可行」區(qū)間，得到這個可行區(qū)間后，我們按照「收縮」窗口的原則更新左邊界，得到最小區(qū)間。 unordered_map<char, int> ori, cnt; bool check(){ for(const auto& f:ori){ if(cnt[f.first] < f.second){ return false; } } return true; } string minWindow(string s, string t) { for(const char& c:t){ ori[c]++; } int l = 0, r = 0, ansl = -1; int len = INT_MAX, n = s.size(); while(r < n){ if(ori.find(s[r]) != ori.end()){ cnt[s[r]]++; } ++r; while(check() && l <= r){ if(r - l < len){ len = r - l; ansl = l; } if(ori.find(s[l]) != ori.end()){ cnt[s[l]]–; } ++l; } } return ansl == -1 ? string() : s.substr(ansl, len); }12345678910111213141516171819202122232425262728293031323334353637383940其他滑動窗口例題：滑動窗口講解438. 找到字符串中所有字母異位詞30. 串聯(lián)所有單詞的子串76. 最小覆蓋子串159. 至多包含兩個不同字符的最長子串209. 長度最小的子數(shù)組239. 滑動窗口最大值567. 字符串的排列632. 最小區(qū)間727. 最小窗口子序列例題講解：438. 找到字符串中所有字母異位詞給定兩個字符串 s 和 p，找到 s 中所有 p 的 異位詞 的子串，返回這些子串的起始索引。不考慮答案輸出的順序。異位詞 指由相同字母重排列形成的字符串（包括相同的字符串）。示例 1:輸入: s = “cbaebabacd”, p = “abc”輸出: [0,6]解釋: 起始索引等于 0 的子串是 “cba”, 它是"abc" 的異位詞。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的異位詞?！痉治觥吭谧址?s 中構(gòu)造一個長度為與字符串 p 的長度相同的滑動窗口，并在滑動中維護窗口中每種字母的數(shù)量；當窗口中每種字母的數(shù)量與字符串 p 中每種字母的數(shù)量相同時，則說明當前窗口為字符串 p 的異位詞。在算法的實現(xiàn)中，可以使用數(shù)組來存儲字符串 pp 和滑動窗口中每種字母的數(shù)量?！炯毠?jié)】當字符串 s 的長度小于字符串 p 的長度時，字符串 s 中一定不存在字符串 p 的異位詞。但是因為字符串 s 中無法構(gòu)造長度與字符串 p 的長度相同的窗口，所以這種情況需要單獨處理。此外，比較兩個數(shù)組是否相等時，可以直接用 “數(shù)組1 == 數(shù)組2” 來判斷。 vector findAnagrams(string s, string p) { int m = p.size(), n = s.size(); if(n < m) return {}; vector ans; vector scount(26); vector pcount(26); for(int i = 0; i < m; ++i){ ++scount[s[i] - ‘a(chǎn)’]; ++pcount[p[i] - ‘a(chǎn)’]; } for(int l = 0; l + m <= n; ++l){ if(l != 0){ ++scount[s[l + m -1] - ‘a(chǎn)’]; --scount[s[l - 1] - ‘a(chǎn)’]; } //判斷兩個數(shù)組是否相等，可以直接用 == if(scount == pcount){ ans.emplace_back(l); } } return ans; }12345678910111213141516171819202122下面第30題的過渡版寫法：用了一個哈希表來進出字符，初始時先存p的哈希值，再減去s中第一個窗口的哈希值，之后對s進行窗口滑動，以及哈希表字符進出，當字符鍵值為0時刪除該字符，當哈希表為空時表示匹配成功，可以存入輸出數(shù)組。 vector findAnagrams(string s, string p) { vector ans; unordered_map<char, int> mp; int m = p.size(), n = s.size(); //用字符串 p 來初始化哈希表 for(char &ch : p){ ++mp[ch]; } //字符串 s 的首個窗口 for(int i = 0; i < m && i < n; ++i){ if(–mp[s[i]] == 0){ mp.erase(s[i]); } } //對字符串 s 進行滑動窗口 for(int l = 0; l + m <= n; ++l){ if(l != 0){ //注意這里的++ 與 --特別容易搞混 if(–mp[s[l + m - 1]] == 0) mp.erase(s[l + m - 1]); if(++mp[s[l - 1]] == 0) mp.erase(s[l - 1]); } if(mp.empty()){ ans.emplace_back(l); } } return ans; }12345678910111213141516171819202122232425262730. 串聯(lián)所有單詞的子串給定一個字符串 s 和一些 長度相同 的單詞 words 。找出 s 中恰好可以由 words 中所有單詞串聯(lián)形成的子串的起始位置。注意子串要與 words 中的單詞完全匹配，中間不能有其他字符 ，但不需要考慮 words 中單詞串聯(lián)的順序。示例 1：輸入：s = “barfoothefoobarman”, words = [“foo”,“bar”]輸出：[0,9]解釋：從索引 0 和 9 開始的子串分別是 “barfoo” 和 “foobar” 。 輸出的順序不重要, [9,0] 也是有效答案?！痉治觥坑?words \textit{words}words 的長度為 m mm，words \textit{words}words 中每個單詞的長度為 n nn，s ss 的長度為 ls \textit{ls}ls。首先需要將 s ss 劃分為單詞組，每個單詞的大小均為 n nn （首尾除外）。這樣的劃分方法有 n nn 種，即先刪去前 i ii （i = 0 ～ n ? 1 i = 0 \sim n-1i=0～n?1）個字母后，將剩下的字母進行劃分，如果末尾有不到 n nn 個字母也刪去。對這 n nn 種劃分得到的單詞數(shù)組分別使用滑動窗口對 words \textit{words}words 進行類似于「字母異位詞」的搜尋。劃分成單詞組后，一個窗口包含 s ss 中前 m mm 個單詞，用一個哈希表 differ \textit{differ}differ 表示窗口中單詞頻次和 words \textit{words}words 中單詞頻次之差。初始化 differ \textit{differ}differ 時，出現(xiàn)在窗口中的單詞，每出現(xiàn)一次，相應(yīng)的值增加 1，出現(xiàn)在 words \textit{words}words 中的單詞，每出現(xiàn)一次，相應(yīng)的值減少 1。然后將窗口右移，右側(cè)會加入一個單詞，左側(cè)會移出一個單詞，并對 differ \textit{differ}differ 做相應(yīng)的更新。窗口移動時，若出現(xiàn) differ \textit{differ}differ 中值不為 0 的鍵的數(shù)量為 0，則表示這個窗口中的單詞頻次和 words \textit{words}words 中單詞頻次相同，窗口的左端點是一個待求的起始位置。劃分的方法有 n nn 種，做 n nn 次滑動窗口后，即可找到所有的起始位置。 vector findSubstring(string s, vector& words) { vector ans; int m = words.size(); int n = words[0].size(); int ls = s.size(); //注意添加&& i + m * n 長度限制 for(int i = 0; i < n && i + m * n <= ls; ++i){ unordered_map<string, int> mp; //現(xiàn)將 s 中前 m 個單詞作為初始化窗口 for(int j = 0; j < m; ++j){ string str = s.substr(i + j * n, n);//注意添加起始位置，i + mp[str]++; } for(string &str : words){ if(–mp[str] == 0){ mp.erase(str); } } //向后邊滑動窗口 for(int l = i; l + m * n <= ls; l += n){ if(l != i){ string str = s.substr(l - n, n); if(–mp[str] == 0){ mp.erase(str); } str = s.substr(l + (m - 1) * n, n); if(++mp[str] == 0){ // == 0 mp.erase(str); } } if(mp.empty()){ ans.emplace_back(l); } } } return ans; }12345678910111213141516171819202122232425262728293031323334353637前綴和/積與后綴和/積前綴和/積與后綴和/積不是什么數(shù)據(jù)結(jié)構(gòu)，而是一種常用的技巧。常用于查詢連續(xù)區(qū)間和是否為k，以及區(qū)間值運算等問題。前綴和經(jīng)常和哈希表結(jié)合，這樣可以將查詢的操作提升到O(1), 但是使用前綴和會有一個問題，當我們的更新次數(shù)過多時，尤其是需要更新的元素比較靠前時，每一次更新的代價都會為O(n)，從而沒有達到優(yōu)化的效果。前綴和適用于元素不變動的數(shù)組！前綴和非常經(jīng)典的一道好題：560. 和為 K 的子數(shù)組給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，請你統(tǒng)計并返回 該數(shù)組中和為 k 的子數(shù)組的個數(shù) 。示例 1：輸入：nums = [1,1,1], k = 2輸出：2示例 2：輸入：nums = [1,2,3], k = 3輸出：2【分析】前綴和 + 哈希表優(yōu)化定義 pre [ i ] \textit{pre}[i]pre[i] 為 [ 0… i ] [0…i][0…i] 里所有數(shù)的和，我們需要統(tǒng)計符合條件的下標 j jj 的個數(shù)，其中 0 ≤ j ≤ i 0\leq j\leq i0≤j≤i 且 [ j . . i ] [j…i][j…i] 這個子數(shù)組的和恰好為 k kk ?？紤]以 i ii 結(jié)尾的和為 k kk 的連續(xù)子數(shù)組個數(shù)時只要統(tǒng)計有多少個前綴和為 pre [ i ] ? k \textit{pre}[i]-kpre[i]?k 的 pre [ j ] \textit{pre}[j]pre[j] 即可。我們建立哈希表 mp \textit{mp}mp，以和為鍵，出現(xiàn)次數(shù)為對應(yīng)的值，記錄 pre [ i ] \textit{pre}[i]pre[i] 出現(xiàn)的次數(shù)，從左往右邊更新 mp \textit{mp}mp 邊計算答案，那么以 i ii 結(jié)尾的答案 mp [ pre [ i ] ? k ] \textit{mp}[\textit{pre}[i]-k]mp[pre[i]?k] 即可在 O ( 1 ) O(1)O(1) 時間內(nèi)得到。最后的答案即為所有下標結(jié)尾的和為 k kk 的子數(shù)組個數(shù)之和。需要注意的是，從左往右邊更新邊計算的時候已經(jīng)保證了mp [ pre [ i ] ? k ] \textit{mp}[\textit{pre}[i]-k]mp[pre[i]?k] 里記錄的 pre [ j ] \textit{pre}[j]pre[j] 的下標范圍是 0 ≤ j ≤ i 0\leq j\leq i0≤j≤i 。同時，由于pre [ i ] \textit{pre}[i]pre[i] 的計算只與前一項的答案有關(guān)，因此我們可以不用建立 pre \textit{pre}pre 數(shù)組，直接用 pre \textit{pre}pre 變量來記錄 p r e [ i ? 1 ] pre[i-1]pre[i?1] 的答案即可。 int subarraySum(vector& nums, int k) { unordered_map<int, int> mp; mp[0] = 1; int pre = 0, ans = 0; for(int &a:nums){ pre += a; ans += mp[pre - k]; //if (mp.find(pre - k) != mp.end()) mp[pre]++; } return ans; }1234567891011前綴積與后綴積的經(jīng)典例題：劍指 Offer 66. 構(gòu)建乘積數(shù)組給定一個數(shù)組 A[0,1,…,n-1]，請構(gòu)建一個數(shù)組 B[0,1,…,n-1]，其中 B[i] 的值是數(shù)組 A 中除了下標 i 以外的元素的積, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。示例:輸入: [1,2,3,4,5]輸出: [120,60,40,30,24]【分析】我們不必將所有數(shù)字的乘積除以給定索引處的數(shù)字得到相應(yīng)的答案，而是利用索引左側(cè)所有數(shù)字的乘積和右側(cè)所有數(shù)字的乘積（即前綴與后綴）相乘得到答案。對于給定索引 i ii，我們將使用它左邊所有數(shù)字的乘積乘以右邊所有數(shù)字的乘積。由于輸出數(shù)組不算在空間復(fù)雜度內(nèi)，所以可以先利用輸出數(shù)組作為前綴和數(shù)組，然后再在輸出數(shù)組的基礎(chǔ)上×后綴和（用一個變量表示即可），從而大大節(jié)省空間。算法1）初始化 ans 數(shù)組，對于給定索引 i，a n s [ i ] ans[i]ans[i] 代表的是 i 左側(cè)所有數(shù)字的乘積。2）不用構(gòu)造后綴和數(shù)組，而是用一個變量 r rr 表示索引 i 右側(cè)數(shù)字的乘積。通過遍歷來不斷更新右側(cè)元素的乘積 r 。更新數(shù)組 a n s [ i ] = a n s [ i ] ? r ans[i]=ans[i]rans[i]=ans[i]?r ，然后 r rr 更新為 r = r ? a [ i ] r=ra[i]r=r?a[i]。 vector constructArr(vector& a) { int n = a.size(); vector ans(n); if(a.empty()) return ans; // ans[i] 表示索引 i 左側(cè)所有元素的乘積 // 因為索引為 ‘0’ 的元素左側(cè)沒有元素， 所以 ans[0] = 1 ans[0] = 1; for(int i = 1; i < n; ++i){ ans[i] = ans[i - 1] * a[i - 1]; } // r 為右側(cè)所有元素的乘積 // 剛開始右邊沒有元素，所以 r = 1 int r = 1; for(int i = n - 1; i >= 0; --i){ // 對于索引 i，左邊的乘積為 ans[i]，右邊的乘積為 r ans[i] = r; // r 需要包含右邊所有的乘積，所以計算下一個結(jié)果時需要將當前值乘到 r 上 r = a[i]; } return ans; }123456789101112131415161718192021差分數(shù)組差分數(shù)組又叫插旗法，利用差分前綴和來求解公交車上下車和插旗問題等區(qū)間更新、區(qū)間重疊（活動安排）問題。差分數(shù)組是把原數(shù)組中后一個元素減前一個元素的差構(gòu)成一個新的數(shù)組，作為輔助數(shù)組使用。通常用map 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，如下圖所示：差分數(shù)組有什么用？diff[0] = nums[0];diff[1] = nums[1] - nums[0];diff[2] = nums[2] - nums[1];…nums[0] = diff[0];nums[1] = diff[1] + nums[0] = diff[0] + diff[1];nums[2] = nums[1] + diff[2] = diff[0] + diff[1] + diff[2];…nums[n] = diff[0] + diff[1] +diff[2] +…+ diff[n]由上可知:根據(jù)差分數(shù)組各項的前綴和，即可還原出原數(shù)組的各值，差分數(shù)組常用于對區(qū)間內(nèi)元素值的統(tǒng)一修改。 假設(shè)我們頻繁得對原數(shù)組進行范圍更新，則只需要更新差分數(shù)組端點值即可。應(yīng)用舉例1：假如把 nums 數(shù)組中 [0,3] 范圍到元素值都加 2：常規(guī)方法：for( int i =0;i < 4;++i){ nums[i] += 2;}1234差分數(shù)組：map<int, int> diff;diff[0] += 2;// 0 往后到值全部加 2diff[4] -= 2;// 4 往后到值全部減 2123應(yīng)用舉例2：在區(qū)間 [10, 15) [12, 18) 內(nèi)進行插旗，判斷插旗區(qū)間是否有重疊。插旗子 計數(shù)：對于每個區(qū)間[start,end)，在 start 計數(shù)diff[start] 加 1，表示從start 開始插旗的數(shù)目加 1；從 end 計數(shù)diff[end] 減 1，表示從 end 開始插旗的數(shù)目減 1。若差分數(shù)組前綴和 >1 即表示到當前位置為止的插旗區(qū)有重疊。區(qū)間原數(shù)組nums 10 12 15 18差分數(shù)組diff 1 1 -1 -1【分析】建立差分數(shù)組diff，nums數(shù)組中的每個區(qū)間的start對應(yīng)的差分數(shù)組計數(shù) ++， end 對應(yīng)的差分數(shù)組計數(shù) – ，注意每個區(qū)間的start 和 end 是分別作為獨立key 存儲到查分數(shù)組中的，對應(yīng)的value分別為++和–之后的值 ，而不是start 對應(yīng) key，end 對應(yīng)value這樣存儲。所有區(qū)間的 start 和 end 存儲到 map 中后，一起按照key從大到小的順序排序//nums = {{10, 15}, {12, 18}}//建立差分數(shù)組diff，每個區(qū)間的start對應(yīng)的差分數(shù)組計數(shù) ++， end 對應(yīng)的差分數(shù)組計數(shù) --//注意每個區(qū)間的start 和 end 是分別作為獨立key 存儲到查分數(shù)組中的，對應(yīng)的value分別為++和–之后的值//而不是start 對應(yīng) key，end 對應(yīng)value這樣存儲。//所有區(qū)間的 start 和 end 存儲到 map 中后，一起按照key從大到小的順序排序map<int, int> diff;for(auto v:nums){ diff[v[0]] ++; diff[v[1]] --;}//遍歷差分數(shù)組，用cnt進行插旗計數(shù)，大于1則說明區(qū)間重疊int cnt = 0;for(auto w:diff){ cnt += w.second; if(cnt > 1){ cout <<“插旗區(qū)間出現(xiàn)重疊” <<endl; break; }} 12345678910111213141516171819如果 兩個Interval 不相交，則 連續(xù)兩個 插旗計數(shù)的 和 必然等于零，一個+1，一個-1如果 兩個 Interval 相交，則 連續(xù)兩個插旗計數(shù) 的和 必然大于0，一個+1，一個+1732. 我的日程安排表 III當 k 個日程安排有一些時間上的交叉時（例如 k 個日程安排都在同一時間內(nèi)），就會產(chǎn)生 k 次預(yù)訂。給你一些日程安排 [start, end) ，請你在每個日程安排添加后，返回一個整數(shù) k ，表示所有先前日程安排會產(chǎn)生的最大 k 次預(yù)訂。實現(xiàn)一個 MyCalendarThree 類來存放你的日程安排，你可以一直添加新的日程安排。MyCalendarThree() 初始化對象。int book(int start, int end) 返回一個整數(shù) k ，表示日歷中存在的 k 次預(yù)訂的最大值。示例：輸入：[“MyCalendarThree”, “book”, “book”, “book”, “book”, “book”, “book”][[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]輸出：[null, 1, 1, 2, 3, 3, 3]解釋：MyCalendarThree myCalendarThree = new MyCalendarThree();myCalendarThree.book(10, 20); // 返回 1 ，第一個日程安排可以預(yù)訂并且不存在相交，所以最大 k 次預(yù)訂是1 次預(yù)訂。myCalendarThree.book(50, 60); // 返回 1 ，第二個日程安排可以預(yù)訂并且不存在相交，所以最大 k 次預(yù)訂是 1 次預(yù)訂。myCalendarThree.book(10, 40); // 返回 2 ，第三個日程安排 [10, 40)與第一個日程安排相交，所以最大 k 次預(yù)訂是 2 次預(yù)訂。 myCalendarThree.book(5, 15); // 返回 3，剩下的日程安排的最大 k 次預(yù)訂是 3 次預(yù)訂。myCalendarThree.book(5, 10); // 返回 3myCalendarThree.book(25, 55); // 返回 3題目翻譯：有一個數(shù)組初始值全部為 0 ，每次調(diào)用 book 方法都把 [start,end) 范圍內(nèi)的所有元素加 1，并返回當前數(shù)組中的最大值?！窘獯稹恐苯訕?gòu)建差分數(shù)組，更改區(qū)間值后再用前綴和還原出原數(shù)組即可。利用差分數(shù)組的思想，每當我們預(yù)定一個新的日程安排[start,end)，在 start 計數(shù)diff[start] 加 1，表示從start 預(yù)定的數(shù)目加 1；從 end 計數(shù)diff[end] 減 1，表示從 end 開始預(yù)定的數(shù)目減 1。從起點開始的計數(shù)累加值（前綴和）即為當前位置原數(shù)組的值（也就是該區(qū)間日程的安排次數(shù)）【注意點】book傳入的區(qū)間是左閉右開 所以[5,10) 跟 [10,…) 不會有 overlap 交叉map 自帶按key值的遞增排序.代碼class MyCalendarThree {public: MyCalendarThree() {} int book(int start, int end) { diff[start]++;// start 開始的值都加 1 diff[end]–;// end 開始的值都減 1 int res = 0; int cur = 0; for( auto & kv : diff ) { cur += kv.second;//前綴和還原原數(shù)組值 res = max(res,cur); } return res; }private: map<int,int> diff;//差分數(shù)組};123456789101112131415161718731. 我的日程安排表 II實現(xiàn)一個 MyCalendar 類來存放你的日程安排。如果要添加的時間內(nèi)不會導(dǎo)致三重預(yù)訂時，則可以存儲這個新的日程安排。MyCalendar 有一個 book(int start, int end)方法。它意味著在 start 到 end 時間內(nèi)增加一個日程安排，注意，這里的時間是半開區(qū)間，即 [start, end), 實數(shù) x 的范圍為， start <= x < end。當三個日程安排有一些時間上的交叉時（例如三個日程安排都在同一時間內(nèi)），就會產(chǎn)生三重預(yù)訂。每次調(diào)用 MyCalendar.book方法時，如果可以將日程安排成功添加到日歷中而不會導(dǎo)致三重預(yù)訂，返回 true。否則，返回 false 并且不要將該日程安排添加到日歷中。請按照以下步驟調(diào)用MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)示例：MyCalendar();MyCalendar.book(10, 20); // returns trueMyCalendar.book(50, 60); // returns trueMyCalendar.book(10, 40); // returns trueMyCalendar.book(5, 15); // returns falseMyCalendar.book(5, 10); // returns trueMyCalendar.book(25, 55); //returns true解釋：前兩個日程安排可以添加至日歷中。第三個日程安排會導(dǎo)致雙重預(yù)訂，但可以添加至日歷中。第四個日程安排活動（5,15）不能添加至日歷中，因為它會導(dǎo)致三重預(yù)訂。第五個日程安排（5,10）可以添加至日歷中，因為它未使用已經(jīng)雙重預(yù)訂的時間10。第六個日程安排（25,55）可以添加至日歷中，因為時間[25,40] 將和第三個日程安排雙重預(yù)訂； 時間 [40,50] 將單獨預(yù)訂，時間 [50,55）將和第二個日程安排雙重預(yù)訂。class MyCalendarTwo { map <int, int> differ;public: MyCalendarTwo() { } bool book(int start, int end) { differ[start]++; differ[end]–; int cur = 0; for(auto mp : differ){ if(mp.first == end){ break; } cur += mp.second; if(mp.first >= start){ if(cur >= 3){//注意：當三重訂單時需要刪除當前日程安排，否則將因為誤添加訂單，導(dǎo)致后面的訂單數(shù)計算有誤 differ[start]–; differ[end]++; return false; } } } return true; }};1234567891011121314151617181920212223242526272829補充題：729. 我的日程安排表 I實現(xiàn)一個 MyCalendar 類來存放你的日程安排。如果要添加的日程安排不會造成 重復(fù)預(yù)訂 ，則可以存儲這個新的日程安排。當兩個日程安排有一些時間上的交叉時（例如兩個日程安排都在同一時間內(nèi)），就會產(chǎn)生 重復(fù)預(yù)訂 。日程可以用一對整數(shù) start 和 end 表示，這里的時間是半開區(qū)間，即 [start, end), 實數(shù) x 的范圍為， start <= x < end 。實現(xiàn) MyCalendar 類：MyCalendar() 初始化日歷對象。boolean book(int start, int end) 如果可以將日程安排成功添加到日歷中而不會導(dǎo)致重復(fù)預(yù)訂，返回 true 。否則，返回 false 并且不要將該日程安排添加到日歷中。示例：輸入：[“MyCalendar”, “book”, “book”, “book”][[], [10, 20], [15, 25], [20, 30]]輸出：[null, true, false, true]解釋：MyCalendar myCalendar = new MyCalendar();myCalendar.book(10, 20); // return TruemyCalendar.book(15, 25); // return False，這個日程安排不能添加到日歷中，因為時間 15 已經(jīng)被另一個日程安排預(yù)訂了。myCalendar.book(20, 30); // return True ，這個日程安排可以添加到日歷中，因為第一個日程安排預(yù)訂的每個時間都小于 20 ，且不包含時間 20 ?！痉治觥慷植檎野磿r間順序維護日程安排，用 Set數(shù)據(jù)結(jié)構(gòu)來保持元素排序和支持快速插入。class MyCalendar { //按時間順序維護日程安排，則可以通過二分查找日程安排的情況來檢查新日程安排是否可以預(yù)訂 //需要一個數(shù)據(jù)結(jié)構(gòu)能夠保持元素排序和支持快速插入，可以用 Set 來構(gòu)建 set<pair<int, int>> calendar;public: MyCalendar() {} bool book(int start, int end) { //每次查找起點大于等于 end 的第一個區(qū)間 //對于集合set而言沒有下面這種用法 // auto it = lower_bound(calendar.begin(), calendar.end(), {end, 0}); //集合set需要這樣調(diào)用二分查找函數(shù) auto it = calendar.lower_bound({end, 0}); //同時緊挨著這個第一個區(qū)間的前一個區(qū)間的后端（注意不是前端）需要≤start if(it == calendar.begin() || (–it)->second <= start){ calendar.insert({start, end}); return true; } return false; }};123456789101112131415161718192021線段樹除了查分數(shù)組之外，另一種維護區(qū)間更新的數(shù)據(jù)結(jié)構(gòu)就是線段樹，線段樹除了可以快速的更新區(qū)間，還可以快速的查詢區(qū)間最值。由于普通的線段樹需要開4n的空間，所以為了讓數(shù)據(jù)離散化可以選擇動態(tài)開點。并且根節(jié)點的值就是所有區(qū)間的最大值，通常來說，時間提升了不少但整體空間復(fù)雜度提升。線段樹最經(jīng)典的應(yīng)該是307.區(qū)域和檢索。就是給你一個數(shù)組，會有簡單的更新操作以及查詢區(qū)域和的操作。查詢操作指的是給你一個區(qū)間[L,R], 返回該區(qū)間[L,R]內(nèi)所有元素的和。更新操作指的是，給你一個下標索引和一個值，將數(shù)組中該索引值對于的元素值改為新的給定值。線段樹（處理區(qū)域和查詢問題）：對于查詢區(qū)間和，我們?nèi)菀紫氲降囊粋€點就是使用前綴和，這樣我們就可以將查詢的操作提升到O(1), 但是使用前綴和會有一個問題，當我們的更新次數(shù)過多時，尤其是需要更新的元素比較靠前時，每一次更新的代價都會為O(n)，從而沒有達到優(yōu)化的效果。但是對于元素不變動的數(shù)組前綴和還是有很不錯的優(yōu)勢！線段樹將此類問題的查詢以及更新的時間復(fù)雜度都變成了O(logn)。當進行多次查詢與更新時，線段樹一定比前綴和更具優(yōu)勢。線段樹的結(jié)構(gòu)有點像堆，首先需要明確的是，我們用數(shù)組來表示樹的結(jié)構(gòu)，對于根樹的根節(jié)點，它會在index=1的位置上(其實此處0也行，不過大家普遍用1,區(qū)別就是計算子節(jié)點的方式不同)，然后對于其節(jié)點的左右子節(jié)點的下標分別為 2×index 與 2×index+1。然后其子節(jié)點也是這樣的規(guī)律。查詢: 我們會根據(jù)區(qū)間從根節(jié)點向樹的兩邊遞歸查尋。假設(shè)我們現(xiàn)在要查找此樹的[2,4]的區(qū)間和，即[50,50,1]的和, 那么這個過程是什么樣的呢？更新：假設(shè)我們要將其數(shù)組中的1更新為2，結(jié)構(gòu)會發(fā)生什么變化？而有那些節(jié)點會做出改變呢？到此我們已經(jīng)基本了解了線段樹了，我們發(fā)現(xiàn)線段樹讓更新與查詢的時間復(fù)雜度都變成了O(logn), 下面我們來代碼層面的學(xué)習(xí)一下線段樹。建樹跑完以上代碼后，我們的線段樹數(shù)組如下: （可以發(fā)現(xiàn)根節(jié)點在索引為1的位置的確為284，是所有元素的和，讀者可以根據(jù)樹的結(jié)構(gòu)，以及從開頭介紹的左右子節(jié)點的計算方式一一檢查是否正確檢索檢索需要討論以下情況：情況一：情況二：情況二則是當前區(qū)間被我們的檢索區(qū)間包圍，即藍色區(qū)間在綠色區(qū)間里面時，因此不必繼續(xù)往下遞歸，可以直接返回當前節(jié)點值。這里比較容易想，讀者可參考之前的線段樹查詢。思考一下，每一個節(jié)點表示的都是一個區(qū)間內(nèi)所有元素的和，那么當整個當前區(qū)間都被我們的檢索區(qū)間包圍了，證明我們需要所有的元素，因此不必繼續(xù)往下遞歸查詢，可以返回其節(jié)點值。譬如之前例子中的區(qū)間[3,4]，代碼輸出中依然可以觀察到這一點。代碼如下:示例查詢區(qū)間[2,4]的區(qū)域和結(jié)果如下: 50 + 50 + 1 = 101.為了可視化，我在其query方法中加入了幾行輸出。我們可以發(fā)現(xiàn)當遞歸到區(qū)間[3,4]時其實已經(jīng)停止繼續(xù)遞歸下去了，這正是我們想要的結(jié)果。更新更新與建樹很像，當其遞歸到出口時就說明我們已經(jīng)找到了要更新元素的節(jié)點。要注意更新完元素后，其包含此元素的區(qū)間節(jié)點都需要更新，代碼中已加注釋。我們做一次更新，將數(shù)組從[93,90,50,50,1]改到[93,90,50,50,2]，然后在做一次查詢看結(jié)果是否正確:題目練習(xí)：732. 我的日程安排表 III當 k 個日程安排有一些時間上的交叉時（例如 k 個日程安排都在同一時間內(nèi)），就會產(chǎn)生 k 次預(yù)訂。給你一些日程安排 [start, end) ，請你在每個日程安排添加后，返回一個整數(shù) k ，表示所有先前日程安排會產(chǎn)生的最大 k 次預(yù)訂。【問題解讀】首先我們來將問題轉(zhuǎn)化一下，讓題意更加明顯，其實本題的本質(zhì)就是給你一個區(qū)間，然后讓你將其[start, end)內(nèi)所有的元素值加上1，在進行了每一次的book更新的操作后，返回[0, 1 e 9 1e91e9]這個區(qū)間內(nèi)的最大元素值是多少。本題的解法本質(zhì)上其實也是運用了線段樹的思想，但是從檢查區(qū)域和，變?yōu)榱藱z索線段樹中葉子節(jié)點的最大值是多少。我們很容易的想到，對于其一段區(qū)間我們需要book時，我們可以將其區(qū)間內(nèi)的所有元素都加上1。顯而易見的是，我們無法真的去建樹，以及真的去更新其元素值。對于第一個問題，由于此題的數(shù)據(jù)問題，我們可能造成內(nèi)存溢出。因此我們用哈希表來表示我們的線段樹，這樣可以省去許多內(nèi)存空間。對于其第二個問題，不需要真的去手動更新每個節(jié)點值。我們選擇的是官解中的懶標記，及如果當前節(jié)點區(qū)間的被索引的區(qū)間覆蓋時，我們則將表示此區(qū)間的節(jié)點值加1，表示此區(qū)間內(nèi)的所有元素值都加了一位，這里很重要，讀者需要多讀幾遍。 個人覺得懶標記最難理解的地方就在這里，詳細可看思路步驟中的第二點解讀。【思路步驟】1.需要兩個哈希表，一個用于線段樹，一個用于區(qū)間的懶標記使用。注意此時的線段樹的節(jié)點擁有的是該區(qū)間內(nèi)的所有元素中的最大值。（不要被上述區(qū)間和的例子干擾，注意本題問的是什么！區(qū)間和提供的是思路！)2.對于一個區(qū)間的更新，我們左右遞歸，下面分類討論：1）當該區(qū)間不在檢索區(qū)間內(nèi)時，則start > r || end < l，不做更新，直接返回。2）當該區(qū)間被檢索區(qū)間覆蓋時，我們無需手動去更新該區(qū)間內(nèi)所有元素值，只需要標記一下該區(qū)間內(nèi)的所有元素都被加上了一位即可。顯而易見，無論當前節(jié)點區(qū)間的最大值為多少，當該區(qū)間的所有元素值都加一時，其擁有的最大值自然也需要加一位。3）當該區(qū)間內(nèi)有元素不在其檢索區(qū)間時，遞歸左右兩邊去更新我們的線段樹。3.返回根節(jié)點的最大值，即所有元素中的最大值。class MyCalendarThree {private: unordered_map<int, int> tree; unordered_map<int, int> lazy;public: MyCalendarThree() { } void update(int start, int end, int l, int r, int node) { if(start > r || end < l) { return; } else if(start <= l && r <= end) { // 當前區(qū)間被檢索區(qū)間覆蓋, 因此區(qū)間內(nèi)所有元素都加一 // 自然而然，無論當前節(jié)點區(qū)間的最大值為多少，當該區(qū)間的所有 // 元素值都加一時，其擁有的最大值自然也需要加一位 ++tree[node]; ++lazy[node]; } else { int left_node = node2, right_node = node2 + 1; int mid = (l+r) >> 1; update(start, end, l, mid, left_node); update(start, end, mid+1, r, right_node); tree[node] = lazy[node] + max(tree[left_node], tree[right_node]); } } int book(int start, int end) { update(start, end-1, 0, 1e9, 1); return tree[1]; }};123456789101112131415161718192021222324252627282930313233復(fù)雜度分析時間復(fù)雜度：O ( n log ? C ) O(n \log C)O(nlogC)，其中 n 為日程安排的數(shù)量。由于使用了線段樹查詢，線段樹的最大深度為 log ? C \log ClogC, 每次最多會查詢 log ? C \log ClogC個節(jié)點，每次求最大的預(yù)定需的時間復(fù)雜度為 O ( log ? C + log ? C ) O(\log C + \log C)O(logC+logC)，因此時間復(fù)雜度為 O ( n log ? C ) O(n \log C)O(nlogC)，在此 C 取固定值即為 1 0 9 10^910 9 ?？臻g復(fù)雜度：O ( n log ? C ) O(n \log C)O(nlogC)，其中 n 為日程安排的數(shù)量。由于該解法采用的為動態(tài)線段樹，線段樹的最大深度為 log ? C \log ClogC，每次預(yù)定最多會在線段樹上增加log ? C \log ClogC個節(jié)點，因此空間復(fù)雜度為 O ( n log ? C ) O(n \log C)O(nlogC)，在此 C 取固定值即為 1 0 9 10^910 9 。前綴樹/字典樹（Trie）前綴樹（Trie Tree），Trie [tra?] 讀音和 try 相同，前綴樹也叫字典樹或單詞查找樹。Trie（發(fā)音類似 “try”）或者說 前綴樹 是一種樹形數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲和檢索字符串數(shù)據(jù)集中的鍵。這一數(shù)據(jù)結(jié)構(gòu)有相當多的應(yīng)用情景，例如自動補完和拼寫檢查。「前綴樹」比較常用的應(yīng)用場景：給定一個字符串集合構(gòu)建一棵前綴樹，然后給一個字符串，判斷前綴樹中是否存在該字符串或者該字符串的前綴。Trie 是一種非典型的多叉樹模型，多叉好理解，即每個結(jié)點的分支數(shù)量可能為多個。為什么說非典型呢？因為它和一般的多叉樹不一樣，尤其在結(jié)點的數(shù)據(jù)結(jié)構(gòu)設(shè)計上，比如一般的多叉樹的結(jié)點是這樣的：struct TreeNode { VALUETYPE value; //結(jié)點值 TreeNode children[NUM]; //指向孩子結(jié)點};1234而 Trie 的結(jié)點是這樣的(假設(shè)只包含’a’~'z’中的字符)，可以理解為26叉樹（有的分支為空，可以忽略）：struct TrieNode { bool isEnd; //該結(jié)點是否是一個串的結(jié)束 vector<TrieNode> children = vector<TrieNode>(26);//字母映射表 //TrieNode children[26]; //或者這樣寫};12345children 中保存了對當前結(jié)點而言下一個可能出現(xiàn)的所有字符的鏈接，因此我們可以通過一個父結(jié)點來預(yù)知它所有子結(jié)點的值：for (int i = 0; i < 26; i++) { char ch = ‘a(chǎn)’ + i; if (parentNode->children[i] == nullptr) { 說明父結(jié)點的后一個字母不可為 ch } else { 說明父結(jié)點的后一個字母可以是 ch }}12345678來看個例子，想象以下，包含三個單詞 “sea”,“sells”,“she” 的 Trie 會長啥樣呢？它的真實情況是這樣的：Trie 中一般都含有大量的空鏈接，因此在繪制一棵單詞查找樹時一般會忽略空鏈接，同時為了方便理解我們可以畫成這樣：由于都是小寫字母，所以對于每個節(jié)點，均有 26 個孩子節(jié)點，上圖中沒有畫出來，省略了而已…，但是要記住：每個節(jié)點均有 26 個孩子節(jié)點還有一個點要明確：節(jié)點僅僅表示從根節(jié)點到本節(jié)點的路徑構(gòu)成的字符串是否有效而已對于上圖中紅色的節(jié)點，均為有效節(jié)點，即：從根節(jié)點到紅色節(jié)點的路徑構(gòu)成的字符串均在集合中接下來我們一起來實現(xiàn)對 Trie 的一些常用操作方法：1.定義類 Trieclass Trie {private: bool isEnd; vector<Trie> children = vector<Trie>(26);//字母映射表public: //方法將在下文實現(xiàn)…};12345672.插入描述：向 Trie 中插入一個單詞 word實現(xiàn)：這個操作和構(gòu)建鏈表很像。首先從根結(jié)點的子結(jié)點開始與 word 第一個字符進行匹配，一直匹配到前綴鏈上沒有對應(yīng)的字符，這時開始不斷開辟新的結(jié)點，直到插入完 word 的最后一個字符，同時還要將最后一個結(jié)點isEnd = true;，表示它是一個單詞的末尾。void insert(string word) { Trie* node = this; for (char c : word) { if (node->children[c-‘a(chǎn)’] == nullptr) { node->children[c-‘a(chǎn)’] = new Trie(); } node = node->children[c-‘a(chǎn)’]; } node->isEnd = true;}123456789103.查找描述：查找 Trie 中是否存在單詞 word實現(xiàn)：從根結(jié)點的子結(jié)點開始，一直向下匹配即可，如果出現(xiàn)結(jié)點值為空就返回 false，如果匹配到了最后一個字符，那我們只需判斷 node->isEnd 即可。bool search(string word) { Trie* node = this; for (char c : word) { node = node->children[c - ‘a(chǎn)’]; if (node == nullptr) { return false; } } return node->isEnd;}123456789104.前綴匹配描述：判斷 Trie 中是或有以 prefix 為前綴的單詞實現(xiàn)：和 search 操作類似，只是不需要判斷最后一個字符結(jié)點的isEnd，因為既然能匹配到最后一個字符，那后面一定有單詞是以它為前綴的。bool startsWith(string prefix) { Trie* node = this; for (char c : prefix) { node = node->children[c-‘a(chǎn)’]; if (node == nullptr) { return false; } } return true;}12345678910總結(jié)：通過以上介紹和代碼實現(xiàn)我們可以總結(jié)出 Trie 的幾點性質(zhì)：1.Trie 的形狀和單詞的插入或刪除順序無關(guān)，也就是說對于任意給定的一組單詞，Trie 的形狀都是唯一的。2.查找或插入一個長度為 L 的單詞，訪問 children 數(shù)組的次數(shù)最多為 L + 1 L+1L+1，和 Trie 中包含多少個單詞無關(guān)。3.Trie 的每個結(jié)點中都保留著一個字母表，這是很耗費空間的。如果 Trie 的高度為 n nn，字母表的大小為 m mm，最壞的情況是 Trie 中還不存在前綴相同的單詞，那空間復(fù)雜度就為 O ( m n ) O(m^n)O(m n )最后，關(guān)于 Trie 的應(yīng)用場景，希望你能記住 8 個字：一次建樹，多次查詢。(慢慢領(lǐng)悟叭~~)
——————————————

總結(jié)

以上是生活随笔為你收集整理的C++数据结构，三万字详解（强烈建议收藏）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。