一、前言

首先，為什么我會(huì)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法呢，其實(shí)主要是有兩方面

第一，是我在今年的flag里明確說到我會(huì)學(xué)這個(gè)東西
第二，學(xué)了這些，對(duì)自己以后在工作或者面試也會(huì)帶來許多好處

然后，本文是最近學(xué)習(xí)的一個(gè)總結(jié)文章，文中有不足的地方也希望大家在評(píng)論區(qū)進(jìn)行指正，本文較長(zhǎng)，設(shè)有目錄?？芍苯油ㄟ^目錄跳轉(zhuǎn)閱讀。

文中的算法題，大部分都是leetcode中的，如不太理解題意，可直接去leetcode中找到對(duì)應(yīng)的題。

二、基本概念

常常聽到算法的時(shí)候，就會(huì)有人說到?時(shí)間復(fù)雜度，?空間復(fù)雜度。那么這倆玩意是啥呢，下面我就來一一解釋

1. 時(shí)間復(fù)雜度

其實(shí)就是一個(gè)函數(shù)，用大 O 表示，比如 O(1)、 O(n)...

它的作用就是用來定義描述算法的運(yùn)行時(shí)間

O(1)

????let?i?=?0
????i?+=?1
復(fù)制代碼

O(n)：?如果是 O(1) + O(n) 則還是 O(n)

????for?(let?i?=?0;?i?1)?{
??????console.log(i)
????}
復(fù)制代碼

O(n^2)：?O(n) * O(n), 也就是雙層循環(huán)，自此類推：O(n^3)...

????for?(let?i?=?0;?i?1)?{
??????for?(let?j?=?0;?j?1)?{
????????console.log(i,?j)
??????}
????}
復(fù)制代碼

O(logn)：?就是求 log 以 2 為底的多少次方等于 n

????//?這個(gè)例子就是求2的多少次方會(huì)大于i，然后就會(huì)結(jié)束循環(huán)。?這就是一個(gè)典型的 O(logn)
????let?i?=?1
????while?(i???????console.log(i)
??????i?*=?2
????}
復(fù)制代碼

2. 空間復(fù)雜度

和時(shí)間復(fù)雜度一樣，空間復(fù)雜度也是用大 O 表示，比如 O(1)、 O(n)...

它用來定義描述算法運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間大小

占用越少代碼寫的就越好

O(1)：?單個(gè)變量，所以占用永遠(yuǎn)是 O(1)

????let?i?=?0
????i?+=?1
復(fù)制代碼

O(n)：?聲明一個(gè)數(shù)組，添加 n 個(gè)值，相當(dāng)于占用了 n 個(gè)空間單元

????const?arr?=?[]
????for?(let?i?=?0;?i?1)?{
??????arr.push(i)
????}
復(fù)制代碼

O(n^2)：?類似一個(gè)矩陣的概念，就是二維數(shù)組的意思

????const?arr?=?[]
????for?(let?i?=?0;?i?1)?{
??????arr.push([])
??????for?(let?j?=?0;?j?1)?{
????????arr[i].push(j)
??????}
????}
復(fù)制代碼

三、數(shù)據(jù)結(jié)構(gòu)

1. 棧

一個(gè)后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)

按照常識(shí)理解就是有序的擠公交，最后上車的人會(huì)在門口，然后門口的人會(huì)最先下車

js中沒有棧的數(shù)據(jù)類型，但我們可以通過Array來模擬一個(gè)

const?stack?=?[];

stack.push(1);?//?入棧
stack.push(2);?//?入棧

const?item1?=?stack.pop();??//出棧的元素
復(fù)制代碼

1）十進(jìn)制轉(zhuǎn)二進(jìn)制

//?時(shí)間復(fù)雜度?O(n)?n為二進(jìn)制的長(zhǎng)度
//?空間復(fù)雜度?O(n)?n為二進(jìn)制的長(zhǎng)度
const?dec2bin?=?(dec)?=>?{
??//?創(chuàng)建一個(gè)字符串
??let?res?=?"";

??//?創(chuàng)建一個(gè)棧
??let?stack?=?[]

??//?遍歷數(shù)字?如果大于0?就可以繼續(xù)轉(zhuǎn)換2進(jìn)制
??while?(dec?>?0)?{
????//?將數(shù)字的余數(shù)入棧
????stack.push(dec?%?2);

????//?除以2
????dec?=?dec?>>?1;
??}

??//?取出棧中的數(shù)字
??while?(stack.length)?{
????res?+=?stack.pop();
??}

??//?返回這個(gè)字符串
??return?res;
};
復(fù)制代碼

2）判斷字符串的有效括號(hào)

//?時(shí)間復(fù)雜度O(n)?n為s的length
//?空間復(fù)雜度O(n)
const?isValid?=?(s)?=>?{

??//?如果長(zhǎng)度不等于2的倍數(shù)肯定不是一個(gè)有效的括號(hào)
??if?(s.length?%?2?===?1)?return?false;

??//?創(chuàng)建一個(gè)棧
??let?stack?=?[];

??//?遍歷字符串
??for?(let?i?=?0;?i?
????const?c?=?s[i];

????//?如果是左括號(hào)就入棧
????if?(c?===?'('?||?c?===?"{"?||?c?===?"[")?{
??????stack.push(c);
????}?else?{

??????//?如果不是左括號(hào)?且棧為空?肯定不是一個(gè)有效的括號(hào)?返回false
??????if?(!stack.length)?return?false

??????//?拿到最后一個(gè)左括號(hào)
??????const?top?=?stack[stack.length?-?1];

??????//?如果是右括號(hào)和左括號(hào)能匹配就出棧
??????if?((top?===?"("?&&?c?===?")")?||?(top?===?"{"?&&?c?===?"}")?||?(top?===?"["?&&?c?===?"]"))?{
????????stack.pop();
??????}?else?{

????????//?否則就不是一個(gè)有效的括號(hào)
????????return?false
??????}
????}

??}
??return?stack.length?===?0;
};
復(fù)制代碼

2. 隊(duì)列

和棧相反?先進(jìn)先出的一個(gè)數(shù)據(jù)結(jié)構(gòu)

按照常識(shí)理解就是銀行排號(hào)辦理業(yè)務(wù),?先去領(lǐng)號(hào)排隊(duì)的人,?先辦理業(yè)務(wù)

同樣 js中沒有棧的數(shù)據(jù)類型，但我們可以通過?Array來模擬一個(gè)

const?queue?=?[];

//?入隊(duì)
queue.push(1);
queue.push(2);

//?出隊(duì)
const?first?=?queue.shift();
const?end?=?queue.shift();
復(fù)制代碼

1）最近的請(qǐng)求次數(shù)

var?RecentCounter?=?function?()?{
??//?初始化隊(duì)列
??this.q?=?[];
};

//?輸入?inputs?=?[[],[1],[100],[3001],[3002]]?請(qǐng)求間隔為?3000ms
//?輸出?outputs?=?[null,1,2,3,3]???

//?時(shí)間復(fù)雜度?O(n)?n為剔出老請(qǐng)求的長(zhǎng)度
//?空間復(fù)雜度?O(n)?n為最近請(qǐng)求的次數(shù)
RecentCounter.prototype.ping?=?function?(t)?{
??//?如果傳入的時(shí)間小于等于最近請(qǐng)求的時(shí)間，則直接返回0
??if?(!t)?return?null

??//?將傳入的時(shí)間放入隊(duì)列
??this.q.push(t);

??//?如果隊(duì)頭小于?t?-?3000?則剔除隊(duì)頭
??while?(this.q[0]?3000)?{
????this.q.shift();
??}

??//?返回最近請(qǐng)求的次數(shù)
??return?this.q.length;
};
復(fù)制代碼

