走過(guò)路過(guò)不要錯(cuò)過(guò)

點(diǎn)擊藍(lán)字關(guān)注我們

前言

隨著互聯(lián)網(wǎng)寒潮的到來(lái), 越來(lái)越多的互聯(lián)網(wǎng)公司提高了面試的難度，其中之一就是加大了面試當(dāng)中手撕算法題的比例。這里說(shuō)的算法題不是深度學(xué)習(xí)，機(jī)器學(xué)習(xí)這類的算法，而是排序，廣度優(yōu)先，動(dòng)態(tài)規(guī)劃這類既考核數(shù)據(jù)結(jié)構(gòu)也考核編程能力的題目。刷題的網(wǎng)址非常的多，其中以leetcode是最為出名的。

在刷題上，我花了大量的時(shí)間，蹚了許多的坑，總結(jié)了一下，主要有這三個(gè)問(wèn)題:

刷過(guò)的題老是忘，第二次刷的時(shí)候還是不會(huì)做
刷題的速度很慢，即使花一天時(shí)間，也常常只能刷五六道
堅(jiān)持不下來(lái)，老是刷到一半就停滯下來(lái)了，當(dāng)我第二次再來(lái)刷的時(shí)候，前面刷過(guò)的題都又忘的差不多

說(shuō)出來(lái)都是淚，感覺(jué)刷題這個(gè)路是真的難走，花了很多時(shí)間，但是感覺(jué)沒(méi)有什么收獲。所以最近我一直在反思自己刷題的方法，希望能夠提高刷題的效率和速度。當(dāng)我總結(jié)了以下方法以后，我很明顯的感受到自己的刷題速度從以前周末的一天五六道提升到周末一天刷十五六道以上，速度相比以前提升的非常明顯。

本文采用Java語(yǔ)言來(lái)進(jìn)行描述，幫大家好好梳理一下數(shù)據(jù)結(jié)構(gòu)與算法，在工作和面試中用的上。亦即總結(jié)常見(jiàn)的的數(shù)據(jù)結(jié)構(gòu)，以及在Java中相應(yīng)的實(shí)現(xiàn)方法，務(wù)求理論與實(shí)踐一步總結(jié)到位。

常用數(shù)據(jù)結(jié)構(gòu)

數(shù)組

數(shù)組是相同數(shù)據(jù)類型的元素按一定順序排列的集合，是一塊連續(xù)的內(nèi)存空間。數(shù)組的優(yōu)點(diǎn)是：get和set操作時(shí)間上都是O(1)的；缺點(diǎn)是：add和remove操作時(shí)間上都是O(N)的。

Java中，Array就是數(shù)組，此外，ArrayList使用了數(shù)組Array作為其實(shí)現(xiàn)基礎(chǔ),它和一般的Array相比，最大的好處是，我們?cè)谔砑釉貢r(shí)不必考慮越界，元素超出數(shù)組容量時(shí)，它會(huì)自動(dòng)擴(kuò)張保證容量。

Vector和ArrayList相比，主要差別就在于多了一個(gè)線程安全性，但是效率比較低下。如今java.util.concurrent包提供了許多線程安全的集合類（比如 LinkedBlockingQueue），所以不必再使用Vector了。

鏈表

鏈表是一種非連續(xù)、非順序的結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的，鏈表由一系列結(jié)點(diǎn)組成。鏈表的優(yōu)點(diǎn)是：add和remove操作時(shí)間上都是O(1)的；缺點(diǎn)是：get和set操作時(shí)間上都是O(N)的，而且需要額外的空間存儲(chǔ)指向其他數(shù)據(jù)地址的項(xiàng)。

查找操作對(duì)于未排序的數(shù)組和鏈表時(shí)間上都是O(N)。

隊(duì)列

隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作，亦即所謂的先進(jìn)先出（FIFO）。

Java中，LinkedList實(shí)現(xiàn)了Deque，可以做為雙向隊(duì)列（自然也可以用作單向隊(duì)列）。另外PriorityQueue實(shí)現(xiàn)了帶優(yōu)先級(jí)的隊(duì)列，亦即隊(duì)列的每一個(gè)元素都有優(yōu)先級(jí)，且元素按照優(yōu)先級(jí)排序。

棧

棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。它體現(xiàn)了后進(jìn)先出（LIFO）的特點(diǎn)。

