深入理解數(shù)據(jù)結(jié)構(gòu)和算法
[導(dǎo)讀]hi，大家好，今天分享一些對數(shù)據(jù)結(jié)構(gòu)和算法精華總結(jié)，希望對大家的面試或者工作有一定的幫助；看完本文可以學(xué)到什么知道哪些數(shù)據(jù)結(jié)構(gòu)和算法在實際工作中最常用，最重要理解一些設(shè)計上注意事項（經(jīng)驗總結(jié)）掌握常用數(shù)據(jù)結(jié)構(gòu)和算法核心知識點數(shù)據(jù)結(jié)構(gòu)工作中或者開源項目中最常用數(shù)據(jù)結(jié)構(gòu)：數(shù)組/lis...
hi，大家好，今天分享一些對數(shù)據(jù)結(jié)構(gòu)和算法精華總結(jié)，希望對大家的面試或者工作有一定的幫助；看完本文可以學(xué)到什么
- 知道哪些數(shù)據(jù)結(jié)構(gòu)和算法在實際工作中最常用，最重要
- 理解一些設(shè)計上注意事項（經(jīng)驗總結(jié)）
- 掌握常用數(shù)據(jù)結(jié)構(gòu)和算法核心知識點
數(shù)據(jù)結(jié)構(gòu)
工作中或者開源項目中最常用數(shù)據(jù)結(jié)構(gòu)：數(shù)組/list hash treeO(n)結(jié)構(gòu)：list/棧/隊列O(1)結(jié)構(gòu)：數(shù)組/hash/位圖O(logn)樹形結(jié)構(gòu)：紅黑樹/B 樹/skip list
數(shù)組核心點：1 內(nèi)存空間大小固定，如果支持動態(tài)擴展，需要內(nèi)存遷移，有一定的性能代價，比如C STL的vector結(jié)構(gòu)；2 內(nèi)存連續(xù)，對CPU cache友好，如果內(nèi)存空間足夠，能用數(shù)組就最好用數(shù)組結(jié)構(gòu)；3 ?數(shù)組空間一般都是預(yù)分配的，不會頻繁申請和釋放，所以可以提供程序性能，這個做內(nèi)存池優(yōu)化的實現(xiàn)手段；
鏈表核心點：
- 可以動態(tài)項擴縮容，比較節(jié)約空間；
- 鏈表編程邊界case檢查：??
- 每個節(jié)點必須有個“指針“要么指向其他節(jié)點，要么為空，這樣才能把鏈表串起來，任何操作都必須保證鏈表完整性，不允許節(jié)點無故脫鏈，所以任何操作之前，都要思考會不會導(dǎo)致節(jié)點脫鏈，如果不下心脫鏈就會存在內(nèi)存泄漏風(fēng)險；
- 鏈表作為最基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，很多高級結(jié)構(gòu)：隊列，棧，hash，二叉樹，都是在鏈表基礎(chǔ)上演化而來；
編程技巧
- 頭結(jié)點解決什么問題？
- 鏈表最常規(guī)操作
{
? ? next->prev = prev;
? ? prev->next = next;
}再釋放刪除節(jié)點內(nèi)存；添加: ?遍歷鏈表找到要加入位置（或者節(jié)點），保存該節(jié)點的pre節(jié)點和next節(jié)點，然后把新接入插入到鏈表中：static inline void __list_add(struct list_head *new,
? ? struct list_head *prev,
? ? struct list_head *next)
{
? ? next->prev = new;
? ? new->next = next;
? ? new->prev = prev;
? ? prev->next = new;
}2 ?快慢指針，快慢指針一般都初始化指向鏈表的頭結(jié)點 head，前進時快指針 fast 在前，慢指針 slow 在后，巧妙解決一些鏈表中的問題。比如：判定鏈表中是否含有環(huán)，尋找鏈表的中點, 尋找距離尾部第K個節(jié)點等；3 dummy node，dummy node是鏈表問題中一個重要的技巧，中文翻譯叫“啞節(jié)點”，使用通常針對單鏈表沒有前向指針的問題，保證鏈表的 head不會在刪除操作中丟失，當(dāng)鏈表的 head 有可能變化（被修改或者被刪除）時，使用 dummy node 可以很好的簡化代碼，最終返回 dummy.next 即新的鏈表。4 通常鏈表有兩種實現(xiàn)方式，一種是抽象獨立型，一種是傳統(tǒng)耦合型；list作為常用數(shù)據(jù)結(jié)構(gòu)，寫代碼時候經(jīng)常會遇到，可以看一下傳統(tǒng)list設(shè)計和抽象list設(shè)計有什么不一樣。一般的雙向鏈表一般是如下的結(jié)構(gòu):
- 有個單獨的頭結(jié)點(head)
- 每個節(jié)點(node)除了包含必要的數(shù)據(jù)之外，還有2個指針(pre,next)
- pre指針指向前一個節(jié)點(node)，next指針指向后一個節(jié)點(node)
- 頭結(jié)點(head)的pre指針指向鏈表的最后一個節(jié)點
- 最后一個節(jié)點的next指針指向頭結(jié)點(head)
傳統(tǒng)list如下圖：傳統(tǒng)的鏈表不同node類型，需要重新定義結(jié)構(gòu)，不夠通用化，還需要為node實現(xiàn)脫鏈、入鏈操作等。我們需要抽象出一個“基類”來實現(xiàn)鏈表的功能，其他數(shù)據(jù)結(jié)構(gòu)只需要簡單的繼承這個鏈表類就可以了。抽象型list設(shè)計如下：
- 鏈表不是將用戶數(shù)據(jù)保存在鏈表節(jié)點中，而是將鏈表節(jié)點保存在用戶數(shù)據(jù)中
- 鏈表節(jié)點只有2個指針(prev和next)
- prev指針指向前一個節(jié)點的鏈表節(jié)點，next指針指向后一個節(jié)點(node)的鏈表節(jié)點
如下圖：
這樣設(shè)計的好處是鏈表的節(jié)點將獨立于用戶數(shù)據(jù)之外，便于把鏈表的操作獨立出來，和具體數(shù)據(jù)節(jié)點無關(guān)，這里可能有些人會問，數(shù)據(jù)節(jié)點怎么訪問呢？通過一個container_of的宏從鏈表節(jié)點找到數(shù)據(jù)節(jié)點起始地址：
找到數(shù)據(jù)節(jié)點起始地址后，通過數(shù)據(jù)節(jié)點定義就可以訪問數(shù)據(jù)。5 鏈表最核心技巧，就是理解指針操作（包括安全檢查-空指針判斷），不要被指針復(fù)雜的賦值操作搞暈，多敲代碼，找到經(jīng)典的鏈表練習(xí)題（28原則）不斷練習(xí)，比如：判斷鏈表是否有環(huán)，反轉(zhuǎn)鏈表，合并鏈表等，寫好每一題，再認(rèn)真總結(jié)，唯有熟才能生巧。
棧
核心點：
- 需要關(guān)注棧的深度大?。ㄈ萘浚?；
- 棧各個極端情況處理，比如空，滿，溢出等；
- 多線程下實現(xiàn)安全的棧操作；
- 堆棧很容易被攻擊(緩沖區(qū)溢出攻擊)，程序員必須特別注意避免這些實現(xiàn)的陷阱, 防止代碼產(chǎn)生安全漏洞；
3 ?編譯器使用，比如表達式解析，語法檢查等；
隊列核心點：
- 隊列核心作用：應(yīng)用耦合、異步處理、流量削鋒（緩沖）；
- 隊列各個極端情況處理，比如空，滿，溢出等；
- 隊列支持多線程并發(fā)操作，加鎖或者無鎖隊列實現(xiàn)；
- 隊列零拷貝優(yōu)化，比如隊列操作零拷貝（操作指針地址或者索引），IO零拷貝；
使用場景：1 各種消息隊列中間件，比如RabbitMQ、RocketMQ、ActiveMQ、Kafka、ZeroMQ、MetaMq等；
2 各種排隊（緩沖區(qū)）系統(tǒng)，操作系統(tǒng)任務(wù)FIFO調(diào)度隊列，數(shù)據(jù)包發(fā)送隊列，凡是需要滿足FIFO場景，都是可以用隊列實現(xiàn)；
Hash結(jié)構(gòu)：hash結(jié)構(gòu)核心點：
- Hash是以空間換時間結(jié)構(gòu)，需要評估好所有Hash頭結(jié)構(gòu)的內(nèi)存使用量；
- Hash桶選擇需要考慮到內(nèi)存和沖突鏈長度大?。ㄓ绊懖檎倚?；
- hash的優(yōu)化 --解決hash沖突3.1 內(nèi)存有限場景下，就需要優(yōu)化沖突鏈結(jié)構(gòu)（鏈表轉(zhuǎn)紅黑樹）；3.2 優(yōu)化hash函數(shù)，讓hash結(jié)果更均勻；3.3 可以考慮雙重hash（空間和時間，還有編碼復(fù)雜度的一種折中方案）?
- 需要考慮hash擴容4.1 在設(shè)計hash結(jié)構(gòu)的時候，需要考慮未來可用戶量增長后導(dǎo)致規(guī)格變大，這樣原先hash結(jié)構(gòu)已經(jīng)不合適，沖突鏈太長，導(dǎo)致查詢效率急速降低，所以再最初設(shè)計的時候，需要考慮到rehash設(shè)計（為什么不一次設(shè)置為最大，因為內(nèi)存不是無限的，需要考慮一定時間還可以提供很好的服務(wù)，不需要升級版本），當(dāng)hash沖突鏈太長后，進行rehash流程；4.2 rehash算法有很多，需要考慮幾點：a. 要不要保證hash一致性，擴容后，重hash還是不變，這個在負(fù)載均衡網(wǎng)關(guān)里面很重要，需要保證hash選擇RS后端服務(wù)節(jié)點不變，否則會到存量連接走到其他RS節(jié)點，讓服務(wù)變得不可用，甚至斷開（tcp需要建立會話，其他RS沒有這個會話）等。?所以這里可能會采用一致性hash算法，或者其他hash算法，保證相同client去相同RS。 b. 在rehash過程中，由于需要保證業(yè)務(wù)正常，需要保證在修改過程中，所以為了減少鎖影響，一般采用雙份內(nèi)存，逐步把原h(huán)ash數(shù)據(jù)遷移到新hash結(jié)構(gòu)（防止大規(guī)模rehash導(dǎo)致CPU性能瓶頸），當(dāng)存量遷移完后，可以快速加鎖切換hash結(jié)構(gòu)，這樣可以減少服務(wù)不可用時間；
使用場景：1 redis的dict結(jié)構(gòu)設(shè)計；2 簽名算法MD5算法；3 數(shù)據(jù)包校驗 CRC算法；4 負(fù)載均衡LB選擇后端服務(wù)器hash算法；5 布隆過濾器：布隆過濾器被廣泛用于黑名單過濾、垃圾郵件過濾、爬蟲判重系統(tǒng)以及緩存穿透問題。對于數(shù)量小，內(nèi)存足夠大的情況，我們可以直接用hashMap或者h(yuǎn)ashSet就可以滿足這個活動需求了。但是如果數(shù)據(jù)量非常大，比如5TB的硬盤上放滿了用戶的參與數(shù)據(jù)，需要一個算法對這些數(shù)據(jù)進行去重，取得活動的去重參與用戶數(shù)。這種時候，布隆過濾器就是一種比較好的解決方案了。
位圖（Bitmap）核心點：
- 即位（Bit）的集合，是一種數(shù)據(jù)結(jié)構(gòu)，可用于記錄大量的0-1狀態(tài)，在很多地方都會用到，優(yōu)勢是可以在一個非常高的空間利用率下保存大量0-1狀態(tài)。
- 本質(zhì)上是采用了bit位來表示元素狀態(tài)，從而在特定場景下能夠極大的節(jié)省存儲空間，非常適合對海量數(shù)據(jù)的查找，判重，刪除等問題的處理；
- 數(shù)據(jù)稀疏。又比如要存入(10,8887983,93452134)這三個數(shù)據(jù)，我們需要建立一個 99999999 長度的 BitMap ，但是實際上只存了3個數(shù)據(jù)，這時候就有很大的空間浪費，碰到這種問題的話，可以通過引入 Roaring BitMap 來解決，就是通過壓縮算法進行空間壓縮。
- 數(shù)據(jù)碰撞。比如將字符串映射到 BitMap 的時候會有碰撞的問題，那就可以考慮用 Bloom Filter 來解決，Bloom Filter 使用多個 Hash 函數(shù)來減少沖突的概率
使用場景：1 在Java里面一個int類型占4個字節(jié)，假如要對于10億個int數(shù)據(jù)進行處理呢？10億*4/1024/1024/1024=4個G左右，需要4個G的內(nèi)存。如果能夠采用bit儲,10_0000_0000Bit=1_2500_0000byte=122070KB=119MB, 那么在存儲空間方面可以大大節(jié)省。在Java里面，BitMap已經(jīng)有對應(yīng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類java.util.BitSet，BitSet的底層使用的是long類型的數(shù)組來存儲元素。2 redis bitmap；3 布隆過濾器；4 ?Linux內(nèi)核（如inode，磁盤塊）；
紅黑樹
核心點
在已經(jīng)有了AVL之類的BBST，為什么還需要引入紅黑樹？我們希望數(shù)據(jù)結(jié)構(gòu)具有關(guān)聯(lián)性，即相鄰版本之間，比如說第一次插入，和第二次插入時，樹的結(jié)構(gòu)不能發(fā)生太大變化，應(yīng)該可以經(jīng)過O（1）次數(shù)就可以變化完成。對于AVL樹來說，插入是滿足這個條件的，刪除卻不滿足這個條件。紅黑樹就滿足這一特性，插入和刪除操作后的拓?fù)渥兓粫^O(1)。
- 紅黑樹與AVL樹相似，但提供更快的實時有界最壞情況下的插入和刪除性能（分別達到最多兩輪和三輪以平衡樹），但速度稍慢（但仍為O（log n））查找時間；
- 紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔(dān)保。這不只是使它們在時間敏感的應(yīng)用，如實時應(yīng)用（real time application）中有價值，而且使它們有在提供最壞情況擔(dān)保的其他數(shù)據(jù)結(jié)構(gòu)中作為基礎(chǔ)模板的價值；例如，在計算幾何中使用的很多數(shù)據(jù)結(jié)構(gòu)都可以基于紅黑樹實現(xiàn)。
- 紅黑樹在函數(shù)式編程中也特別有用，在這里它們是最常用的持久數(shù)據(jù)結(jié)構(gòu)（persistent data structure）之一，它們用來構(gòu)造關(guān)聯(lián)數(shù)組和集合，每次插入、刪除之后它們能保持為以前的版本。除了的時間之外，紅黑樹的持久版本對每次插入或刪除需要的空間。
- 紅黑樹相對于AVL樹來說，犧牲了部分平衡性以換取插入/刪除操作時少量的旋轉(zhuǎn)操作，整體來說性能要優(yōu)于AVL樹。
- 維護紅黑樹的平衡需要考慮7種不同的情況:
- 紅黑樹為什么綜合性能好？
發(fā)展：我們將紅黑樹分成這么幾種類型：左傾紅黑樹、右傾紅黑樹、AA樹。左傾紅黑樹（LLRB，Left-Learning Red-Black Tree），一個節(jié)點如果有紅色子節(jié)點，那么，它的紅色子節(jié)點是向左傾斜的。右傾紅黑樹（RLRB，Right-Learning Red-Black Tree），也是一樣的道理，即紅色子節(jié)點向右傾斜。左傾紅黑樹（*LLRB**）是一種類型的自平衡二叉查找樹。它是紅黑樹的變體，并保證對操作相同漸近的復(fù)雜性，但被設(shè)計成更容易實現(xiàn)。AA樹是紅黑樹的一種變種，是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹，設(shè)計的目的是減少紅黑樹考慮的不同情況，區(qū)別于紅黑樹的是，AA樹的紅節(jié)點只能作為右葉子，從而大大簡化了維護2-3樹的模擬，因為AA樹有嚴(yán)格的條件(紅節(jié)點只能為右節(jié)點)，故只需考慮2種情形:使用場景：1 C 廣泛用在C 的STL中。如map和set都是用紅黑樹實現(xiàn)的；2 JavaJava的TreeMap實現(xiàn)；HashMap的底層實現(xiàn)，在JDK1.8中為了解決過度哈希沖突帶來的長鏈表，當(dāng)鏈表長度大于某個閾值會將鏈表轉(zhuǎn)為紅黑樹；3 Linux操作系統(tǒng)?????CFS進程調(diào)度算法中，vruntime利用紅黑樹來進行存儲，選擇最小vruntime節(jié)點調(diào)度。數(shù)據(jù)包CD / DVD驅(qū)動程序執(zhí)行相同的操作。高分辨率計時器代碼使用rbtree來組織未完成的計時器請求。ext3文件系統(tǒng)跟蹤紅黑樹中的目錄條目。虛擬內(nèi)存結(jié)構(gòu)管理（VMA）.。多路復(fù)用技術(shù)的Epoll的核心結(jié)構(gòu)也是紅黑樹 雙向鏈表。加密密鑰和網(wǎng)絡(luò)數(shù)據(jù)包均由紅黑樹跟蹤。4 Linux應(yīng)用程序nginx用紅黑樹管理timer等。5 實際工作中也會用到紅黑樹
1 我們做的是大流量網(wǎng)關(guān)，100G 流量，pps 實際是5000w pps 左右， 我們路由表項總共是5000w。2 當(dāng)時采用數(shù)據(jù)結(jié)構(gòu)是hash list，路由規(guī)模還會不斷增大，但不能無腦增加hash桶，這個會增加內(nèi)存，本身當(dāng)時網(wǎng)關(guān)內(nèi)存就不是很充裕，所以這里要把list換成紅黑樹。3 ?但之前l(fā)ist都是用RCU鎖（因為鏈表操作可以原子化（64位指針））實現(xiàn)多核并發(fā)訪問，但紅黑樹這種樹形結(jié)構(gòu)要實現(xiàn)無鎖多核并發(fā)一直是比較困難的點，每次變更可能會產(chǎn)生多次位移（旋轉(zhuǎn)）操作，多個操作比較困實現(xiàn)原子化。4 ?最終想到一個比較好方法是 雙份指針，用空間換時間，紅黑樹維護兩份指針（骨架），當(dāng)前使用的active指針，更新操作backup指針，等更新backup指針后，再原子交換根節(jié)點，這樣不妨礙其他核讀，然后再同步指針拓?fù)潢P(guān)系到備份指針。
跳表（skip list）核心點：
1 跳表本質(zhì)上是對鏈表的一種優(yōu)化，通過逐層跳步采樣的方式構(gòu)建索引，以加快查找速度。使用概率均衡的思路，確定新插入節(jié)點的層數(shù)，使其滿足集合分布，在保證相似的查找效率簡化了插入實現(xiàn)。2 skiplist的復(fù)雜度和紅黑樹一樣，而且實現(xiàn)起來更簡單；3 在并發(fā)環(huán)境下skiplist有另外一個優(yōu)勢，紅黑樹在插入和刪除的時候可能需要做一些rebalance的操作，這樣的操作可能會涉及到整個樹的其他部分，而skiplist的操作顯然更加局部性一些，鎖需要盯住的節(jié)點更少，因此在這樣的情況下性能好一些；使用場景：1 HBase MemStore 的數(shù)據(jù)結(jié)構(gòu)：HBase 屬于 LSM Tree 結(jié)構(gòu)的數(shù)據(jù)庫，LSM Tree 結(jié)構(gòu)的數(shù)據(jù)庫有個特點，實時寫入的數(shù)據(jù)先寫入到內(nèi)存，內(nèi)存達到閾值往磁盤 flush 的時候，會生成類似于 StoreFile 的有序文件，而跳表恰好就是天然有序的，所以在 flush 的時候效率很高。2 Google 開源的 key/value 存儲引擎 LevelDB 以及 Facebook 基于 LevelDB 優(yōu)化的 RocksDB 都是 LSM Tree 結(jié)構(gòu)的數(shù)據(jù)庫，他們內(nèi)部的 MemTable 都是使用了跳表這種數(shù)據(jù)結(jié)構(gòu)；3 ?redis的sorted set內(nèi)部實現(xiàn)；
B/B 樹（平衡多路查找樹）
核心點：1 Ｂ樹和Ｂ＋樹的出現(xiàn)是因為磁盤ＩＯ；眾所周知，ＩＯ操作的效率很低，那么，當(dāng)在大量數(shù)據(jù)存儲中，查詢時我們不能一下子將所有數(shù)據(jù)加載到內(nèi)存中，只能逐一加載磁盤頁，每個磁盤頁對應(yīng)樹的節(jié)點。造成大量磁盤ＩＯ操作（最壞情況下為樹的高度）。平衡二叉樹由于樹深度過大而造成磁盤IO讀寫過于頻繁，進而導(dǎo)致效率低下。所以，我們?yōu)榱藴p少磁盤ＩＯ的次數(shù)，就你必須降低樹的深度，將“瘦高”的樹變得“矮胖”。一個基本的想法就是：
- 每個節(jié)點存儲多個元素
- 摒棄二叉樹結(jié)構(gòu)，采用多叉樹
O(logN)這樣的對數(shù)級別上。2 B-Tree是為磁盤等外存儲設(shè)備設(shè)計的一種平衡查找樹。系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存時是以磁盤塊（block）為基本單位的，位于同一個磁盤塊中的數(shù)據(jù)會被一次性讀取出來，B Tree是在B-Tree基礎(chǔ)上 ? 的一種優(yōu)化，使其更適合實現(xiàn)外存儲索引結(jié)構(gòu)；3 B Tree 只有葉子結(jié)點存儲數(shù)據(jù)，所有非葉子結(jié)點（內(nèi)部結(jié)點）不存儲數(shù)據(jù)，只有指向子結(jié)點的指針。葉子結(jié)點均在同一層，且葉子結(jié)點之間類似于鏈表結(jié)構(gòu)，即有指針指向下一個葉子結(jié)點；4 由于B 樹在內(nèi)部節(jié)點上不包含數(shù)據(jù)信息，因此在內(nèi)存頁中能夠存放更多的key。數(shù)據(jù)存放的更加緊密，具有更好的空間局部性。因此訪問葉子節(jié)點上關(guān)聯(lián)的數(shù)據(jù)也具有更好的緩存命中率5 B 樹的葉子結(jié)點都是相鏈的，因此對整棵樹的便利只需要一次線性遍歷葉子結(jié)點即可。而且由于數(shù)據(jù)順序排列并且相連，所以便于區(qū)間查找和搜索。而B樹則需要進行每一層的遞歸遍歷，相鄰的元素可能在內(nèi)存中不相鄰，所以緩存命中性沒有B 樹好，B樹也有優(yōu)點，其優(yōu)點在于：由于B樹的每一個節(jié)點都包含key和value，因此經(jīng)常訪問的元素可能離根節(jié)點更近，因此訪問也更迅速。使用場景：MySQL InnoDB存儲引擎就是用B Tree實現(xiàn)：
- 每個級別的所有頁面都相互雙向鏈接，并且在每個頁面內(nèi)，記錄按升序單獨鏈接。非葉頁包含“指針”（包含子頁碼）而不是非關(guān)鍵行數(shù)據(jù)。
算法
一些的重要算法，很多算法在工作中都經(jīng)常使用；排序算法核心：
核心點:
- 穩(wěn)定性得好處：從一個鍵上排序，然后再從另一個鍵上排序，第一個鍵排序的結(jié)果可以為第二個鍵排序所用，多重key值排序；
- 大多數(shù)語言的標(biāo)準(zhǔn)庫排序算法是快速排序：
- 增量型排序（比如實時計算topN這種）采用是堆排序（最小堆或者最大堆）；
字符串匹配算法核心點：
- 盡可能利用一切可以利用信息，比如模式串本身信息，后綴信息，比較后的殘余信息等；
- 掌握正則表達式語法；
- 理解模式匹配：KMP、Boyer-Moore算法；
1 ?linux文本處理三劍客 grep ，awk， sed 等用了大量正則表達式算法。2 文本編輯器使用大量字符串匹配算法。
圖論核心點：
- 實際工作中網(wǎng)絡(luò)會用到部分圖算法，比如網(wǎng)絡(luò)拓?fù)渑判?，OSPF路由協(xié)議（最短路徑）；
- 如果你要參加ACM or OJ 這種比賽，可以學(xué)一些常用圖算法：最短路徑、最小生成樹、網(wǎng)絡(luò)流建模；
搜索(遍歷) 剪枝
核心點:
- 核心是減少解空間，窮舉 排除法；
- 核心是減少解空間，遞歸 判斷；
二分法核心點：
- 前置條件，需要有序；
- 全面考慮算法邊界點，實現(xiàn)細(xì)節(jié)，溢出等問題；
- 不能在線增量計算；
分治算法
核心點:
- 一是自頂向下分解問題，二是自底向上抽象合并；
- 將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之；?
使用場景：1 二分搜索，排序算法(快速排序，歸并排序)，動態(tài)規(guī)劃；2 傅立葉變換(快速傅立葉變換)；3 程序模塊化設(shè)計；
動態(tài)規(guī)劃（DP）
?核心點:
- 實際工作中很少用到，工作多年，從來沒有在工作中使用過動態(tài)規(guī)劃。
- 核心是了解其思想和原理:
- 動態(tài)規(guī)劃最核心的思想，就在于拆分子問題，記住過往，減少重復(fù)計算；
- 深刻理解最優(yōu)子結(jié)構(gòu)，重疊子問題，狀態(tài)轉(zhuǎn)移方程，無后效性，以及邊界條件；
- 熟悉各種類型DP特點，普通DP，區(qū)間DP，樹形DP，數(shù)位DP，狀態(tài)壓縮DP等；
- 應(yīng)對面試，刷幾道題就行，一般面試很少出動態(tài)規(guī)劃的題，校招可能會出，社招基本上不會出；
- 如果你要參加ACM or OJ 這種比賽，必須掌握, 這個區(qū)分菜鳥的分界點。
最后總結(jié)
程序 = 數(shù)據(jù)結(jié)構(gòu) 算法?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ?---Niklaus EmilWirth程序本質(zhì)是數(shù)據(jù)結(jié)構(gòu) 算法，任何一門語言都可以這樣理解，這個公式對計算機科學(xué)的影響程度足以類似物理學(xué)中愛因斯坦的“E=MC^2”——一個公式展示出了程序的本質(zhì)。其實在工作中，最重要是設(shè)計好數(shù)據(jù)結(jié)構(gòu)，因為在設(shè)計數(shù)據(jù)結(jié)構(gòu)的時候，就是性能和實現(xiàn)難度的權(quán)衡，程序當(dāng)然是越簡單越好，但為了性能，有時候不得不設(shè)計出像紅黑樹這種復(fù)雜數(shù)據(jù)結(jié)構(gòu)。
希望我們都可以掌握好算法核心思想，和常見數(shù)據(jù)結(jié)構(gòu)精妙設(shè)計，幫助我們在面試和工作中打好堅實的基礎(chǔ)；
擴展閱讀
https://www.cnblogs.com/binarylei/p/12419863.htmlhttps://en.wikipedia.org/wiki/Quicksorthttps://mp.weixin.qq.com/s/7PZ6L1YzPZdiMNK25sUqjghttps://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/https://www.drdobbs.com/parallel/choose-concurrency-friendly-data-structu/208801371https://cloud.tencent.com/developer/article/1136054Robert Sedgewick. Left-leaning Red–Black Treeshttps://cloud.tencent.com/developer/news/652039https://github.com/greyireland/algorithm-patternhttps://www.huaweicloud.com/articles/1bce95370dbe6348fe3f277968cf078c.html- EOF -
下載文檔