3. 鏈表

多個(gè)元素組成的列表，元素存儲(chǔ)不連續(xù)，通過 next 指針來鏈接, 最底層為 null

就類似于?父輩鏈接關(guān)系?吧，比如：你爺爺?shù)膬鹤邮悄惆职?，你爸爸的兒子是你，而你假如目前還沒有結(jié)婚生子，那你就暫時(shí)木有兒子

js中類似于鏈表的典型就是原型鏈, 但是js中沒有鏈表這種數(shù)據(jù)結(jié)構(gòu)，我們可以通過一個(gè)object來模擬鏈表

const?a?=?{
??val:?"a"
}

const?b?=?{
??val:?"b"
}

const?c?=?{
??val:?"c"
}

const?d?=?{
??val:?"d"
}

a.next?=?b;
b.next?=?c;
c.next?=?d;

//?const?linkList?=?{
//????val:?"a",
//????next:?{
//????????val:?"b",
//????????next:?{
//????????????val:?"c",
//????????????next:?{
//????????????????val:?"d",
//????????????????next:?null
//????????????}
//????????}
//????}
//?}

//?遍歷鏈表
let?p?=?a;
while?(p)?{
??console.log(p.val);
??p?=?p.next;
}

//?插入
const?e?=?{?val:?'e'?};
c.next?=?e;
e.next?=?d;


//?刪除
c.next?=?d;
復(fù)制代碼

1）手寫instanceOf

const?myInstanceOf?=?(A,?B)?=>?{
??//?聲明一個(gè)指針
??let?p?=?A;
??
??//?遍歷這個(gè)鏈表
??while?(p)?{
????if?(p?===?B.prototype)?return?true;
????p?=?p.__proto__;
??}

??return?false
}

myInstanceOf([],?Object)
復(fù)制代碼

2）刪除鏈表中的節(jié)點(diǎn)

//?時(shí)間復(fù)雜和空間復(fù)雜度都是?O(1)
const?deleteNode?=?(node)?=>?{
??//?把當(dāng)前鏈表的指針指向下下個(gè)鏈表的值就可以了
??node.val?=?node.next.val;
??node.next?=?node.next.next
}
復(fù)制代碼

3）刪除排序鏈表中的重復(fù)元素

//?1?->?1?->?2?->?3?->?3?
//?1?->?2?->?3?->?null

//?時(shí)間復(fù)雜度?O(n)?n為鏈表的長(zhǎng)度
//?空間復(fù)雜度?O(1)
const?deleteDuplicates?=?(head)?=>?{

??//?創(chuàng)建一個(gè)指針
??let?p?=?head;

??//?遍歷鏈表
??while?(p?&&?p.next)?{

????//?如果當(dāng)前節(jié)點(diǎn)的值等于下一個(gè)節(jié)點(diǎn)的值
????if?(p.val?===?p.next.val)?{

??????//?刪除下一個(gè)節(jié)點(diǎn)
??????p.next?=?p.next.next
????}?else?{

??????//?否則繼續(xù)遍歷
??????p?=?p.next
????}
??}

??//??最后返回原來鏈表
??return?head
}
復(fù)制代碼

4）反轉(zhuǎn)鏈表

//?1?->?2?->?3?->?4?->?5?->?null
//?5?->?4?->?3?->?2?->?1?->?null

//?時(shí)間復(fù)雜度?O(n)?n為鏈表的長(zhǎng)度
//?空間復(fù)雜度?O(1)
var?reverseList?=?function?(head)?{

??//?創(chuàng)建一個(gè)指針
??let?p1?=?head;

??//?創(chuàng)建一個(gè)新指針
??let?p2?=?null;

??//?遍歷鏈表
??while?(p1)?{

????//?創(chuàng)建一個(gè)臨時(shí)變量
????const?tmp?=?p1.next;

????//?將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向新鏈表
????p1.next?=?p2;

????//?將新鏈表指向當(dāng)前節(jié)點(diǎn)
????p2?=?p1;

????//?將當(dāng)前節(jié)點(diǎn)指向臨時(shí)變量
????p1?=?tmp;
??}

??//?最后返回新的這個(gè)鏈表
??return?p2;
}