Java中，Stack實(shí)現(xiàn)了這種特性，但是Stack也繼承了Vector，所以具有線程安全線和效率低下兩個(gè)特性，最新的JDK8中，推薦用Deque來(lái)實(shí)現(xiàn)棧。

集合

集合是指具有某種特定性質(zhì)的具體的或抽象的對(duì)象匯總成的集體，這些對(duì)象稱為該集合的元素，其主要特性是元素不可重復(fù)。

在Java中，HashSet 體現(xiàn)了這種數(shù)據(jù)結(jié)構(gòu)，而HashSet是在MashMap的基礎(chǔ)上構(gòu)建的。LinkedHashSet繼承了HashSet，使用HashCode確定在集合中的位置，使用鏈表的方式確定位置，所以有順序。

TreeSet實(shí)現(xiàn)了SortedSet 接口，是排好序的集合（在TreeMap 基礎(chǔ)之上構(gòu)建），因此查找操作比普通的Hashset要快（log(N)）；插入操作要慢（log（N））,因?yàn)橐S護(hù)有序。

散列表

散列表也叫哈希表，是根據(jù)關(guān)鍵鍵值(Keyvalue)進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度，這個(gè)映射函數(shù)叫做散列函數(shù)。

Java中HashMap實(shí)現(xiàn)了散列表，而Hashtable比它多了一個(gè)線程安全性，但是由于使用了全局鎖導(dǎo)致其性能較低，所以現(xiàn)在一般用ConcurrentHashMap來(lái)實(shí)現(xiàn)線程安全的HashMap（類似的，以上的數(shù)據(jù)結(jié)構(gòu)在最新的java.util.concurrent的包中幾乎都有對(duì)應(yīng)的高性能的線程安全的類）。

TreeMap實(shí)現(xiàn)SortMap接口，能夠把它保存的記錄按照鍵排序。LinkedHashMap保留了元素插入的順序。WeakHashMap是一種改進(jìn)的HashMap，它對(duì)key實(shí)行“弱引用”，如果一個(gè)key不再被外部所引用，那么該key可以被GC回收，而不需要我們手動(dòng)刪除。

樹(shù)

樹(shù)（tree）是包含n（n>0）個(gè)節(jié)點(diǎn)的有窮集合，其中：

每個(gè)元素稱為節(jié)點(diǎn)（node）
有一個(gè)特定的節(jié)點(diǎn)被稱為根節(jié)點(diǎn)或樹(shù)根（root）
除根節(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分為m（m≥0）個(gè)互不相交的結(jié)合T1，T2，……Tm-1，其中每一個(gè)集合Ti（1<=i<=m）本身也是一棵樹(shù)，被稱作原樹(shù)的子樹(shù)（subtree）

樹(shù)這種數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)世界中有廣泛的應(yīng)用，比如操作系統(tǒng)中用到了紅黑樹(shù)，數(shù)據(jù)庫(kù)用到了B+樹(shù)，編譯器中的語(yǔ)法樹(shù)，內(nèi)存管理用到了堆（本質(zhì)上也是樹(shù)），信息論中的哈夫曼編碼等等等等，在Java中TreeSet和TreeMap用到了樹(shù)來(lái)排序（二分查找提高檢索速度），不過(guò)一般都需要程序員自己去定義一個(gè)樹(shù)的類，并實(shí)現(xiàn)相關(guān)性質(zhì)，而沒(méi)有現(xiàn)成的API。

下面用Java來(lái)實(shí)現(xiàn)各種常見(jiàn)的樹(shù)。

二叉樹(shù)

二叉樹(shù)是一種基礎(chǔ)而且重要的數(shù)據(jù)結(jié)構(gòu)，其每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)，二叉樹(shù)有左右子樹(shù)之分，第i層至多有2(i-1)個(gè)結(jié)點(diǎn)（i從1開(kāi)始）；深度為k的二叉樹(shù)至多有2(k)-1)個(gè)結(jié)點(diǎn)，對(duì)任何一棵二叉樹(shù)，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。

二叉樹(shù)的性質(zhì)：

