|
作為一名前端開發(fā)工程師，你可能有時會問：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)或者算法對于前端工程師有用么,？ 總的來說,，這些基礎(chǔ)學(xué)科在短期內(nèi)收效確實甚微，但是我們首先不要將自己局限在前端工程師這點(diǎn)上,，當(dāng)我們把視野放到編程這個角度去說,，數(shù)據(jù)結(jié)構(gòu)算法一定是有用的，并且也是你未來的一個天花板,?？梢圆换ㄙM(fèi)集中的時間去學(xué)習(xí)這些內(nèi)容，但是一定需要時常去學(xué)習(xí)一點(diǎn),，因為這些技能可以實實在在提升你寫代碼的能力,。 這一篇文章的內(nèi)容信息量會很大，代碼也比較多,，為了方便大家閱讀,，有些代碼我會轉(zhuǎn)成圖片。 時間復(fù)雜度 在進(jìn)入正題之前,，我們先來了解下什么是時間復(fù)雜度,。 通常使用最差的時間復(fù)雜度來衡量一個算法的好壞。 常數(shù)時間 O(1) 代表這個操作和數(shù)據(jù)量沒關(guān)系，是一個固定時間的操作,，比如說四則運(yùn)算,。 對于一個算法來說，可能會計算出操作次數(shù)為 aN 1,，N 代表數(shù)據(jù)量,。那么該算法的時間復(fù)雜度就是 O(N)。因為我們在計算時間復(fù)雜度的時候,，數(shù)據(jù)量通常是非常大的,，這時候低階項和常數(shù)項可以忽略不計。 當(dāng)然可能會出現(xiàn)兩個算法都是 O(N) 的時間復(fù)雜度,，那么對比兩個算法的好壞就要通過對比低階項和常數(shù)項了,。 棧概念 棧是一個線性結(jié)構(gòu)，在計算機(jī)中是一個相當(dāng)常見的數(shù)據(jù)結(jié)構(gòu),。 棧的特點(diǎn)是只能在某一端添加或刪除數(shù)據(jù),，遵循先進(jìn)后出的原則 實現(xiàn) 每種數(shù)據(jù)結(jié)構(gòu)都可以用很多種方式來實現(xiàn)，其實可以把?？闯墒菙?shù)組的一個子集,，所以這里使用數(shù)組來實現(xiàn) class Stack {
constructor() {
this.stack = []
}
push(item) {
this.stack.push(item)
}
pop() {
this.stack.pop()
}
peek() {
return this.stack[this.getCount() - 1]
}
getCount() {
return this.stack.length
}
isEmpty() {
return this.getCount() === 0
}
}
應(yīng)用 題意是匹配括號，可以通過棧的特性來完成這道題目 var isValid = function (s) {
let map = {
'(': -1,
')': 1,
'[': -2,
']': 2,
'{': -3,
'}': 3
}
let stack = []
for (let i = 0; i < s.length; i ) {
if (map[s[i]] < 0) {
stack.push(s[i])
} else {
let last = stack.pop()
if (map[last] map[s[i]] != 0) return false
}
}
if (stack.length > 0) return false
return true
};
其實在 Vue 中關(guān)于模板解析的代碼,，就有應(yīng)用到匹配尖括號的內(nèi)容,。 隊列概念 隊列是一個線性結(jié)構(gòu)，特點(diǎn)是在某一端添加數(shù)據(jù),，在另一端刪除數(shù)據(jù),，遵循先進(jìn)先出的原則。 實現(xiàn) 這里會講解兩種實現(xiàn)隊列的方式,，分別是單鏈隊列和循環(huán)隊列,。 單鏈隊列 class Queue {
constructor() {
this.queue = []
}
enQueue(item) {
this.queue.push(item)
}
deQueue() {
return this.queue.shift()
}
getHeader() {
return this.queue[0]
}
getLength() {
return this.queue.length
}
isEmpty() {
return this.getLength() === 0
}
}
因為單鏈隊列在出隊操作的時候需要 O(n) 的時間復(fù)雜度，所以引入了循環(huán)隊列,。循環(huán)隊列的出隊操作平均是 O(1) 的時間復(fù)雜度,。 循環(huán)隊列 我們直接看代碼： 鏈表概念 鏈表是一個線性結(jié)構(gòu)，同時也是一個天然的遞歸結(jié)構(gòu),。鏈表結(jié)構(gòu)可以充分利用計算機(jī)內(nèi)存空間,，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn),，同時鏈表由于增加了結(jié)點(diǎn)的指針域,，空間開銷比較大。 實現(xiàn) 下面我們主要以單向鏈表為例,。 單向鏈表 樹二叉樹 樹擁有很多種結(jié)構(gòu),，二叉樹是樹中最常用的結(jié)構(gòu)，同時也是一個天然的遞歸結(jié)構(gòu)。 二叉樹擁有一個根節(jié)點(diǎn),，每個節(jié)點(diǎn)至多擁有兩個子節(jié)點(diǎn),，分別為：左節(jié)點(diǎn)和右節(jié)點(diǎn)。樹的最底部節(jié)點(diǎn)稱之為葉節(jié)點(diǎn),，當(dāng)一顆樹的葉數(shù)量數(shù)量為滿時,，該樹可以稱之為滿二叉樹。 二分搜索樹 二分搜索樹也是二叉樹,，擁有二叉樹的特性,。但是區(qū)別在于二分搜索樹每個節(jié)點(diǎn)的值都比他的左子樹的值大,，比右子樹的值小,。 這種存儲方式很適合于數(shù)據(jù)搜索。如下圖所示,，當(dāng)需要查找 6 的時候,，因為需要查找的值比根節(jié)點(diǎn)的值大，所以只需要在根節(jié)點(diǎn)的右子樹上尋找,，大大提高了搜索效率,。 實現(xiàn) 以上是最基本的二分搜索樹實現(xiàn)，接下來實現(xiàn)樹的遍歷,。 對于樹的遍歷來說,，有三種遍歷方法，分別是先序遍歷,、中序遍歷,、后序遍歷。三種遍歷的區(qū)別在于何時訪問節(jié)點(diǎn),。在遍歷樹的過程中,，每個節(jié)點(diǎn)都會遍歷三次，分別是遍歷到自己,，遍歷左子樹和遍歷右子樹,。如果需要實現(xiàn)先序遍歷，那么只需要第一次遍歷到節(jié)點(diǎn)時進(jìn)行操作即可,。 以上的這幾種遍歷都可以稱之為深度遍歷,，對應(yīng)的還有種遍歷叫做廣度遍歷，也就是一層層地遍歷樹,。對于廣度遍歷來說,，我們需要利用之前講過的隊列結(jié)構(gòu)來完成。
接下來先介紹如何在樹中尋找最小值或最大數(shù),。因為二分搜索樹的特性,，所以最小值一定在根節(jié)點(diǎn)的最左邊，最大值相反
向上取整和向下取整，這兩個操作是相反的,，所以代碼也是類似的,，這里只介紹如何向下取整。既然是向下取整,，那么根據(jù)二分搜索樹的特性,，值一定在根節(jié)點(diǎn)的左側(cè)。只需要一直遍歷左子樹直到當(dāng)前節(jié)點(diǎn)的值不再大于等于需要的值,，然后判斷節(jié)點(diǎn)是否還擁有右子樹,。如果有的話，繼續(xù)上面的遞歸判斷,。
排名,，這是用于獲取給定值的排名或者排名第幾的節(jié)點(diǎn)的值，這兩個操作也是相反的,，所以這個只介紹如何獲取排名第幾的節(jié)點(diǎn)的值,。對于這個操作而言，我們需要略微的改造點(diǎn)代碼,，讓每個節(jié)點(diǎn)擁有一個 size 屬性,。該屬性表示該節(jié)點(diǎn)下有多少子節(jié)點(diǎn)（包含自身）。
接下來講解的是二分搜索樹中最難實現(xiàn)的部分：刪除節(jié)點(diǎn),。因為對于刪除節(jié)點(diǎn)來說,，會存在以下幾種情況
對于前兩種情況很好解決，但是第三種情況就有難度了,，所以先來實現(xiàn)相對簡單的操作：刪除最小節(jié)點(diǎn),，對于刪除最小節(jié)點(diǎn)來說，是不存在第三種情況的,，刪除最大節(jié)點(diǎn)操作是和刪除最小節(jié)點(diǎn)相反的,，所以這里也就不再贅述。
最后講解的就是如何刪除任意節(jié)點(diǎn)了,。對于這個操作,，T.Hibbard 在 1962 年提出了解決這個難題的辦法，也就是如何解決第三種情況,。 當(dāng)遇到這種情況時,，需要取出當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)（也就是當(dāng)前節(jié)點(diǎn)右子樹的最小節(jié)點(diǎn)）來替換需要刪除的節(jié)點(diǎn)。然后將需要刪除節(jié)點(diǎn)的左子樹賦值給后繼結(jié)點(diǎn),，右子樹刪除后繼結(jié)點(diǎn)后賦值給他,。 你如果對于這個解決辦法有疑問的話，可以這樣考慮,。因為二分搜索樹的特性,，父節(jié)點(diǎn)一定比所有左子節(jié)點(diǎn)大,，比所有右子節(jié)點(diǎn)小。那么當(dāng)需要刪除父節(jié)點(diǎn)時,，勢必需要拿出一個比父節(jié)點(diǎn)大的節(jié)點(diǎn)來替換父節(jié)點(diǎn),。這個節(jié)點(diǎn)肯定不存在于左子樹，必然存在于右子樹,。然后又需要保持父節(jié)點(diǎn)都是比右子節(jié)點(diǎn)小的,，那么就可以取出右子樹中最小的那個節(jié)點(diǎn)來替換父節(jié)點(diǎn)。
AVL 樹概念 二分搜索樹實際在業(yè)務(wù)中是受到限制的,，因為并不是嚴(yán)格的 O(logN),，在極端情況下會退化成鏈表，比如加入一組升序的數(shù)字就會造成這種情況,。 AVL 樹改進(jìn)了二分搜索樹,，在 AVL 樹中任意節(jié)點(diǎn)的左右子樹的高度差都不大于 1，這樣保證了時間復(fù)雜度是嚴(yán)格的 O(logN),?；诖耍瑢?AVL 樹增加或刪除節(jié)點(diǎn)時可能需要旋轉(zhuǎn)樹來達(dá)到高度的平衡,。 實現(xiàn) 因為 AVL 樹是改進(jìn)了二分搜索樹，所以部分代碼是于二分搜索樹重復(fù)的,，對于重復(fù)內(nèi)容不作再次解析,。 對于 AVL 樹來說，添加節(jié)點(diǎn)會有四種情況
對于左左情況來說,，新增加的節(jié)點(diǎn)位于節(jié)點(diǎn) 2 的左側(cè),，這時樹已經(jīng)不平衡，需要旋轉(zhuǎn),。因為搜索樹的特性,，節(jié)點(diǎn)比左節(jié)點(diǎn)大，比右節(jié)點(diǎn)小,，所以旋轉(zhuǎn)以后也要實現(xiàn)這個特性,。 旋轉(zhuǎn)之前：new < 2 < C < 3 < B < 5 < A，右旋之后節(jié)點(diǎn) 3 為根節(jié)點(diǎn),，這時候需要將節(jié)點(diǎn) 3 的右節(jié)點(diǎn)加到節(jié)點(diǎn) 5 的左邊,，最后還需要更新節(jié)點(diǎn)的高度。 對于右右情況來說,，相反于左左情況,，所以不再贅述。 對于左右情況來說,，新增加的節(jié)點(diǎn)位于節(jié)點(diǎn) 4 的右側(cè),。對于這種情況,，需要通過兩次旋轉(zhuǎn)來達(dá)到目的。 首先對節(jié)點(diǎn)的左節(jié)點(diǎn)左旋,，這時樹滿足左左的情況,，再對節(jié)點(diǎn)進(jìn)行一次右旋就可以達(dá)到目的。
Trie概念 在計算機(jī)科學(xué),，trie,，又稱前綴樹或字典樹，是一種有序樹,，用于保存關(guān)聯(lián)數(shù)組,，其中的鍵通常是字符串。 簡單點(diǎn)來說,，這個結(jié)構(gòu)的作用大多是為了方便搜索字符串,，該樹有以下幾個特點(diǎn)
實現(xiàn) 總得來說 Trie 的實現(xiàn)相比別的樹結(jié)構(gòu)來說簡單的很多，實現(xiàn)就以搜索英文字符為例,。
并查集概念 并查集是一種特殊的樹結(jié)構(gòu),，用于處理一些不交集的合并及查詢問題。該結(jié)構(gòu)中每個節(jié)點(diǎn)都有一個父節(jié)點(diǎn),，如果只有當(dāng)前一個節(jié)點(diǎn),，那么該節(jié)點(diǎn)的父節(jié)點(diǎn)指向自己。 這個結(jié)構(gòu)中有兩個重要的操作,，分別是：
實現(xiàn)
堆概念 堆通常是一個可以被看做一棵樹的數(shù)組對象,。 堆的實現(xiàn)通過構(gòu)造二叉堆，實為二叉樹的一種,。這種數(shù)據(jù)結(jié)構(gòu)具有以下性質(zhì),。
將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆,，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆,。 優(yōu)先隊列也完全可以用堆來實現(xiàn),，操作是一模一樣的。 實現(xiàn)大根堆 堆的每個節(jié)點(diǎn)的左邊子節(jié)點(diǎn)索引是 i * 2 1,，右邊是 i * 2 2,，父節(jié)點(diǎn)是 (i - 1) /2。 堆有兩個核心的操作,，分別是 shiftUp 和 shiftDown ,。前者用于添加元素，后者用于刪除根節(jié)點(diǎn),。 shiftUp 的核心思路是一路將節(jié)點(diǎn)與父節(jié)點(diǎn)對比大小,，如果比父節(jié)點(diǎn)大，就和父節(jié)點(diǎn)交換位置,。 shiftDown 的核心思路是先將根節(jié)點(diǎn)和末尾交換位置,，然后移除末尾元素。接下來循環(huán)判斷父節(jié)點(diǎn)和兩個子節(jié)點(diǎn)的大小,，如果子節(jié)點(diǎn)大,，就把最大的子節(jié)點(diǎn)和父節(jié)點(diǎn)交換。
下面是代碼實現(xiàn)方案
小結(jié)這一篇主要介紹了一些比較常見的數(shù)據(jù)結(jié)構(gòu),，當(dāng)然還有其他更難的數(shù)據(jù)結(jié)構(gòu),，這次沒有放進(jìn)來，是因為小編覺得如果能夠掌握這些常見的內(nèi)容已經(jīng)足夠解決大部分的問題了,。當(dāng)然你如果還想繼續(xù)深入學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),，可以閱讀《算法第四版》以及在 leetcode 中去實踐。 |
|
|