reverseList(list
復(fù)制代碼

4. 集合

一種無序且唯一的數(shù)據(jù)結(jié)構(gòu)

ES6中有集合?Set類型

const?arr?=?[1,?1,?1,?2,?2,?3];

//?去重
const?arr2?=?[...new?Set(arr)];

//?判斷元素是否在集合中
const?set?=?new?Set(arr);
set.has(2)?//?true

//??交集
const?set2?=?new?Set([1,?2]);
const?set3?=?new?Set([...set].filter(item?=>?set.has(item)));
復(fù)制代碼

1）去重

具體代碼在上面介紹中有寫過，就不再重寫了

2）兩個(gè)數(shù)組的交集

//?時(shí)間復(fù)雜度?O(n^2)?n為數(shù)組長(zhǎng)度
//?空間復(fù)雜度?O(n)??n為去重后的數(shù)組長(zhǎng)度
const?intersection?=?(nums1,?nums2)?=>?{

??//?通過數(shù)組的filter選出交集
??//?然后通過?Set集合?去重?并生成數(shù)組
??return?[...new?Set(nums1.filter(item?=>?nums2.includes(item)))];
}
復(fù)制代碼

5. 字典

與集合類似，一個(gè)存儲(chǔ)唯一值的結(jié)構(gòu),以鍵值對(duì)的形式存儲(chǔ)

js中有字典數(shù)據(jù)結(jié)構(gòu) 就是?Map 類型

1）兩數(shù)之和

//?nums?=?[2,?7,?11,?15]?target?=?9

//?時(shí)間復(fù)雜度O(n)?n為nums的length
//?空間復(fù)雜度O(n)
var?twoSum?=?function?(nums,?target)?{

??//?建立一個(gè)字典數(shù)據(jù)結(jié)構(gòu)來保存需要的值
??const?map?=?new?Map();
??for?(let?i?=?0;?i???
????//?獲取當(dāng)前的值，和需要的值
????const?n?=?nums[i];
????const?n2?=?target?-?n;
????
????//?如字典中有需要的值，就匹配成功
????if?(map.has(n2))?{
??????return?[map.get(n2),?i];
????}?else?{
????
????//?如沒有，則把需要的值添加到字典中
??????map.set(n,?i);
????}
??}
};
復(fù)制代碼

2）兩個(gè)數(shù)組的交集

//?nums1?=?[1,2,2,1],?nums2?=?[2,2]
//?輸出：[2]

//?時(shí)間復(fù)雜度?O(m?+?n)?m為nums1長(zhǎng)度?n為nums2長(zhǎng)度
//?空間復(fù)雜度?O(m)?m為交集的數(shù)組長(zhǎng)度
const?intersection?=?(nums1,?nums2)?=>?{
??//?創(chuàng)建一個(gè)字典
??const?map?=?new?Map();

??//?將數(shù)組1中的數(shù)字放入字典
??nums1.forEach(n?=>?map.set(n,?true));

??//?創(chuàng)建一個(gè)新數(shù)組
??const?res?=?[];

??//?將數(shù)組2遍歷?并判斷是否在字典中
??nums2.forEach(n?=>?{
????if?(map.has(n))?{
??????res.push(n);

??????//?如果在字典中，則刪除該數(shù)字
??????map.delete(n);
????}
??})

??return?res;
};
復(fù)制代碼

3）字符的有效的括號(hào)

//?用字典優(yōu)化

//?時(shí)間復(fù)雜度?O(n)?n為s的字符長(zhǎng)度
//?空間復(fù)雜度?O(n)?
const?isValid?=?(s)?=>?{

??//?如果長(zhǎng)度不等于2的倍數(shù)肯定不是一個(gè)有效的括號(hào)
??if?(s.length?%?2?!==?0)?return?false

??//?創(chuàng)建一個(gè)字典
??const?map?=?new?Map();
??map.set('(',?')');
??map.set('{',?'}');
??map.set('[',?']');

??//?創(chuàng)建一個(gè)棧
??const?stack?=?[];

??//?遍歷字符串
??for?(let?i?=?0;?i?
????//?取出字符
????const?c?=?s[i];

????//?如果是左括號(hào)就入棧
????if?(map.has(c))?{
??????stack.push(c)
????}?else?{

??????//?取出棧頂
??????const?t?=?stack[stack.length?-?1];

??????//?如果字典中有這個(gè)值?就出棧
??????if?(map.get(t)?===?c)?{
????????stack.pop();
??????}?else?{

????????//?否則就不是一個(gè)有效的括號(hào)
????????return?false
??????}

????}

??}

??return?stack.length?===?0;
};
復(fù)制代碼

4）最小覆蓋字串

//?輸入：s =?"ADOBECODEBANC", t =?"ABC"
//?輸出："BANC"


//?時(shí)間復(fù)雜度?O(m?+?n)?m是t的長(zhǎng)度?n是s的長(zhǎng)度
//?空間復(fù)雜度?O(k)?k是字符串中不重復(fù)字符的個(gè)數(shù)
var?minWindow?=?function?(s,?t)?{
??//?定義雙指針維護(hù)一個(gè)滑動(dòng)窗口
??let?l?=?0;
??let?r?=?0;

??//?建立一個(gè)字典
??const?need?=?new?Map();

??//??遍歷t
??for?(const?c?of?t)?{
????need.set(c,?need.has(c)???need.get(c)?+?1?:?1)
??}

??let?needType?=?need.size

??//?記錄最小子串
??let?res?=?""

??//?移動(dòng)右指針
??while?(r???
????//?獲取當(dāng)前字符
????const?c?=?s[r];

????//?如果字典里有這個(gè)字符
????if?(need.has(c))?{
????
??????//?減少字典里面的次數(shù)
??????need.set(c,?need.get(c)?-?1);

??????//?減少需要的值
??????if?(need.get(c)?===?0)?needType?-=?1;
????}

????//?如果字典中所有的值都為0了?就說明找到了一個(gè)最小子串
????while?(needType?===?0)?{
????
??????//?取出當(dāng)前符合要求的子串
??????const?newRes?=?s.substring(l,?r?+?1)

??????//?如果當(dāng)前子串是小于上次的子串就進(jìn)行覆蓋
??????if?(!res?||?newRes.length?
??????//?獲取左指針的字符
??????const?c2?=?s[l];

??????//?如果字典里有這個(gè)字符
??????if?(need.has(c2))?{
????????//?增加字典里面的次數(shù)
????????need.set(c2,?need.get(c2)?+?1);

????????//?增加需要的值
????????if?(need.get(c2)?===?1)?needType?+=?1;
??????}
??????l?+=?1;
????}
????r?+=?1;
??}
??return?res
};
復(fù)制代碼

6. 樹

一種分層數(shù)據(jù)的抽象模型，比如DOM樹、樹形控件等

js中沒有樹但是可以用?Object 和 Array 構(gòu)建樹

1）普通樹

//?這就是一個(gè)常見的普通樹形結(jié)構(gòu)
const?tree?=?{
??val:?"a",
??children:?[
????{
??????val:?"b",
??????children:?[
????????{
??????????val:?"d",
??????????children:?[],
????????},
????????{
??????????val:?"e",
??????????children:?[],
????????}
??????],
????},
????{
??????val:?"c",
??????children:?[
????????{
??????????val:?"f",
??????????children:?[],
????????},
????????{
??????????val:?"g",
??????????children:?[],
????????}
??????],
????}
??],
}
復(fù)制代碼

> 深度優(yōu)先遍歷

盡可能深的搜索樹的分支,就比如遇到一個(gè)節(jié)點(diǎn)就會(huì)直接去遍歷他的子節(jié)點(diǎn)，不會(huì)立刻去遍歷他的兄弟節(jié)點(diǎn)
口訣：
訪問根節(jié)點(diǎn)
對(duì)根節(jié)點(diǎn)的 children 挨個(gè)進(jìn)行深度優(yōu)先遍歷

//?深度優(yōu)先遍歷
const?dfs?=?(tree)?=>?{
??tree.children.forEach(dfs)
};
復(fù)制代碼

> 廣度優(yōu)先遍歷

先訪問離根節(jié)點(diǎn)最近的節(jié)點(diǎn), 如果有兄弟節(jié)點(diǎn)就會(huì)先遍歷兄弟節(jié)點(diǎn)，再去遍歷自己的子節(jié)點(diǎn)
口訣
新建一個(gè)隊(duì)列并把根節(jié)點(diǎn)入隊(duì)
把隊(duì)頭出隊(duì)并訪問
把隊(duì)頭的children挨個(gè)入隊(duì)
重復(fù)第二、三步直到隊(duì)列為空

//?廣度優(yōu)先遍歷
const?bfs?=?(tree)?=>?{
??const?q?=?[tree];

??while?(q.length?>?0)?{
????const?n?=?q.shift()
????console.log(n.val);
????n.children.forEach(c?=>?q.push(c))
??}
};
復(fù)制代碼

2）二叉樹

樹中每個(gè)節(jié)點(diǎn)?最多只能有兩個(gè)子節(jié)點(diǎn)

?const?bt?=?{
??val:?1,
??left:?{
????val:?2,
????left:?null,
????right:?null
??},
??right:?{
????val:?3,
????left:?{
??????val:?4,
??????left:?null,
??????right:?null
????},
????right:?{
??????val:?5,
??????left:?null,
??????right:?null
????}
??}
}
復(fù)制代碼

> 二叉樹的先序遍歷

訪問根節(jié)點(diǎn)
對(duì)根節(jié)點(diǎn)的左子樹進(jìn)行先序遍歷
對(duì)根節(jié)點(diǎn)的右子樹進(jìn)行先序遍歷

//?先序遍歷?遞歸
const?preOrder?=?(tree)?=>?{
??if?(!tree)?return

??console.log(tree.val);

??preOrder(tree.left);
??preOrder(tree.right);
}



//?先序遍歷?非遞歸
const?preOrder2?=?(tree)?=>?{
??if?(!tree)?return

??//?新建一個(gè)棧
??const?stack?=?[tree];

??while?(stack.length?>?0)?{
????const?n?=?stack.pop();
????console.log(n.val);

????//?負(fù)負(fù)為正
????if?(n.right)?stack.push(n.right);
????if?(n.left)?stack.push(n.left);

??}
}
復(fù)制代碼

> 二叉樹的中序遍歷

對(duì)根節(jié)點(diǎn)的左子樹進(jìn)行中序遍歷
訪問根節(jié)點(diǎn)
對(duì)根節(jié)點(diǎn)的右子樹進(jìn)行中序遍歷

//?中序遍歷?遞歸
const?inOrder?=?(tree)?=>?{
??if?(!tree)?return;
??inOrder(tree.left)
??console.log(tree.val);
??inOrder(tree.right)
}


//?中序遍歷?非遞歸
const?inOrder2?=?(tree)?=>?{
??if?(!tree)?return;

??//?新建一個(gè)棧
??const?stack?=?[];

??//?先遍歷所有的左節(jié)點(diǎn)
??let?p?=?tree;
??while?(stack.length?||?p)?{

????while?(p)?{
??????stack.push(p)
??????p?=?p.left
????}

????const?n?=?stack.pop();
????console.log(n.val);

????p?=?n.right;
??}
}
復(fù)制代碼

> 二叉樹的后序遍歷

對(duì)根節(jié)點(diǎn)的左子樹進(jìn)行后序遍歷
對(duì)根節(jié)點(diǎn)的右子樹進(jìn)行后序遍歷
訪問根節(jié)點(diǎn)

//?后序遍歷?遞歸
const?postOrder?=?(tree)?=>?{
??if?(!tree)?return

??postOrder(tree.left)
??postOrder(tree.right)
??console.log(tree.val)
};



//?后序遍歷?非遞歸
const?postOrder2?=?(tree)?=>?{
??if?(!tree)?return

??const?stack?=?[tree];
??const?outputStack?=?[];

??while?(stack.length)?{
????const?n?=?stack.pop();
????outputStack.push(n)
????//?負(fù)負(fù)為正
????if?(n.left)?stack.push(n.left);
????if?(n.right)?stack.push(n.right);

??}

??while?(outputStack.length)?{
????const?n?=?outputStack.pop();
????console.log(n.val);
??}
};
復(fù)制代碼

> 二叉樹的最大深度

//?給一個(gè)二叉樹，需要你找出其最大的深度，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的距離

//?時(shí)間復(fù)雜度?O(n)?n為樹的節(jié)點(diǎn)數(shù)
//?空間復(fù)雜度?有一個(gè)遞歸調(diào)用的棧?所以為?O(n)?n也是為二叉樹的最大深度
var?maxDepth?=?function?(root)?{
??let?res?=?0;
????
??//?使用深度優(yōu)先遍歷
??const?dfs?=?(n,?l)?=>?{
????if?(!n)?return;
????if?(!n.left?&&?!n.right)?{
?????//?沒有葉子節(jié)點(diǎn)就把深度數(shù)量更新
??????res?=?Math.max(res,?l);
????}
????dfs(n.left,?l?+?1)
????dfs(n.right,?l?+?1)
??}

??dfs(root,?1)

??return?res
}
復(fù)制代碼

> 二叉樹的最小深度

//?給一個(gè)二叉樹，需要你找出其最小的深度，?從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的距離


//?時(shí)間復(fù)雜度O(n)?n是樹的節(jié)點(diǎn)數(shù)量
//?空間復(fù)雜度O(n)?n是樹的節(jié)點(diǎn)數(shù)量
var?minDepth?=?function?(root)?{
??if?(!root)?return?0
??
??//?使用廣度優(yōu)先遍歷
??const?q?=?[[root,?1]];

??while?(q.length)?{
????//?取出當(dāng)前節(jié)點(diǎn)
????const?[n,?l]?=?q.shift();
????
????//?如果是葉子節(jié)點(diǎn)直接返回深度就可
????if?(!n.left?&&?!n.right)?return?l
????if?(n.left)?q.push([n.left,?l?+?1]);
????if?(n.right)?q.push([n.right,?l?+?1]);
??}

}
復(fù)制代碼

> 二叉樹的層序遍歷

//?需要返回?[[1],?[2,3],?[4,5]]


//?時(shí)間復(fù)雜度?O(n)?n為樹的節(jié)點(diǎn)數(shù)
//?空間復(fù)雜度?O(n)?
var?levelOrder?=?function?(root)?{
??if?(!root)?return?[]
???
??//?廣度優(yōu)先遍歷
??const?q?=?[root];
??const?res?=?[];
??while?(q.length)?{
????let?len?=?q.length

????res.push([])
????
????//?循環(huán)每層的節(jié)點(diǎn)數(shù)量次
????while?(len--)?{
??????const?n?=?q.shift();
??????
??????res[res.length?-?1].push(n.val)
??????
??????if?(n.left)?q.push(n.left);
??????if?(n.right)?q.push(n.right);
????}

??}

??return?res
};
復(fù)制代碼

7. 圖

圖是網(wǎng)絡(luò)結(jié)構(gòu)的抽象模型, 是一組由邊連接的節(jié)點(diǎn)

js中可以利用Object和Array構(gòu)建圖

//?上圖可以表示為
const?graph?=?{
??0:?[1,?2],
??1:?[2],
??2:?[0,?3],
??3:?[3]
}


//?深度優(yōu)先遍歷，對(duì)根節(jié)點(diǎn)沒訪問過的相鄰節(jié)點(diǎn)挨個(gè)進(jìn)行遍歷
{
????//?記錄節(jié)點(diǎn)是否訪問過
????const?visited?=?new?Set();
????const?dfs?=?(n)?=>?{
??????visited.add(n);
??????
??????//?遍歷相鄰節(jié)點(diǎn)
??????graph[n].forEach(c?=>?{
????????//?沒訪問過才可以，進(jìn)行遞歸訪問
????????if(!visited.has(c)){
??????????dfs(c)
????????}
??????});
????}
????
????//?從2開始進(jìn)行遍歷
????dfs(2)
}


//?廣度優(yōu)先遍歷?
{
????const?visited?=?new?Set();
????//?新建一個(gè)隊(duì)列，?根節(jié)點(diǎn)入隊(duì)，?設(shè)2為根節(jié)點(diǎn)
????const?q?=?[2];
????visited.add(2)
????while?(q.length)?{
????
??????//?隊(duì)頭出隊(duì)，并訪問
??????const?n?=?q.shift();
??????console.log(n);
??????graph[n].forEach(c?=>?{
??????
????????//?對(duì)沒訪問過的相鄰節(jié)點(diǎn)入隊(duì)
????????if?(!visited.has(c))?{
??????????q.push(c)
??????????visited.add(c)
????????}
??????})
????}
}
復(fù)制代碼

1）有效數(shù)字

//?生成數(shù)字關(guān)系圖?只有狀態(tài)為?3?5?6?的時(shí)候才為一個(gè)數(shù)字
const?graph?=?{
??0:?{?'blank':?0,?'sign':?1,?".":?2,?"digit":?6?},
??1:?{?"digit":?6,?".":?2?},
??2:?{?"digit":?3?},
??3:?{?"digit":?3,?"e":?4?},
??4:?{?"digit":?5,?"sign":?7?},
??5:?{?"digit":?5?},
??6:?{?"digit":?6,?".":?3,?"e":?4?},
??7:?{?"digit":?5?},
}


//?時(shí)間復(fù)雜度?O(n)?n是字符串長(zhǎng)度
//?空間復(fù)雜度?O(1)?
var?isNumber?=?function?(s)?{

??//?記錄狀態(tài)
??let?state?=?0;

??//?遍歷字符串
??for?(c?of?s.trim())?{
????//?把字符進(jìn)行轉(zhuǎn)換
????if?(c?>=?'0'?&&?c?<=?'9')?{
??????c?=?'digit';
????}?else?if?(c?===?"?")?{
??????c?=?'blank';
????}?else?if?(c?===?"+"?||?c?===?"-")?{
??????c?=?"sign";
????}?else?if?(c?===?"E"?||?c?===?"e")?{
??????c?=?"e";
????}

????//?開始尋找圖
????state?=?graph[state][c];

????//?如果最后是undefined就是錯(cuò)誤
????if?(state?===?undefined)?return?false
??}

??//?判斷最后的結(jié)果是不是合法的數(shù)字
??if?(state?===?3?||?state?===?5?||?state?===?6)?return?true
??return?false
};?
復(fù)制代碼

8. 堆

一種特殊的完全二叉樹, 所有的節(jié)點(diǎn)都大于等于最大堆,或者小于等于最小堆的子節(jié)點(diǎn)

js通常使用數(shù)組來表示堆

左側(cè)子節(jié)點(diǎn)的位置是?2*index + 1
右側(cè)子節(jié)點(diǎn)的位置是?2*index + 2
父節(jié)點(diǎn)的位置是?(index - 1) / 2?, 取余數(shù)

2）JS實(shí)現(xiàn)一個(gè)最小堆

//?js實(shí)現(xiàn)最小堆類
class?MinHeap?{
??constructor()?{
????//?元素容器
????this.heap?=?[];
??}

??//?交換節(jié)點(diǎn)的值
??swap(i1,?i2)?{
????[this.heap[i1],?this.heap[i2]]?=?[this.heap[i2],?this.heap[i1]]
??}

??//??獲取父節(jié)點(diǎn)
??getParentIndex(index)?{
????//?除以二，?取余數(shù)
????return?(index?-?1)?>>?1;
??}

??//?獲取左側(cè)節(jié)點(diǎn)索引
??getLeftIndex(i)?{
????return?(i?<1)?+?1;
??}

??//?獲取右側(cè)節(jié)點(diǎn)索引
??getRightIndex(i)?{
????return?(i?<1)?+?2;
??}


??//?上移
??shiftUp(index)?{
????if?(index?==?0)?return;

????//?獲取父節(jié)點(diǎn)
????const?parentIndex?=?this.getParentIndex(index);

????//?如果父節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)的值?就需要進(jìn)行交換
????if?(this.heap[parentIndex]?>?this.heap[index])?{
??????this.swap(parentIndex,?index);

??????//?然后繼續(xù)上移
??????this.shiftUp(parentIndex);
????}
??}

??//?下移
??shiftDown(index)?{
????//?獲取左右節(jié)點(diǎn)索引
????const?leftIndex?=?this.getLeftIndex(index);
????const?rightIndex?=?this.getRightIndex(index);

????//?如果左子節(jié)點(diǎn)小于當(dāng)前的值
????if?(this.heap[leftIndex]?this.heap[index])?{

??????//?進(jìn)行節(jié)點(diǎn)交換
??????this.swap(leftIndex,?index);

??????//?繼續(xù)進(jìn)行下移
??????this.shiftDown(leftIndex)
????}

????//?如果右側(cè)節(jié)點(diǎn)小于當(dāng)前的值
????if?(this.heap[rightIndex]?this.heap[index])?{
??????this.swap(rightIndex,?index);
??????this.shiftDown(rightIndex)
????}
??}

??//?插入元素
??insert(value)?{
????//?插入到堆的底部
????this.heap.push(value);

????//?然后上移：?將這個(gè)值和它的父節(jié)點(diǎn)進(jìn)行交換，知道父節(jié)點(diǎn)小于等于這個(gè)插入的值
????this.shiftUp(this.heap.length?-?1)
??}

??//?刪除堆項(xiàng)
??pop()?{

????//?把數(shù)組最后一位?轉(zhuǎn)移到數(shù)組頭部
????this.heap[0]?=?this.heap.pop();

????//?進(jìn)行下移操作
????this.shiftDown(0);
??}

??//?獲取堆頂元素
??peek()?{
????return?this.heap[0]
??}

??//?獲取堆大小
??size()?{
????return?this.heap.length
??}

}
復(fù)制代碼

2）數(shù)組中的第k個(gè)最大元素

//?輸入?[3,2,1,5,6,4]?和?k?=?2
//?輸出?5

//?時(shí)間復(fù)雜度?O(n?*?logK)?K就是堆的大小
//?空間復(fù)雜度?O(K)?K是參數(shù)k
var?findKthLargest?=?function?(nums,?k)?{

??//?使用上面js實(shí)現(xiàn)的最小堆類，來構(gòu)建一個(gè)最小堆
??const?h?=?new?MinHeap();
??
??//?遍歷數(shù)組
??nums.forEach(n?=>?{
????
????//?把數(shù)組中的值依次插入到堆里
????h.insert(n);
????
????if?(h.size()?>?k)?{
??????//?進(jìn)行優(yōu)勝劣汰
??????h.pop();
????}
??})

??return?h.peek()
};
復(fù)制代碼

3）前 K 個(gè)高頻元素

//?nums?=?[1,1,1,2,2,3],?k?=?2
//?輸出:?[1,2]


//?時(shí)間復(fù)雜度?O(n?*?logK)?
//?空間復(fù)雜度?O(k)
var?topKFrequent?=?function?(nums,?k)?{

??//?統(tǒng)計(jì)每個(gè)元素出現(xiàn)的頻率
??const?map?=?new?Map();

??//?遍歷數(shù)組?建立映射關(guān)系
??nums.forEach(n?=>?{
????map.set(n,?map.has(n)???map.get(n)?+?1?:?1);
??})

??//?建立最小堆
??const?h?=?new?MinHeap();

??//?遍歷映射關(guān)系
??map.forEach((value,?key)?=>?{

????//?由于插入的元素結(jié)構(gòu)發(fā)生了變化，所以需要對(duì)?最小堆的類?進(jìn)行改造一下,改造的方法我會(huì)寫到最后
????h.insert({?value,?key?})
????if?(h.size()?>?k)?{
??????h.pop()
????}
??})
??return?h.heap.map(item?=>?item.key)
};

//?改造上移和下移操作即可
//?shiftUp(index)?{
//???if?(index?==?0)?return;
//???const?parentIndex?=?this.getParentIndex(index);
//???if?(this.heap[parentIndex]?&&?this.heap[parentIndex].value?>?this.heap[index].value)?{
//?????this.swap(parentIndex,?index);
//?????this.shiftUp(parentIndex);
//???}
//?}
//?shiftDown(index)?{
//???const?leftIndex?=?this.getLeftIndex(index);
//???const?rightIndex?=?this.getRightIndex(index);

//???if?(this.heap[leftIndex]?&&?this.heap[leftIndex].value?
//?????this.swap(leftIndex,?index);
//?????this.shiftDown(leftIndex)
//???}

//???if?(this.heap[rightIndex]?&&?this.heap[rightIndex].value?
//?????this.swap(rightIndex,?index);
//?????this.shiftDown(rightIndex)
//???}
//?}
復(fù)制代碼

四、常見算法及算法思想

1. 排序

把某個(gè)亂序的數(shù)組變成升序序或者降序的數(shù)組， js比較常用sort方法進(jìn)行排序

1）冒泡排序

比較所有相鄰元素，如果第一個(gè)比第二個(gè)大就交換他們
執(zhí)行一次后可以保證最后一個(gè)數(shù)字是最大的
重復(fù)執(zhí)行 n-1 次，就可以完成排序

//?時(shí)間復(fù)雜度?O(n?^?2)?n為數(shù)組長(zhǎng)度
//?空間復(fù)雜度?O(1)
Array.prototype.bubbleSort?=?function?()?{
??for?(i?=?0;?i?this.length?-?1;?i++)?{
????for?(let?j?=?0;?j?this.length?-?1?-?i;?j++)?{
??????if?(this[j]?>?this[j?+?1])?{
??????
????????//?交換數(shù)據(jù)
????????[this[j],?this[j?+?1]]?=?[this[j?+?1],?this[j]];
??????}
????}
??}
}
復(fù)制代碼

2）選擇排序

找到數(shù)組中最小的值,選中它并放到第一位
接著找到數(shù)組中第二小的值,選中它并放到第二位
重復(fù)上述步驟執(zhí)行 n-1 次

//?時(shí)間復(fù)雜度：O(n ^ 2) n為數(shù)組長(zhǎng)度
//?空間復(fù)雜度：O(1)
Array.prototype.selectionSort?=?function?()?{
??for?(let?i?=?0;?i?this.length?-?1;?i++)?{
????let?indexMin?=?i;

????for?(let?j?=?i;?j?this.length;?j++)?{

??????//?如果當(dāng)前這個(gè)元素?小于最小值的下標(biāo)?就更新最小值的下標(biāo)
??????if?(this[j]?this[indexMin])?{
????????indexMin?=?j;
??????}
????}

????//?避免自己和自己進(jìn)行交換
????if?(indexMin?!==?i)?{

??????//?進(jìn)行交換數(shù)據(jù)
??????[this[i],?this[indexMin]]?=?[this[indexMin],?this[i]];
????}
??}
}
復(fù)制代碼

3）插入排序

從第二個(gè)數(shù)，開始往前比較
如它大就往后排
以此類推進(jìn)行到最后一個(gè)數(shù)

//?時(shí)間復(fù)雜度?O(n?^?2)
Array.prototype.insertionSort?=?function?()?{

??//?遍歷數(shù)組?從第二個(gè)開始
??for?(let?i?=?1;?i?this.length;?i++)?{

????//?獲取第二個(gè)元素
????const?temp?=?this[i];

????let?j?=?i;
????while?(j?>?0)?{

??????//?如果當(dāng)前元素小于前一個(gè)元素?就開始往后移動(dòng)
??????if?(this[j?-?1]?>?temp)?{
????????this[j]?=?this[j?-?1];
??????}?else?{

????????//?否則就跳出循環(huán)
????????break
??????}

??????//?遞減
??????j--;
????}

????//?前一位置賦值為當(dāng)前元素
????this[j]?=?temp;
??}
}
復(fù)制代碼

4）歸并排序

分：把數(shù)組劈成兩半?在遞歸的對(duì)子數(shù)組進(jìn)行分操作，直到分成一個(gè)個(gè)單獨(dú)的數(shù)
合：把兩個(gè)樹合并為有序數(shù)組，再對(duì)有序數(shù)組進(jìn)行合并，直到全部子數(shù)組合并為一個(gè)完整的數(shù)組

//?時(shí)間復(fù)雜度?O(nlogn)?分需要劈開數(shù)組，所以是logn，?合則是n
//?空間復(fù)雜度?O(n)
Array.prototype.mergeSort?=?function?()?{

??const?rec?=?(arr)?=>?{
????//?遞歸終點(diǎn)
????if?(arr.length?===?1)?return?arr

????//?獲取中間索引
????const?mid?=?arr.length?>>?1;

????//?通過中間下標(biāo),進(jìn)行分割數(shù)組
????const?left?=?arr.slice(0,?mid);
????const?right?=?arr.slice(mid);

????//?左邊和右邊的數(shù)組進(jìn)行遞歸,會(huì)得到有序的左數(shù)組,和有序的右數(shù)組
????const?orderLeft?=?rec(left);
????const?orderRight?=?rec(right);


????//?存放結(jié)果的數(shù)組
????const?res?=?[];

??
????while?(orderLeft.length?||?orderRight.length)?{

??????//?如左邊和右邊數(shù)組都有值
??????if?(orderLeft.length?&&?orderRight.length)?{

????????//?左邊隊(duì)頭的值小于右邊隊(duì)頭的值?就左邊隊(duì)頭出隊(duì),否則就是右邊隊(duì)頭出隊(duì)
????????res.push(orderLeft[0]?0]???orderLeft.shift()?:?orderRight.shift())
??????}?else?if?(orderLeft.length)?{

????????//?把左邊的隊(duì)頭放入數(shù)組
????????res.push(orderLeft.shift())
??????}?else?if?(orderRight.length)?{

????????//?把右邊的隊(duì)頭放入數(shù)組
????????res.push(orderRight.shift())
??????}
????}

????return?res
??}

??const?res?=?rec(this)

??//?把結(jié)果放入原數(shù)組
??res.forEach((n,?i)?=>?this[i]?=?n)
}
復(fù)制代碼

> 合并兩個(gè)有序鏈表

//?時(shí)間復(fù)雜度O(n)?n為鏈表1和鏈表2的長(zhǎng)度之和
//?空間復(fù)雜度O(1)
var?mergeTwoLists?=?function?(list1,?list2)?{

??//?新建一個(gè)新鏈表?作為返回值
??const?res?=?{
????val:?0,
????next:?null
??}

??//?指向新鏈表的指針
??let?p?=?res;

??//?建立兩個(gè)指針
??let?p1?=?list1;
??let?p2?=?list2;


??//?遍歷兩個(gè)鏈表
??while?(p1?&&?p2)?{

????//?如果鏈表1?小于?鏈表2的值?就接入鏈表1的值
????if?(p1.val???????p.next?=?p1;

??????//?需要往后移動(dòng)
??????p1?=?p1.next;
????}?else?{

??????//?否則接入鏈表2的值
??????p.next?=?p2;

??????//?需要往后移動(dòng)
??????p2?=?p2.next;
????}

????//?p永遠(yuǎn)要往后移動(dòng)一位
????p?=?p.next;
??}

??//?如果鏈表1或者鏈表2還有值,就把后面的值全部接入新鏈表
??if?(p1)?{
????p.next?=?p1;
??}
??if?(p2)?{
????p.next?=?p2;
??}

??return?res.next;
};
復(fù)制代碼

5）快速排序

分區(qū)：從數(shù)組中任意選擇一個(gè)?基準(zhǔn)，所有比基準(zhǔn)小的元素放在基準(zhǔn)前面，比基準(zhǔn)大的元素放在基準(zhǔn)后面
遞歸：?遞歸的對(duì)基準(zhǔn)前后的子數(shù)組進(jìn)行分區(qū)

//?時(shí)間復(fù)雜度?O(nlogN)
//?空間復(fù)雜度?O(1)
Array.prototype.quickSort?=?function?()?{
??const?rec?=?(arr)?=>?{
??
????//?如果數(shù)組長(zhǎng)度小于等于1?就不用排序了
????if?(arr.length?<=?1)?{?return?arr?}

????//?存放基準(zhǔn)前后的數(shù)組
????const?left?=?[];
????const?right?=?[];

????//?取基準(zhǔn)
????const?mid?=?arr[0];

????for?(let?i?=?1;?i?
??????//?如果當(dāng)前值小于基準(zhǔn)就放到基準(zhǔn)前數(shù)組里面
??????if?(arr[i]?????????left.push(arr[i]);
??????}?else?{

????????//?否則就放到基準(zhǔn)后數(shù)組里面
????????right.push(arr[i]);
??????}
????}

????//?遞歸調(diào)用兩邊的子數(shù)組
????return?[...rec(left),?mid,?...rec(right)];
??};

??const?res?=?rec(this);
??res.forEach((n,?i)?=>?this[i]?=?n);
}
復(fù)制代碼

2. 搜索

找出數(shù)組中某個(gè)元素的下標(biāo)，js中通常使用indexOf方法進(jìn)行搜索

1）順序搜索

就比如indexOf方法，?從頭開始搜索數(shù)組中的某個(gè)元素

2）二分搜索

從數(shù)組中的中間位置開始搜索，如果中間元素正好是目標(biāo)值，則搜索結(jié)束
如果目標(biāo)值大于或者小于中間元素，則在大于或者小于中間元素的那一半數(shù)組中搜索
數(shù)組必須是有序的，如不是則需要先進(jìn)行排序

//?時(shí)間復(fù)雜度：O(log n)
//?空間復(fù)雜度：O(1)
Array.prototype.binarySearch?=?function?(item)?{
??//?代表數(shù)組的最小索引
??let?low?=?0;

??//?和最大索引
??let?higt?=?this.length?-?1;


??while?(low?<=?higt)?{

????//?獲取中間元素索引
????const?mid?=?(low?+?higt)?>>?1;
????
????const?element?=?this[mid];

????//?如果中間元素小于于要查找的元素?就把最小索引更新為中間索引的下一個(gè)
????if?(element???????low?=?mid?+?1
????}?else?if?(element?>?item)?{

????//?如果中間元素大于要查找的元素?就把最大索引更新為中間索引的前一個(gè)
??????higt?=?mid?-?1;
????}?else?{
??????//?如果中間元素等于要查找的元素?就返回索引
??????return?mid;
????}
??}

??return?-1
}
復(fù)制代碼

> 猜數(shù)字大小

//?時(shí)間復(fù)雜度?O(logn)?分割成兩半的?基本都是logn
//?空間復(fù)雜度?O(1)
var?guessNumber?=?function?(n)?{

??//?定義范圍最小值和最大值
??const?low?=?1;
??const?high?=?n;

??while?(low?<=?high)?{

????//?獲取中間值
????const?mid?=?(low?+?high)?>>>?1;

????//?這個(gè)方法是?leetcode?中的方法
????//?如果返回值為-1?就是小了
????//?如果返回值為1??就是大了
????//?如果返回值為0??就是找到了?
????const?res?=?guess(mid);
????
????//?剩下的操作就和二分搜索一樣
????if?(res?===?0)?{
??????return?mid
????}?else?if?(res?===?1)?{
??????low?=?mid?+?1;
????}?else?{
??????high?=?mid?-?1;
????}
??}
};
復(fù)制代碼

3. 分而治之

算法設(shè)計(jì)中的一種思想，將一個(gè)問題分成多個(gè)子問題，遞歸解決子問題，然后將子問題的解合并成最終的解

1）歸并排序

分：把數(shù)組從中間一分為二
解：遞歸地對(duì)兩個(gè)子數(shù)組進(jìn)行歸并排序
合：合并有序子數(shù)組

2）快速排序

分：選基準(zhǔn)，按基準(zhǔn)把數(shù)組分成兩個(gè)子數(shù)組
解：遞歸地對(duì)兩個(gè)子數(shù)組進(jìn)行快速排序
合：對(duì)兩個(gè)子數(shù)組進(jìn)行合并

3）二分搜索

二分搜索也屬于分而治之這種思想

> 分而治之思想：猜數(shù)字大小

//?時(shí)間復(fù)雜度?O(logn)?
//?空間復(fù)雜度?O(logn)?遞歸調(diào)用棧?所以是logn
var?guessNumber?=?function?(n)?{

??//?遞歸函數(shù)?接受一個(gè)搜索范圍
??const?rec?=?(low,?high)?=>?{
??
????//?遞歸結(jié)束條件
????if?(low?>?high)?return;

????//?獲取中間元素
????const?mid?=?(low?+?high)?>>>?1;

????//?判斷是否猜對(duì)
????const?res?=?guess(mid)

????//?猜對(duì)
????if?(res?===?0)?{
??????return?mid
????}?else?if?(res?===?1)?{
??????//?猜大了
??????return?rec(mid?+?1,?high)
????}?else?{
??????//?猜小了
??????return?rec(low,?mid?-?1)
????}
??}

??return?rec(1,?n)
};
復(fù)制代碼

> 分而治之思想：翻轉(zhuǎn)二叉樹

//?時(shí)間復(fù)雜度?O(n)?n為樹的節(jié)點(diǎn)數(shù)量
//?空間復(fù)雜度?O(h)?h為樹的高度
var?invertTree?=?function?(root)?{
??if?(!root)?return?null
??return?{
????val:?root.val,
????left:?invertTree(root.right),
????right:?invertTree(root.left)
??}
};
復(fù)制代碼

> 分而治之思想：相同的樹

//?時(shí)間復(fù)雜度?o(n)?n為樹的節(jié)點(diǎn)數(shù)量
//?空間復(fù)雜度?o(h)?h為樹的節(jié)點(diǎn)數(shù)
var?isSameTree?=?function?(p,?q)?{
??if?(!p?&&?!q)?return?true
??
??if?(
????p?&&?q
????&&?p.val?===?q.val
????&&?isSameTree(p.left,?q.left)
????&&?isSameTree(p.right,?q.right)
??)?return?true

??return?false
};
復(fù)制代碼

> 分而治之思想：對(duì)稱二叉樹

//?時(shí)間復(fù)雜度?O(n)
//?空間復(fù)雜度?O(n)?
var?isSymmetric?=?function?(root)?{
??if?(!root)?return?true
??const?isMirror?=?(l,?r)?=>?{
????if?(!l?&&?!r)?return?true
????if?(
??????l?&&?r?
??????&&?l.val?===?r.val
??????&&?isMirror(l.left,?r.right)
??????&&?isMirror(l.right,?r.left)
????)?return?true
????return?false
??}

??return?isMirror(root.left,?root.right)
};
復(fù)制代碼

4. 動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃是算法設(shè)計(jì)中的一種思想，將一個(gè)問題分解為相互重疊的子問題，通過反復(fù)求解子問題來解決原來的問題

1）斐波那契數(shù)列

//?時(shí)間復(fù)雜度?O(n)?
//?空間復(fù)雜度?O(n)
function?fib(n)?{
????let?dp?=?[0,?1,?1];
????for?(let?i?=?3;?i?<=?n;?i++)?{

????????//?當(dāng)前值等于前兩個(gè)值之和
????????dp[i]?=?dp[i?-?1]?+?dp[i?-?2];
????}
????return?dp[n];
}
復(fù)制代碼

2）爬樓梯

//?正在爬樓梯,?需要n階才能到達(dá)樓頂
//?每次只能爬?1?或者?2?個(gè)臺(tái)階,?有多少中不同的方法可以到達(dá)樓頂

//?時(shí)間復(fù)雜度?O(n)?n是樓梯長(zhǎng)度
//?空間復(fù)雜度?O(1)
var?climbStairs?=?function?(n)?{
????if?(n?2)?return?1

????let?dp0?=?1;
????let?dp1?=?1

????for?(let?i?=?2;?i?<=?n;?i++)?{
????????[dp0,?dp1]?=?[dp1,?dp1?+?dp0]
????}

????return?dp1
};
復(fù)制代碼

5. 貪心算法

貪心算法是算法設(shè)計(jì)中的一種思想，期盼通過每個(gè)階段的局部最優(yōu)選擇，從而達(dá)到全局的最優(yōu)，但?結(jié)果并不一定是最優(yōu)

1）分發(fā)餅干

//?每個(gè)孩子都有一個(gè)胃口g.?每個(gè)孩子只能擁有一個(gè)餅干
//?輸入:?g?=?[1,2,3],?s?=?[1,1]
//?輸出:?1
//?三個(gè)孩子胃口值分別是1,2,3??但是只有兩個(gè)餅干,所以只能讓胃口1的孩子滿足

//?時(shí)間復(fù)雜度?O(nlogn)?
//?空間復(fù)雜度?O(1)
var?findContentChildren?=?function?(g,?s)?{
????//?對(duì)餅干和孩子胃口進(jìn)行排序
????g.sort((a,?b)?=>?a?-?b)
????s.sort((a,?b)?=>?a?-?b)


????//?是第幾個(gè)孩子
????let?i?=?0

????s.forEach((n)?=>?{
????????//?如果餅干能滿足第一個(gè)孩子
????????if?(n?>=?g[i])?{?
????????????//?就開始滿足第二個(gè)孩子
????????????i?+=?1
????????}
????})

????return?i
}
復(fù)制代碼

2）買賣股票的最佳時(shí)機(jī)Ⅱ

//?時(shí)間復(fù)雜度?O(n)?n為股票的數(shù)量
//?空間復(fù)雜度?O(1)
var?maxProfit?=?function?(prices)?{
??//?存放利潤(rùn)
??const?profit?=?0;
??for?(let?i?=?1;?i?
????//?不貪?如有更高的利潤(rùn)就直接賣出
????if?(prices[i]?>?prices[i?-?1])?{
??????profit?+=?prices[i]?-?prices[i?-?1]
????}
??}

??return?profit
};
復(fù)制代碼

6. 回溯算法

回溯算法是算法設(shè)計(jì)中的一種思想，一種漸進(jìn)式尋找并構(gòu)建問題解決方式的策略，會(huì)先從一個(gè)可能的動(dòng)作開始解決問題，如不行，就回溯選擇另外一個(gè)動(dòng)作，直到找到一個(gè)解

1）全排列

//?輸入?[1,?2,?3]
//?輸出?[[1,?2,?3],?[1,?3,?2],?[2,?1,?3],?[2,?3,?1],?[3,?1,?2],?[3,?2,?1]]


//?時(shí)間復(fù)雜度?O(n!)?n!?=?1?*?2?*?3?*?···?*?(n-1)?*?n;
//?空間復(fù)雜度?O(n)
var?permute?=?function?(nums)?{
??//?存放結(jié)果
??const?res?=?[];

??const?backTrack?=?(path)?=>?{
????//?遞歸結(jié)束條件?
????if?(path.length?===?nums.length)?{
??????res.push(path)
??????return
????}

????//?遍歷傳入數(shù)組
????nums.forEach(n?=>?{
??????//?如果子數(shù)組中有這個(gè)元素就是死路，?需要回溯回去走其他路
??????if?(path.includes(n))?return;

??????//?加入到子數(shù)組里
??????backTrack(path.concat(n))
????})
??}

??backTrack([])

??return?res;
};
復(fù)制代碼

2）子集

//?輸入?[1,2,3]
//?輸出?[?[3],?[1],?[2],?[1,2,3],?[1,3],?[2,3],?[1,2],?[]?]

//?時(shí)間復(fù)雜度?O(2?^?N)?每個(gè)元素都有兩種可能
//?空間復(fù)雜度?O(N)
var?subsets?=?function?(nums)?{
??//?存放結(jié)果數(shù)組
??const?res?=?[];

??const?backTrack?=?(path,?l,?start)?=>?{
????//?遞歸結(jié)束條件
????if?(path.length?===?l)?{
??????res.push(path)
??????return
????}

????//?遍歷輸入的數(shù)組長(zhǎng)度?起始位置是start
????for?(let?i?=?start;?i?
??????//?遞歸調(diào)用?需要保證子集的有序,?start為?i+1
??????backTrack(path.concat(nums[i]),?l,?i?+?1)
????}
??};

??//?遍歷輸入數(shù)組長(zhǎng)度
??for?(let?i?=?0;?i?<=?nums.length;?i++)?{

????//?傳入長(zhǎng)度?起始索引
????backTrack([],?i,?0)
??}


??return?res
};
復(fù)制代碼

五、結(jié)語

本文中，僅對(duì)常見和常用的數(shù)據(jù)結(jié)構(gòu)與算法進(jìn)行了演示

算法這個(gè)東西，平時(shí)還是要?多練。記得看完后多刷一刷leetcode

文中如有錯(cuò)誤，歡迎大家在評(píng)論區(qū)指正，如果本文對(duì)你有幫助，記得點(diǎn)贊??和關(guān)注??

關(guān)于本文

來自：Ali2333

https://juejin.cn/post/7094056264283471908

最后

歡迎關(guān)注【前端瓶子君】??ヽ(°▽°)ノ?

回復(fù)「算法」，加入前端編程源碼算法群，每日一道面試題（工作日），第二天瓶子君都會(huì)很認(rèn)真的解答喲！

回復(fù)「交流」，吹吹水、聊聊技術(shù)、吐吐槽！

回復(fù)「閱讀」，每日刷刷高質(zhì)量好文！

如果這篇文章對(duì)你有幫助，「在看」是最大的支持

?》》面試官也在看的算法資料《《

“在看和轉(zhuǎn)發(fā)”就是最大的支持

萬字總結(jié) JS 數(shù)據(jù)結(jié)構(gòu)與常用的算法

一、前言

二、基本概念

1. 時(shí)間復(fù)雜度

2. 空間復(fù)雜度

三、數(shù)據(jù)結(jié)構(gòu)

1. 棧

1）十進(jìn)制轉(zhuǎn)二進(jìn)制

2）判斷字符串的有效括號(hào)

2. 隊(duì)列

1）最近的請(qǐng)求次數(shù)

3. 鏈表

1）手寫instanceOf

2）刪除鏈表中的節(jié)點(diǎn)

3）刪除排序鏈表中的重復(fù)元素

4）反轉(zhuǎn)鏈表

4. 集合

1）去重

2）兩個(gè)數(shù)組的交集

5. 字典

1）兩數(shù)之和

2）兩個(gè)數(shù)組的交集

3）字符的有效的括號(hào)

4）最小覆蓋字串

6. 樹

1）普通樹

> 深度優(yōu)先遍歷

> 廣度優(yōu)先遍歷

2）二叉樹

> 二叉樹的先序遍歷

> 二叉樹的中序遍歷

> 二叉樹的后序遍歷

> 二叉樹的最大深度

> 二叉樹的最小深度

> 二叉樹的層序遍歷

7. 圖

1）有效數(shù)字

8. 堆

2）JS實(shí)現(xiàn)一個(gè)最小堆

2）數(shù)組中的第k個(gè)最大元素

3）前 K 個(gè)高頻元素

四、常見算法及算法思想

1. 排序

1）冒泡排序

2）選擇排序

3）插入排序

4）歸并排序

> 合并兩個(gè)有序鏈表

5）快速排序

2. 搜索

1）順序搜索

2）二分搜索

> 猜數(shù)字大小

3. 分而治之

1）歸并排序

2）快速排序

3）二分搜索

> 分而治之思想：猜數(shù)字大小

> 分而治之思想：翻轉(zhuǎn)二叉樹

> 分而治之思想：相同的樹

> 分而治之思想：對(duì)稱二叉樹

4. 動(dòng)態(tài)規(guī)劃

1）斐波那契數(shù)列

2）爬樓梯

5. 貪心算法

1）分發(fā)餅干

2）買賣股票的最佳時(shí)機(jī)Ⅱ

6. 回溯算法

1）全排列

2）子集

五、結(jié)語

最后

一、前言

二、基本概念