工作中可能會(huì)使用到的數(shù)據(jù)結(jié)構(gòu)和算法
背景
我們?nèi)粘５拈_(kāi)發(fā)工作避免不了和數(shù)據(jù)打交道。展示數(shù)據(jù)時(shí)，接口返回的數(shù)據(jù)結(jié)構(gòu)可能沒(méi)辦法直接拿來(lái)使用，需要做一層轉(zhuǎn)換；保存數(shù)據(jù)時(shí)，通過(guò)表單拿到的數(shù)據(jù)結(jié)構(gòu)和接口定義的數(shù)據(jù)結(jié)構(gòu)也可能不一致，需要做一層轉(zhuǎn)換；還有一些業(yè)務(wù)場(chǎng)景本身的需要，需要對(duì)數(shù)據(jù)的邏輯校驗(yàn)等。因此避免不了會(huì)使用到一些常用的數(shù)據(jù)結(jié)構(gòu)和算法。本文主要是討論在前端開(kāi)發(fā)工作中，可能會(huì)使用到的數(shù)據(jù)結(jié)構(gòu)和算法。
數(shù)據(jù)結(jié)構(gòu)
棧
棧是一種特殊的線性表。它的特點(diǎn)是，只能在表的一端操作?？梢圆僮鞯亩朔Q為棧頂，不可以操作的另一端稱為棧底。棧的特性：先進(jìn)后出。
原理
生活中的例子：蒸饅頭的籠屜、羽毛球筒。
實(shí)現(xiàn)
我們可以使用 JS 來(lái)模擬棧的功能。從數(shù)據(jù)存儲(chǔ)的方式來(lái)看，可以使用數(shù)組存儲(chǔ)數(shù)據(jù)，也可以使用鏈表存儲(chǔ)數(shù)據(jù)。因?yàn)閿?shù)組是最簡(jiǎn)單的方式，所以這里是用數(shù)組的方式來(lái)實(shí)現(xiàn)棧。
棧的操作包括入棧、出棧、清空、獲取棧頂元素、獲取棧的大小等。
class Stack {
constructor() {
// 存儲(chǔ)數(shù)據(jù)
this.items = [];
}
push(item) {
// 入棧
this.items.push(item);
}
pop() {
// 出棧
return this.items.pop();
}
top() {
// 獲取棧頂元素
return this.items[this.items.length - 1];
}
clear() {
// 清空棧
this.items = [];
}
size() {
// 獲取棧的大小
return this.items.length;
}
isEmpty() {
// 判斷棧是否為空
return this.items.length === 0;
}
}
應(yīng)用
判斷括號(hào)是否匹配
方法一思路分析：
首先從頭到尾遍歷整個(gè)字符串； 當(dāng)遇到字符"("則入棧，遇到字符")"則出棧； 出棧時(shí)，如果棧已經(jīng)為空，則返回 false； 當(dāng)字符串遍歷完畢以后，判斷棧是否為空。
方法二思路分析：
聲明變量 num 為 0，并從頭到尾遍歷整個(gè)字符串； 當(dāng)遇到字符"("則 num 加 1，遇到字符")"num 減 1； 在遍歷的過(guò)程中，當(dāng) num 減 1 時(shí)，num 的值已經(jīng)為 0 則返回 false； 當(dāng)字符串遍歷完畢以后，判斷 num 是否為 0。
// 方式一：棧
function isPairing(str = '') {
const stack = new Stack();
for(let i of str) {
if (i === '(') {
stack.push(i);
} else if (i === ')') {
if (stack.isEmpty()) {
return false;
} else {
stack.pop();
}
}
}
return stack.size() === 0;
}
// 方式二：計(jì)數(shù)
function isPairing(str = '') {
let num = 0;
for(let i of str) {
if (i === '(') {
num++;
} else if (i === ')') {
if (num === 0) {
return false;
} else {
num--;
}
}
}
return num === 0;
}
判斷 HTML 標(biāo)簽是否匹配
思路分析：
聲明變量 stack、nodes；并從頭遍歷 HTML 字符串，查找字符"<"的位置；
如果字符"<"的位置等于 0：
則繼續(xù)嘗試匹配 HTML 結(jié)束標(biāo)簽，匹配成功并且與棧頂?shù)臉?biāo)簽名稱一致，則彈出棧頂；否則報(bào)錯(cuò)； 匹配 HTML 結(jié)束標(biāo)簽失敗以后，則嘗試匹配開(kāi)始標(biāo)簽的起始部分，然后循環(huán)匹配標(biāo)簽屬性對(duì)，最后匹配開(kāi)始標(biāo)簽的結(jié)束部分。匹配完成以后，將匹配到的標(biāo)簽壓入棧頂；并構(gòu)建 node 節(jié)點(diǎn)數(shù)； 如果字符"<"的位置大于 0：
則 html.slice(0, pos)，創(chuàng)建文本節(jié)點(diǎn)。
function parseHtml(html = '') {
const startIndex = 0;
const endIndex = 0;
// 匹配標(biāo)簽<div>、<br/>等標(biāo)簽的開(kāi)始部分"<div、<br"
const startTagOpen = /^<([a-zA-Z\d]+)/;
// 匹配標(biāo)簽<div>、<br/>等標(biāo)簽的閉合部分">、/>"
const startTagClose = /^\s*(\/?)>/;
// 匹配屬性
const attribute = /^\s*([\w-]+)(?:="([^"]*)")?\s*/;
// 匹配閉合標(biāo)簽，例如</div>、</p>
const endTag = /^<\/([a-zA-Z\d]+)>/;
const stack = [];
const nodes = [];
while(html) {
// 查找<的起始位置
const index = html.indexOf('<');
if (index === 0) {
// 先匹配整體結(jié)束標(biāo)簽，例如</div>、</p>
let endTagMatch = html.match(endTag);
if (endTagMatch) {
if (stack[stack.length - 1]) {
if (stack[stack.length - 1].tag === endTagMatch[1]) {
// 出棧
stack.pop();
advanced(endTagMatch[0].length);
continue;
} else {
throw new Error(`起始標(biāo)簽和結(jié)束標(biāo)簽不匹配: 起始標(biāo)簽（${stack[stack.length - 1].tag}），結(jié)束標(biāo)簽（${endTagMatch[0]}）`);
}
} else {
throw new Error(`${endTagMatch[0]}沒(méi)有起始標(biāo)簽`);
}
}
// 然后匹配起始標(biāo)簽的開(kāi)始部分，例如<div>的<div、<p>的<p、<br/>的<br
let startTagOpenMatch = html.match(startTagOpen);
if (startTagOpenMatch) {
const node = {
nodeType: 1,
tag: startTagOpenMatch[1],
attrs: [],
children: [],
};
advanced(startTagOpenMatch[0].length);
let end, attr;
// 匹配標(biāo)簽屬性列表
while(!(end = html.match(startTagClose)) && (attr = html.match(attribute))) {
advanced(attr[0].length);
node.attrs.push({
name: attr[1],
value: attr[2],
});
}
// 匹配起始標(biāo)簽的結(jié)束部分
if (end) {
if (stack.length === 0) {
nodes.push(node);
} else {
stack[stack.length - 1].children.push(node);
}
// 自閉和標(biāo)簽不加入棧中
if (end[1] !== '/') {
stack.push(node);
}
advanced(end[0].length);
}
}
} else {
// 文本
const node = {
nodeType: 3,
textContent: html.slice(0, index)
};
if (stack.length === 0) {
nodes.push(node);
} else {
stack[stack.length - 1].children.push(node);
}
advanced(node.textContent.length);
}
}
function advanced(n) {
html = html.substring(n);
}
return nodes;
}
parseHtml('<div id="test" class="a b"></div>');
parseHtml('<div id="test" class="a b">Hello World</div>');
parseHtml('開(kāi)始<div id="test" class="a b">Hello World</div>');
parseHtml('<div id="test" class="a b"><br class="br" />Hello World</div>');
parseHtml('</div>');
parseHtml('<div></p>');
版本號(hào)比較大小
思路分析：
版本號(hào) v1、v2 按照符號(hào)"."分割成數(shù)組，從左右依次進(jìn)行大小比較； v1 大于 v2 返回 1，v2 小于 v2 返回-1，v1 等于 v2 返回 0。
/*
比較版本號(hào)大小
v1：第一個(gè)版本號(hào)
v2：第二個(gè)版本號(hào)
如果版本號(hào)相等，返回 0, * 如果第一個(gè)版本號(hào)低于第二個(gè)，返回 -1，否則返回 1.
*/
function compareVersion(v1, v2) {
if (!v1 && !v2) return 0;
if (!v1) return -1;
if (!v2) return 1;
const v1Stack = v1.split('.');
const v2Stack = v2.split('.');
const maxLen = Math.max(v1Stack.length, v2Stack.length);
for(let i = 0; i < maxLen; i++) {
// 必須轉(zhuǎn)整，否則按照字符順序比較大小
const prevVal = ~~v1Stack[i];
const currVal = ~~v2Stack[i];
if (prevVal > currVal) {
return 1;
}
if (prevVal < currVal) {
return -1;
}
}
return 0;
}
console.log(compareVersion("2.2.1", "2.2.01")); // 0
console.log(compareVersion("2.2.1", "2.2.0")); // 1
console.log(compareVersion("2.2.1", "2.1.9")); // 1
console.log(compareVersion("2.2", "2.1.1")); // 1
console.log(compareVersion("2.2", "2.2.1")); // -1
console.log(compareVersion("2.2.3.4.5.6", "2.2.2.4.5.12")); // 1
console.log(compareVersion("2.2.3.4.5.6", "2.2.3.4.5.12")); // -1
用途
Vue 模板編譯將模板字符串轉(zhuǎn)換成 AST。 自動(dòng)更新最新版本的 NPM 包。 函數(shù)執(zhí)行上下文棧。
隊(duì)列
隊(duì)列也是一種特殊的線性表，它的特點(diǎn)是，只能在表的一端進(jìn)行刪除操作，而在表的另一點(diǎn)進(jìn)行插入操作。可以進(jìn)行刪除操作的端稱為隊(duì)首，而可以進(jìn)行插入操作的端稱為隊(duì)尾。刪除一個(gè)元素稱為出隊(duì)，插入一個(gè)元素稱為入隊(duì)。和棧一樣，隊(duì)列也是一種操作受限制的線性表。隊(duì)列的特性：先進(jìn)先出 (FIFO，F(xiàn)irst-In-First-Out)。
原理
生活中的例子：排隊(duì)買東西。
實(shí)現(xiàn)
我們也可以使用 JS 來(lái)模擬隊(duì)列的功能。從數(shù)據(jù)存儲(chǔ)的方式來(lái)看，可以使用數(shù)組存儲(chǔ)數(shù)據(jù)，也可以使用鏈表存儲(chǔ)數(shù)據(jù)。因?yàn)閿?shù)組是最簡(jiǎn)單的方式，所以這里是用數(shù)組的方式來(lái)實(shí)現(xiàn)隊(duì)列。
隊(duì)列的操作包括入隊(duì)、出隊(duì)、清空隊(duì)列、獲取隊(duì)頭元素、獲取隊(duì)列的長(zhǎng)度等。
class Queue {
constructor() {
// 存儲(chǔ)數(shù)據(jù)
this.items = [];
}
enqueue(item) {
// 入隊(duì)
this.items.push(item);
}
dequeue() {
// 出隊(duì)
return this.items.shift();
}
head() {
// 獲取隊(duì)首的元素
return this.items[0];
}
tail() {
// 獲取隊(duì)尾的元素
return this.items[this.items.length - 1];
}
clear() {
// 清空隊(duì)列
this.items = [];
}
size() {
// 獲取隊(duì)列的長(zhǎng)度
return this.items.length;
}
isEmpty() {
// 判斷隊(duì)列是否為空
return this.items.length === 0;
}
}
應(yīng)用
約瑟夫環(huán)問(wèn)題
有一個(gè)數(shù)組存放了 100 個(gè)數(shù)據(jù) 0-99，要求每隔兩個(gè)數(shù)刪除一個(gè)數(shù)，到末尾時(shí)再循環(huán)至開(kāi)頭繼續(xù)進(jìn)行，求最后一個(gè)被刪除的數(shù)字。
思路分析
創(chuàng)建隊(duì)列，將 0 到 99 的數(shù)字入隊(duì)； 循環(huán)隊(duì)列，依次出列隊(duì)列中的數(shù)字，對(duì)當(dāng)前出隊(duì)的數(shù)字進(jìn)行計(jì)數(shù) index + 1； 判斷當(dāng)前出列的 index % 3 是否等于 0，如果不等于 0 則入隊(duì)； 直到隊(duì)列的長(zhǎng)度為 1，退出循環(huán)，返回隊(duì)列中的數(shù)字。
function ring(arr) {
const queue = new Queue();
arr.forEach(v => queue.enqueue(v));
let index = 0;
while(queue.size() > 1) {
const item = queue.dequeue();
if (++index % 3 !== 0) {
queue.enqueue(item);
}
}
return queue.head();
}
斐波那契數(shù)列
斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞推的方法定義：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。
function fiboSequence(num) {
if (num < 2) return num;
const queue = [];
queue.push(0);
queue.push(1);
for(let i = 2; i < num; i++) {
const len = queue.length;
queue.push(queue[len - 2] + queue[len - 1]);
}
return queue;
}
打印楊輝三角
思路分析：
通過(guò)觀察發(fā)現(xiàn)，三角中的每一行數(shù)據(jù)都依賴于上一行的數(shù)據(jù)； 我們首先創(chuàng)建隊(duì)列 queue，用于存儲(chǔ)每一行的數(shù)據(jù)，供下一行數(shù)據(jù)使用； 然后初始化第一行的數(shù)據(jù) 1 入隊(duì)，這里需要兩個(gè) for 循環(huán)嵌套，外層的 for 循環(huán)決定最終打印的總行數(shù)，內(nèi)層的 for 循環(huán)生成每行的數(shù)據(jù)； 在生成當(dāng)前行的數(shù)據(jù)時(shí)，將隊(duì)列中的數(shù)據(jù)源依次出隊(duì)，然后將新生成的數(shù)據(jù)入隊(duì)；并記錄當(dāng)前出隊(duì)的數(shù)據(jù)，供生成新數(shù)據(jù)使用。
function printYangHui(num) {
const queue = [];
// 存儲(chǔ)第一行數(shù)據(jù)
queue.push(1);
for(let i = 1; i <= num; i++) {
let rowArr = [];
// 填充空格
for(let j = 0; j < Math.floor((num - i) / 2); j++) {
rowArr.push('');
}
let prev = 0;
for(let j = 0; j < i; j++) {
const num = queue.shift();
queue.push(prev + num);
rowArr.push(num);
prev = num;
}
queue.push(1);
console.log(rowArr.join(' '));
}
}
printYangHui(10);
用途
實(shí)現(xiàn)洋蔥模型
完善代碼，實(shí)現(xiàn)輸出 1、2、3。
function createApp(){
return {
use(fn){},
run(){},
}
}
const app = createApp();
app.use((next)=>{
setTimeout(function(){
next();
})
console.log(new Date() ,'1');
})
app.use((next)=>{
console.log(new Date() ,'2');
next();
})
app.use((next)=>{
console.log(new Date() ,'3');
next();
})
app.run();
消息隊(duì)列
鏈表
由若干個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表，稱之為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
鏈表和數(shù)組的區(qū)別
鏈表和數(shù)組都可以存儲(chǔ)多個(gè)數(shù)據(jù)，那么鏈表和數(shù)組有什么區(qū)別呢？
數(shù)組需要一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)數(shù)據(jù)，對(duì)內(nèi)存的要求比較高。而鏈表卻相反，它并不需要一塊連續(xù)的內(nèi)存空間。鏈表是通過(guò)指針將一組零散的內(nèi)存塊串聯(lián)在一起。
相比數(shù)組，鏈表是一種稍微復(fù)雜一點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。兩者沒(méi)有好壞之分，各有各的優(yōu)缺點(diǎn)。
由于內(nèi)存存儲(chǔ)特性，數(shù)組可以實(shí)現(xiàn)快速的查找元素，但是在插入和刪除時(shí)就需要移動(dòng)大量的元素。原因就在于相鄰元素在內(nèi)存中的位置也是緊挨著的，中間沒(méi)有空隙，因此就無(wú)法快速添加元素。而當(dāng)刪除后，內(nèi)存空間中就會(huì)留出空隙，自然需要彌補(bǔ)。
分類
單向鏈表
雙向鏈表
單向循環(huán)鏈表
雙向循環(huán)鏈表
實(shí)現(xiàn)
const Node = function (data) {
this.data = data;
this.next = null;
}
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
node1.next = node2;
node2.next = node3;
應(yīng)用
環(huán)形鏈表
給定一個(gè)鏈表，如何判斷鏈表中是否有環(huán)？
思路分析：
首先創(chuàng)建兩個(gè)指針 1 和 2，同時(shí)指向這個(gè)鏈表的頭節(jié)點(diǎn)。然后開(kāi)始一個(gè)大循環(huán)，在循環(huán)體中，讓指針 1 每次向下移動(dòng)一個(gè)節(jié)點(diǎn)，讓指針 2 每次向下移動(dòng)兩個(gè)節(jié)點(diǎn)，然后比較兩個(gè)指針指向的節(jié)點(diǎn)是否相同。如果相同，則判斷出鏈表有環(huán)，如果不同，則繼續(xù)下一次循環(huán)。 例如鏈表 A->B->C->D->B->C->D，兩個(gè)指針最初都指向節(jié)點(diǎn) A，進(jìn)入第一輪循環(huán)，指針 1 移動(dòng)到了節(jié)點(diǎn) B，指針 2 移動(dòng)到了 C。第二輪循環(huán)，指針 1 移動(dòng)到了節(jié)點(diǎn) C，指針 2 移動(dòng)到了節(jié)點(diǎn) B。第三輪循環(huán)，指針 1 移動(dòng)到了節(jié)點(diǎn) D，指針 2 移動(dòng)到了節(jié)點(diǎn) D，此時(shí)兩指針指向同一節(jié)點(diǎn)，判斷出鏈表有環(huán)。 假設(shè)從鏈表頭節(jié)點(diǎn)到入環(huán)點(diǎn)的距離是 D，鏈表的環(huán)長(zhǎng)是 S。那么循環(huán)會(huì)進(jìn)行 S 次，可以簡(jiǎn)單理解為 O（N）。除了兩個(gè)指針以外，沒(méi)有使用任何額外存儲(chǔ)空間，所以空間復(fù)雜度是 O（1）。
const Node = function (data) {
this.data = data;
this.next = null;
}
const nodeA = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const nodeD = new Node('D');
const nodeE = new Node('E');
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeC;
function isCircularLinkedList(head) {
if (head === null || head.next === null) {
return false;
}
let point1 = head;
let point2 = head;
do {
point1 = point1.next;
point2 = point2.next && point2.next.next;
} while(point1 && point2 && point1 !== point2);
if (point1 === point2) {
return true;
}
return false;
}
console.log(isCircularLinkedList(nodeA));
相交鏈表
判斷兩個(gè)單鏈表是否相交并求出相交的第一結(jié)點(diǎn)。
思路分析：
兩個(gè)沒(méi)有環(huán)的鏈表如果是相交于某一結(jié)點(diǎn)，如上圖所示，這個(gè)結(jié)點(diǎn)后面都是共有的。所以如果兩個(gè)鏈表相交，那么兩個(gè)鏈表的尾結(jié)點(diǎn)的地址也是一樣的。程序?qū)崿F(xiàn)時(shí)分別遍歷兩個(gè)單鏈表，直到尾結(jié)點(diǎn)。判斷尾結(jié)點(diǎn)地址是否相等即可。時(shí)間復(fù)雜度為 O(L1+L2)。 如何找到第一個(gè)相交結(jié)點(diǎn)？判斷是否相交的時(shí)候，記錄下兩個(gè)鏈表的長(zhǎng)度，算出長(zhǎng)度差 len，接著先讓較長(zhǎng)的鏈表遍歷 len 個(gè)長(zhǎng)度，然后兩個(gè)鏈表同時(shí)遍歷，判斷是否相等，如果相等，就是第一個(gè)相交的結(jié)點(diǎn)。
function intersectNode(head1, head2) {
if (head1 && head2) {
// 計(jì)算鏈表的長(zhǎng)度
let len1 = 0, p = head1;
let len2 = 0, q = head2;
while(p.next) {
len1++;
p = p.next;
}
while(q.next) {
len2++;
q = q.next;
}
if (p === q) {
// p指向短鏈，q指向長(zhǎng)鏈
let len = 0;
if (len1 > len2) {
len = len1 - len2;
p = head2;
q = head1;
} else {
len = len2 - len1;
p = head1;
q = head2;
}
while(len > 0) {
len--;
q = q.next;
}
while(p && q && p !== q) {
p = p.next;
q = q.next;
}
return p;
}
}
return null;
}
const Node = function (data) {
this.data = data;
this.next = null;
}
const nodeA = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const node1 = new Node('1');
const node2 = new Node('2');
const node3 = new Node('3');
const nodeD4 = new Node('D4');
const nodeE5 = new Node('E5');
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD4;
node1.next = node2;
node2.next = node3;
node3.next = nodeD4;
nodeD4.next = nodeE5;
console.log(intersectNode(nodeA, node1));
回文鏈表
請(qǐng)判斷一個(gè)鏈表是否為回文鏈表。
思路分析：
從頭遍歷鏈表，同時(shí)正向和反向拼接每個(gè)鏈表的數(shù)據(jù)，最后比對(duì)正向和反向得到的字符串是否相等。如果相等則是回文鏈表；否則不是。
const Node = function (data) {
this.data = data;
this.next = null;
}
const node1 = new Node('A');
const node2 = new Node('B');
const node3 = new Node('C');
const node4 = new Node('C');
const node5 = new Node('B');
const node6 = new Node('A');
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
const isPalindrome = head => {
let a = '', b = '';
while(head !== null) {
a = a + head.data;
b = head.data + b;
head = head.next;
}
return a === b;
}
console.log(isPalindrome(node1));
用途
原型鏈 作用域鏈
樹(shù)
樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)，它是由 n(n>=1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。
分類
無(wú)序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間沒(méi)有順序關(guān)系，這種樹(shù)稱為無(wú)序樹(shù),也稱為自由樹(shù)。 有序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系，這種樹(shù)稱為有序樹(shù)。 二叉樹(shù)：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹(shù)的樹(shù)稱為二叉樹(shù)。 滿二叉樹(shù)：葉節(jié)點(diǎn)除外的所有節(jié)點(diǎn)均含有兩個(gè)子樹(shù)的樹(shù)被稱為滿二叉樹(shù)。 完全二叉樹(shù)：除最后一層外，所有層都是滿節(jié)點(diǎn)，且最后一層缺右邊連續(xù)節(jié)點(diǎn)的二叉樹(shù)稱為完全二叉樹(shù)（堆就是一個(gè)完全二叉樹(shù)）。 哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）：帶權(quán)路徑最短的二叉樹(shù)稱為哈夫曼樹(shù)或最優(yōu)二叉樹(shù)。
實(shí)現(xiàn)
// 二叉樹(shù)的實(shí)現(xiàn)
function Node(data) {
this.data = data;
this.left = null;
this.right = null;
}
const nodeA = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const nodeD = new Node('D');
const nodeE = new Node('E');
const nodeF = new Node('F');
const nodeG = new Node('G');
nodeA.left = nodeB;
nodeA.right = nodeC;
nodeB.left = nodeD;
nodeB.right = nodeE;
nodeC.left = nodeF;
nodeC.right = nodeG;
我們?nèi)粘９ぷ髦薪佑|到最多的是多叉樹(shù)。
遍歷
深度優(yōu)先遍歷
先序遍歷
先序遍歷（又稱先根遍歷）為 ABDECFG（根-左-右）。
中序遍歷
中序遍歷（又稱中根遍歷）為 DBEAFCG（左-根-右）（僅二叉樹(shù)有中序遍歷）。
后序遍歷
后序遍歷（又稱后根遍歷）為 DEBFGCA（左-右-根）。
廣度優(yōu)先遍歷
層序遍歷
層序遍歷為 ABCDEFG。
用途
樹(shù)的扁平化（展示 OCR 識(shí)別結(jié)果） 扁平化數(shù)組轉(zhuǎn)換成樹(shù)（標(biāo)簽樹(shù)）
圖
圖（Graph）結(jié)構(gòu)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，圖在實(shí)際生活中有很多例子，比如交通運(yùn)輸網(wǎng)，地鐵網(wǎng)絡(luò)，等等都可以抽象成圖結(jié)構(gòu)。圖結(jié)構(gòu)比樹(shù)結(jié)構(gòu)復(fù)雜的非線性結(jié)構(gòu)。
圖是由若干個(gè)頂點(diǎn)和邊組成。
分類
無(wú)向圖
如果一個(gè)圖結(jié)構(gòu)中，所有的邊都沒(méi)有方向性，那么這種圖便稱為無(wú)向圖。
有向圖
一個(gè)圖結(jié)構(gòu)中，邊是有方向性的，那么這種圖就稱為有向圖。
加權(quán)圖
如果給邊加上一個(gè)值表示權(quán)重，這種圖就是加權(quán)圖。
連通圖
如果圖中任意兩個(gè)節(jié)點(diǎn)都能找到路徑可以將它們進(jìn)行連接，則稱該圖為連通圖。
表示
圖有兩種表示方法：鄰接矩陣、鄰接鏈表。不同的場(chǎng)景及算法可能需要不同的圖表示方式，一般情況下當(dāng)結(jié)點(diǎn)數(shù)量非常龐大時(shí)，會(huì)造成矩陣非常稀疏，空間開(kāi)銷會(huì)較大，此時(shí)使用鄰接鏈表的表示方式會(huì)占用較少的空間。而如果是稠密矩陣或者需要快速判斷任意兩個(gè)結(jié)點(diǎn)是否有邊相連等情況，可能鄰接矩陣更合適。
鄰接矩陣
鄰接鏈表
遍歷
深度優(yōu)先遍歷 廣度優(yōu)先遍歷
用途
商品分類選擇
算法
LRU
LRU 是 Least Recently Used 的縮寫(xiě)，即最近最少使用，是一種常用的頁(yè)面置換算法，將最近最久未使用的頁(yè)面予以淘汰。
核心的思想就是“如果數(shù)據(jù)最近被訪問(wèn)，那么將來(lái)被訪問(wèn)的幾率也就更高”。
原理
實(shí)現(xiàn)
思路分析：
選擇合適的數(shù)據(jù)結(jié)構(gòu)。
哈希表：O(1) 級(jí)別的時(shí)間復(fù)雜度，適合數(shù)據(jù)查找。但是元素?zé)o序，沒(méi)辦法判斷元素訪問(wèn)的先后順序。 數(shù)組：元素的插入和刪除元素都是 O(n)。 單向鏈表：刪除節(jié)點(diǎn)需要訪問(wèn)前驅(qū)節(jié)點(diǎn)，需要花 O(n)從前遍歷查找。 雙向鏈表：結(jié)點(diǎn)有前驅(qū)指針，刪除和移動(dòng)節(jié)點(diǎn)都是指針的變動(dòng)，都是 O(1)。
結(jié)論：哈希表 + 雙向鏈表。
使用哈希表的目的就是快速訪問(wèn)到存儲(chǔ)在雙向鏈表中的數(shù)據(jù)，存儲(chǔ)雙向鏈表的 key 和節(jié)點(diǎn)的引用；使用雙向鏈表的目的就是快速進(jìn)行節(jié)點(diǎn)位置的移動(dòng)和刪除，存儲(chǔ) key 和對(duì)應(yīng)的數(shù)據(jù)。
設(shè)置虛擬節(jié)點(diǎn)，方便快速的訪問(wèn)頭尾節(jié)點(diǎn)。初始時(shí)沒(méi)有添加真實(shí)的節(jié)點(diǎn)，所以需要將虛擬節(jié)點(diǎn)的前驅(qū)指針和后繼指針指向自己。
get 方法的實(shí)現(xiàn)。
put 方法的實(shí)現(xiàn)。
寫(xiě)入新數(shù)據(jù)，需要先檢查一下當(dāng)前節(jié)點(diǎn)數(shù)量；如果節(jié)點(diǎn)數(shù)量達(dá)到容量的最大值，則需要先刪除鏈表尾部的節(jié)點(diǎn)，然后創(chuàng)建新的節(jié)點(diǎn)，添加到鏈表頭部，并寫(xiě)入到哈希表。 寫(xiě)入已存在的數(shù)據(jù)，則更新數(shù)據(jù)值，移動(dòng)節(jié)點(diǎn)位置到鏈表頭部。
function Node(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity; // 容量
this.hash = {}; // 哈希表
this.count = 0; // 當(dāng)前節(jié)點(diǎn)數(shù)量
this.virtualNode = new Node(); // 虛擬結(jié)點(diǎn)
// 相互引用
this.virtualNode.next = this.virtualNode;
this.virtualNode.prev = this.virtualNode;
}
get(key) {
const node = this.hash[key];
if (node) {
this.moveToHead(node);
return node.value;
}
}
put(key, value) {
const node = this.hash[key];
if (node) {
node.value = value;
this.moveToHead(node);
} else {
if (this.count === this.capacity) {
this.removeLRUItem();
}
const newNode = new Node(key, value);
this.hash[key] = newNode;
this.addToHead(newNode);
this.count++;
}
}
remove(key) {
const node = this.hash[key];
if (node) {
this.removeFromList(node);
Reflect.deleteProperty(this.hash, key);
this.count--;
}
}
isEmpty() {
return this.count === 0;
}
moveToHead(node) {
this.removeFromList(node);
this.addToHead(node);
}
removeFromList(node) {
const prevNode = node.prev;
const nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
node.prev = null;
node.next = null;
}
addToHead(node) {
const nextNode = this.virtualNode.next;
this.virtualNode.next = node;
nextNode.prev = node;
node.prev = this.virtualNode;
node.next = nextNode;
}
removeLRUItem() {
const tailNode = this.virtualNode.prev;
this.remove(tailNode.key);
}
}
const cache = new LRUCache(5);
console.log(cache.isEmpty());
cache.put('A', 'A');
cache.put('B', 'B');
cache.put('C', 'C');
cache.put('D', 'D');
cache.put('E', 'E');
console.log(cache.get('A'));
cache.put('F', 'F');
console.log(cache.get('B'));
console.log(cache.isEmpty());
cache.remove('E');
cache.remove('F');
cache.remove('A');
cache.remove('C');
cache.remove('D');
console.log(cache.isEmpty());
console.log(cache);
用途
歷史瀏覽記錄。 緩存淘汰策略。
我們來(lái)自字節(jié)跳動(dòng)，是旗下大力教育前端部門(mén)，負(fù)責(zé)字節(jié)跳動(dòng)教育全線產(chǎn)品前端開(kāi)發(fā)工作。
我們圍繞產(chǎn)品品質(zhì)提升、開(kāi)發(fā)效率、創(chuàng)意與前沿技術(shù)等方向沉淀與傳播專業(yè)知識(shí)及案例，為業(yè)界貢獻(xiàn)經(jīng)驗(yàn)價(jià)值。包括但不限于性能監(jiān)控、組件庫(kù)、多端技術(shù)、Serverless、可視化搭建、音視頻、人工智能、產(chǎn)品設(shè)計(jì)與營(yíng)銷等內(nèi)容。
歡迎感興趣的同學(xué)在評(píng)論區(qū)或使用內(nèi)推碼內(nèi)推到作者部門(mén)拍磚哦 ??
字節(jié)跳動(dòng)校/社招投遞鏈接: https://job.toutiao.com/s/eGrF9qQ