在非空二叉樹(shù)中，第i層的結(jié)點(diǎn)總數(shù)不超過(guò)2^(i-1), i>=1;
深度為h的二叉樹(shù)最多有2^h-1個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn);
對(duì)于任意一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1;
具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2(n+1);
有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)各結(jié)點(diǎn)如果用順序方式存儲(chǔ)，則結(jié)點(diǎn)之間有如下關(guān)系：若I為結(jié)點(diǎn)編號(hào)則如果I>1，則其父結(jié)點(diǎn)的編號(hào)為I/2；如果2I<=N，則其左兒子（即左子樹(shù)的根結(jié)點(diǎn)）的編號(hào)為2I；若2I>N，則無(wú)左兒子；如果2I+1<=N，則其右兒子的結(jié)點(diǎn)編號(hào)為2I+1；若2I+1>N，則無(wú)右兒子。
給定N個(gè)節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹(shù)，其中h(N)為卡特蘭數(shù)的第N項(xiàng)，h(n)=C(2*n, n)/(n+1)。
設(shè)有i個(gè)枝點(diǎn)，I為所有枝點(diǎn)的道路長(zhǎng)度總和，J為葉的道路長(zhǎng)度總和J=I+2i。

滿二叉樹(shù)、完全二叉樹(shù)

滿二叉樹(shù)：除最后一層無(wú)任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)；

完全二叉樹(shù)：若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 (1～(h-1)層) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)；

滿二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例。

二叉查找樹(shù)

二叉查找樹(shù)，又稱為是二叉排序樹(shù)（Binary Sort Tree）或二叉搜索樹(shù)。二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：

若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
左、右子樹(shù)也分別為二叉排序樹(shù)；
沒(méi)有鍵值相等的節(jié)點(diǎn)。

二叉查找樹(shù)的性質(zhì)：對(duì)二叉查找樹(shù)進(jìn)行中序遍歷，即可得到有序的數(shù)列。二叉查找樹(shù)的時(shí)間復(fù)雜度：它和二分查找一樣，插入和查找的時(shí)間復(fù)雜度均為O(logn)，但是在最壞的情況下仍然會(huì)有O(n)的時(shí)間復(fù)雜度。原因在于插入和刪除元素的時(shí)候，樹(shù)沒(méi)有保持平衡。我們追求的是在最壞的情況下仍然有較好的時(shí)間復(fù)雜度，這就是平衡二叉樹(shù)設(shè)計(jì)的初衷。

平衡二叉樹(shù)

平衡二叉樹(shù)又被稱為AVL樹(shù)，具有以下性質(zhì)：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。它的出現(xiàn)就是解決二叉查找樹(shù)不平衡導(dǎo)致查找效率退化為線性的問(wèn)題，因?yàn)樵趧h除和插入之時(shí)會(huì)維護(hù)樹(shù)的平衡，使得查找時(shí)間保持在O(logn)，比二叉查找樹(shù)更穩(wěn)定。

堆

堆是一顆完全二叉樹(shù)，在這棵樹(shù)中，所有父節(jié)點(diǎn)都滿足大于等于其子節(jié)點(diǎn)的堆叫大根堆，所有父節(jié)點(diǎn)都滿足小于等于其子節(jié)點(diǎn)的堆叫小根堆。堆雖然是一顆樹(shù)，但是通常存放在一個(gè)數(shù)組中，父節(jié)點(diǎn)和孩子節(jié)點(diǎn)的父子關(guān)系通過(guò)數(shù)組下標(biāo)來(lái)確定。

堆的用途：堆排序，優(yōu)先級(jí)隊(duì)列。此外由于調(diào)整代價(jià)較小，也適合實(shí)時(shí)類型的排序與變更。

最后

寫(xiě)著寫(xiě)著就發(fā)現(xiàn)要想總結(jié)到位是一項(xiàng)非常龐大的工程，路漫漫其修遠(yuǎn)兮，吾將上下而求索。

我個(gè)人認(rèn)為，作為技術(shù)人就要保持終生學(xué)習(xí)的態(tài)度，讓學(xué)習(xí)力成為核心競(jìng)爭(zhēng)力，才能不被時(shí)代所淘汰，而高效的時(shí)間支配能讓你變得更加優(yōu)秀，所以，我在這里將這份耗時(shí)兩個(gè)月搜集的算法刷題書(shū)籍，送給有需要的人，希望這些資料能對(duì)大家有所幫助

《算法的樂(lè)趣》