一、前言

首先，為什么我會學習數據結構與算法呢，其實主要是有兩方面

• 第一，是我在今年的flag里明確說到我會學這個東西

• 第二，學了這些，對自己以后在工作或者面試也會帶來許多好處

然后，本文是最近學習的一個總結文章，文中有不足的地方也希望大家在評論區進行指正，本文較長，設有目錄。可直接通過目錄跳轉閱讀。

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

二、基本概念

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

1. 時間復雜度

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

它的作用就是用來定義描述算法的運行時間

• O(1)

let?i?=?0i?+=?1 復制代碼

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

for?(let?i?=?0;?i?<?n;?i?+=?1)?{console.log(i)} 復制代碼

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

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

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

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

2. 空間復雜度

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

它用來定義描述算法運行過程中臨時占用的存儲空間大小

占用越少 代碼寫的就越好

• O(1)：?單個變量，所以占用永遠是 O(1)

let?i?=?0i?+=?1 復制代碼

• O(n)：?聲明一個數組， 添加 n 個值， 相當于占用了 n 個空間單元

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

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

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

三、數據結構

1. 棧

一個后進先出的數據結構

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

image.png

js中沒有棧的數據類型，但我們可以通過Array來模擬一個

const?stack?=?[];stack.push(1);?//?入棧 stack.push(2);?//?入棧const?item1?=?stack.pop();??//出棧的元素 復制代碼

1）十進制轉二進制

//?時間復雜度?O(n)?n為二進制的長度 //?空間復雜度?O(n)?n為二進制的長度 const?dec2bin?=?(dec)?=>?{//?創建一個字符串let?res?=?"";//?創建一個棧let?stack?=?[]//?遍歷數字?如果大于0?就可以繼續轉換2進制while?(dec?>?0)?{//?將數字的余數入棧stack.push(dec?%?2);//?除以2dec?=?dec?>>?1;}//?取出棧中的數字while?(stack.length)?{res?+=?stack.pop();}//?返回這個字符串return?res; }; 復制代碼

2）判斷字符串的有效括號

//?時間復雜度O(n)?n為s的length //?空間復雜度O(n) const?isValid?=?(s)?=>?{//?如果長度不等于2的倍數肯定不是一個有效的括號if?(s.length?%?2?===?1)?return?false;//?創建一個棧let?stack?=?[];//?遍歷字符串for?(let?i?=?0;?i?<?s.length;?i++)?{const?c?=?s[i];//?如果是左括號就入棧if?(c?===?'('?||?c?===?"{"?||?c?===?"[")?{stack.push(c);}?else?{//?如果不是左括號?且棧為空?肯定不是一個有效的括號?返回falseif?(!stack.length)?return?false//?拿到最后一個左括號const?top?=?stack[stack.length?-?1];//?如果是右括號和左括號能匹配就出棧if?((top?===?"("?&&?c?===?")")?||?(top?===?"{"?&&?c?===?"}")?||?(top?===?"["?&&?c?===?"]"))?{stack.pop();}?else?{//?否則就不是一個有效的括號return?false}}}return?stack.length?===?0; }; 復制代碼

2. 隊列

和棧相反?先進先出的一個數據結構

按照常識理解就是銀行排號辦理業務,?先去領號排隊的人,?先辦理業務

image.png

同樣 js中沒有棧的數據類型，但我們可以通過?Array來模擬一個

const?queue?=?[];//?入隊 queue.push(1); queue.push(2);//?出隊 const?first?=?queue.shift(); const?end?=?queue.shift(); 復制代碼

1）最近的請求次數

var?RecentCounter?=?function?()?{//?初始化隊列this.q?=?[]; };//?輸入?inputs?=?[[],[1],[100],[3001],[3002]]?請求間隔為?3000ms //?輸出?outputs?=?[null,1,2,3,3]???//?時間復雜度?O(n)?n為剔出老請求的長度 //?空間復雜度?O(n)?n為最近請求的次數 RecentCounter.prototype.ping?=?function?(t)?{//?如果傳入的時間小于等于最近請求的時間，則直接返回0if?(!t)?return?null//?將傳入的時間放入隊列this.q.push(t);//?如果隊頭小于?t?-?3000?則剔除隊頭while?(this.q[0]?<?t?-?3000)?{this.q.shift();}//?返回最近請求的次數return?this.q.length; }; 復制代碼

3. 鏈表

多個元素組成的列表，元素存儲不連續，通過 next 指針來鏈接, 最底層為 null

就類似于?父輩鏈接關系?吧， 比如：你爺爺的兒子是你爸爸，你爸爸的兒子是你，而你假如目前還沒有結婚生子，那你就暫時木有兒子

image.png

js中類似于鏈表的典型就是原型鏈, 但是js中沒有鏈表這種數據結構，我們可以通過一個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; 復制代碼

1）手寫instanceOf

const?myInstanceOf?=?(A,?B)?=>?{//?聲明一個指針let?p?=?A;//?遍歷這個鏈表while?(p)?{if?(p?===?B.prototype)?return?true;p?=?p.__proto__;}return?false }myInstanceOf([],?Object) 復制代碼

2）刪除鏈表中的節點

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

3）刪除排序鏈表中的重復元素

//?1?->?1?->?2?->?3?->?3? //?1?->?2?->?3?->?null//?時間復雜度?O(n)?n為鏈表的長度 //?空間復雜度?O(1) const?deleteDuplicates?=?(head)?=>?{//?創建一個指針let?p?=?head;//?遍歷鏈表while?(p?&&?p.next)?{//?如果當前節點的值等于下一個節點的值if?(p.val?===?p.next.val)?{//?刪除下一個節點p.next?=?p.next.next}?else?{//?否則繼續遍歷p?=?p.next}}//??最后返回原來鏈表return?head } 復制代碼

4）反轉鏈表

//?1?->?2?->?3?->?4?->?5?->?null //?5?->?4?->?3?->?2?->?1?->?null//?時間復雜度?O(n)?n為鏈表的長度 //?空間復雜度?O(1) var?reverseList?=?function?(head)?{//?創建一個指針let?p1?=?head;//?創建一個新指針let?p2?=?null;//?遍歷鏈表while?(p1)?{//?創建一個臨時變量const?tmp?=?p1.next;//?將當前節點的下一個節點指向新鏈表p1.next?=?p2;//?將新鏈表指向當前節點p2?=?p1;//?將當前節點指向臨時變量p1?=?tmp;}//?最后返回新的這個鏈表return?p2; }reverseList(list 復制代碼

4. 集合

一種無序且唯一的數據結構

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))); 復制代碼

1）去重

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

2）兩個數組的交集

//?時間復雜度?O(n^2)?n為數組長度 //?空間復雜度?O(n)??n為去重后的數組長度 const?intersection?=?(nums1,?nums2)?=>?{//?通過數組的filter選出交集//?然后通過?Set集合?去重?并生成數組return?[...new?Set(nums1.filter(item?=>?nums2.includes(item)))]; } 復制代碼

5. 字典

與集合類似，一個存儲唯一值的結構,以鍵值對的形式存儲

js中有字典數據結構 就是?Map 類型

1）兩數之和

//?nums?=?[2,?7,?11,?15]?target?=?9//?時間復雜度O(n)?n為nums的length //?空間復雜度O(n) var?twoSum?=?function?(nums,?target)?{//?建立一個字典數據結構來保存需要的值const?map?=?new?Map();for?(let?i?=?0;?i?<?nums.length;?i++)?{//?獲取當前的值，和需要的值const?n?=?nums[i];const?n2?=?target?-?n;//?如字典中有需要的值，就匹配成功if?(map.has(n2))?{return?[map.get(n2),?i];}?else?{//?如沒有，則把需要的值添加到字典中map.set(n,?i);}} }; 復制代碼

2）兩個數組的交集

//?nums1?=?[1,2,2,1],?nums2?=?[2,2] //?輸出：[2]//?時間復雜度?O(m?+?n)?m為nums1長度?n為nums2長度 //?空間復雜度?O(m)?m為交集的數組長度 const?intersection?=?(nums1,?nums2)?=>?{//?創建一個字典const?map?=?new?Map();//?將數組1中的數字放入字典nums1.forEach(n?=>?map.set(n,?true));//?創建一個新數組const?res?=?[];//?將數組2遍歷?并判斷是否在字典中nums2.forEach(n?=>?{if?(map.has(n))?{res.push(n);//?如果在字典中，則刪除該數字map.delete(n);}})return?res; }; 復制代碼

3）字符的有效的括號

//?用字典優化//?時間復雜度?O(n)?n為s的字符長度 //?空間復雜度?O(n)? const?isValid?=?(s)?=>?{//?如果長度不等于2的倍數肯定不是一個有效的括號if?(s.length?%?2?!==?0)?return?false//?創建一個字典const?map?=?new?Map();map.set('(',?')');map.set('{',?'}');map.set('[',?']');//?創建一個棧const?stack?=?[];//?遍歷字符串for?(let?i?=?0;?i?<?s.length;?i++)?{//?取出字符const?c?=?s[i];//?如果是左括號就入棧if?(map.has(c))?{stack.push(c)}?else?{//?取出棧頂const?t?=?stack[stack.length?-?1];//?如果字典中有這個值?就出棧if?(map.get(t)?===?c)?{stack.pop();}?else?{//?否則就不是一個有效的括號return?false}}}return?stack.length?===?0; }; 復制代碼

4）最小覆蓋字串

//?輸入：s =?"ADOBECODEBANC", t =?"ABC" //?輸出："BANC"//?時間復雜度?O(m?+?n)?m是t的長度?n是s的長度 //?空間復雜度?O(k)?k是字符串中不重復字符的個數 var?minWindow?=?function?(s,?t)?{//?定義雙指針維護一個滑動窗口let?l?=?0;let?r?=?0;//?建立一個字典const?need?=?new?Map();//??遍歷tfor?(const?c?of?t)?{need.set(c,?need.has(c)???need.get(c)?+?1?:?1)}let?needType?=?need.size//?記錄最小子串let?res?=?""//?移動右指針while?(r?<?s.length)?{//?獲取當前字符const?c?=?s[r];//?如果字典里有這個字符if?(need.has(c))?{//?減少字典里面的次數need.set(c,?need.get(c)?-?1);//?減少需要的值if?(need.get(c)?===?0)?needType?-=?1;}//?如果字典中所有的值都為0了?就說明找到了一個最小子串while?(needType?===?0)?{//?取出當前符合要求的子串const?newRes?=?s.substring(l,?r?+?1)//?如果當前子串是小于上次的子串就進行覆蓋if?(!res?||?newRes.length?<?res.length)?res?=?newRes;//?獲取左指針的字符const?c2?=?s[l];//?如果字典里有這個字符if?(need.has(c2))?{//?增加字典里面的次數need.set(c2,?need.get(c2)?+?1);//?增加需要的值if?(need.get(c2)?===?1)?needType?+=?1;}l?+=?1;}r?+=?1;}return?res }; 復制代碼

6. 樹

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

js中沒有樹 但是可以用?Object 和 Array 構建樹

1）普通樹

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

> 深度優先遍歷

• 盡可能深的搜索樹的分支,就比如遇到一個節點就會直接去遍歷他的子節點，不會立刻去遍歷他的兄弟節點

• 口訣：

• 訪問根節點

• 對根節點的 children 挨個進行深度優先遍歷

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

> 廣度優先遍歷

• 先訪問離根節點最近的節點, 如果有兄弟節點就會先遍歷兄弟節點，再去遍歷自己的子節點

• 口訣

• 新建一個隊列 并把根節點入隊

• 把隊頭出隊并訪問

• 把隊頭的children挨個入隊

• 重復第二 、三步 直到隊列為空

//?廣度優先遍歷 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))} }; 復制代碼

2）二叉樹

樹中每個節點?最多只能有兩個子節點

Snipaste_2022-04-30_20-33-08.pngconst?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}} } 復制代碼

> 二叉樹的先序遍歷

• 訪問根節點

• 對根節點的左子樹進行先序遍歷

• 對根節點的右子樹進行先序遍歷

//?先序遍歷?遞歸 const?preOrder?=?(tree)?=>?{if?(!tree)?returnconsole.log(tree.val);preOrder(tree.left);preOrder(tree.right); }//?先序遍歷?非遞歸 const?preOrder2?=?(tree)?=>?{if?(!tree)?return//?新建一個棧const?stack?=?[tree];while?(stack.length?>?0)?{const?n?=?stack.pop();console.log(n.val);//?負負為正if?(n.right)?stack.push(n.right);if?(n.left)?stack.push(n.left);} } 復制代碼

> 二叉樹的中序遍歷

• 對根節點的左子樹進行中序遍歷

• 訪問根節點

• 對根節點的右子樹進行中序遍歷

二叉樹中序.png//?中序遍歷?遞歸 const?inOrder?=?(tree)?=>?{if?(!tree)?return;inOrder(tree.left)console.log(tree.val);inOrder(tree.right) }//?中序遍歷?非遞歸 const?inOrder2?=?(tree)?=>?{if?(!tree)?return;//?新建一個棧const?stack?=?[];//?先遍歷所有的左節點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;} } 復制代碼

> 二叉樹的后序遍歷

• 對根節點的左子樹進行后序遍歷

• 對根節點的右子樹進行后序遍歷

• 訪問根節點

二叉樹后序.png//?后序遍歷?遞歸 const?postOrder?=?(tree)?=>?{if?(!tree)?returnpostOrder(tree.left)postOrder(tree.right)console.log(tree.val) };//?后序遍歷?非遞歸 const?postOrder2?=?(tree)?=>?{if?(!tree)?returnconst?stack?=?[tree];const?outputStack?=?[];while?(stack.length)?{const?n?=?stack.pop();outputStack.push(n)//?負負為正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);} }; 復制代碼

> 二叉樹的最大深度

//?給一個二叉樹，需要你找出其最大的深度，從根節點到葉子節點的距離//?時間復雜度?O(n)?n為樹的節點數 //?空間復雜度?有一個遞歸調用的棧?所以為?O(n)?n也是為二叉樹的最大深度 var?maxDepth?=?function?(root)?{let?res?=?0;//?使用深度優先遍歷const?dfs?=?(n,?l)?=>?{if?(!n)?return;if?(!n.left?&&?!n.right)?{//?沒有葉子節點就把深度數量更新res?=?Math.max(res,?l);}dfs(n.left,?l?+?1)dfs(n.right,?l?+?1)}dfs(root,?1)return?res } 復制代碼

> 二叉樹的最小深度

//?給一個二叉樹，需要你找出其最小的深度，?從根節點到葉子節點的距離//?時間復雜度O(n)?n是樹的節點數量 //?空間復雜度O(n)?n是樹的節點數量 var?minDepth?=?function?(root)?{if?(!root)?return?0//?使用廣度優先遍歷const?q?=?[[root,?1]];while?(q.length)?{//?取出當前節點const?[n,?l]?=?q.shift();//?如果是葉子節點直接返回深度就可if?(!n.left?&&?!n.right)?return?lif?(n.left)?q.push([n.left,?l?+?1]);if?(n.right)?q.push([n.right,?l?+?1]);}} 復制代碼

> 二叉樹的層序遍歷

Snipaste_2022-04-30_20-33-08.png//?需要返回?[[1],?[2,3],?[4,5]]//?時間復雜度?O(n)?n為樹的節點數 //?空間復雜度?O(n)? var?levelOrder?=?function?(root)?{if?(!root)?return?[]//?廣度優先遍歷const?q?=?[root];const?res?=?[];while?(q.length)?{let?len?=?q.lengthres.push([])//?循環每層的節點數量次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 }; 復制代碼

7. 圖

圖是網絡結構的抽象模型, 是一組由邊連接的節點

js中可以利用Object和Array構建圖

樹.png//?上圖可以表示為 const?graph?=?{0:?[1,?2],1:?[2],2:?[0,?3],3:?[3] }//?深度優先遍歷，對根節點沒訪問過的相鄰節點挨個進行遍歷 {//?記錄節點是否訪問過const?visited?=?new?Set();const?dfs?=?(n)?=>?{visited.add(n);//?遍歷相鄰節點graph[n].forEach(c?=>?{//?沒訪問過才可以，進行遞歸訪問if(!visited.has(c)){dfs(c)}});}//?從2開始進行遍歷dfs(2) }//?廣度優先遍歷? {const?visited?=?new?Set();//?新建一個隊列，?根節點入隊，?設2為根節點const?q?=?[2];visited.add(2)while?(q.length)?{//?隊頭出隊，并訪問const?n?=?q.shift();console.log(n);graph[n].forEach(c?=>?{//?對沒訪問過的相鄰節點入隊if?(!visited.has(c))?{q.push(c)visited.add(c)}})} } 復制代碼

1）有效數字

//?生成數字關系圖?只有狀態為?3?5?6?的時候才為一個數字 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?}, }//?時間復雜度?O(n)?n是字符串長度 //?空間復雜度?O(1)? var?isNumber?=?function?(s)?{//?記錄狀態let?state?=?0;//?遍歷字符串for?(c?of?s.trim())?{//?把字符進行轉換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就是錯誤if?(state?===?undefined)?return?false}//?判斷最后的結果是不是合法的數字if?(state?===?3?||?state?===?5?||?state?===?6)?return?truereturn?false };? 復制代碼

8. 堆

一種特殊的完全二叉樹, 所有的節點都大于等于最大堆,或者小于等于最小堆的子節點

js通常使用數組來表示堆

• 左側子節點的位置是?2*index + 1

• 右側子節點的位置是?2*index + 2

• 父節點的位置是?(index - 1) / 2?, 取余數

堆.png

2）JS實現一個最小堆

//?js實現最小堆類 class?MinHeap?{constructor()?{//?元素容器this.heap?=?[];}//?交換節點的值swap(i1,?i2)?{[this.heap[i1],?this.heap[i2]]?=?[this.heap[i2],?this.heap[i1]]}//??獲取父節點getParentIndex(index)?{//?除以二，?取余數return?(index?-?1)?>>?1;}//?獲取左側節點索引getLeftIndex(i)?{return?(i?<<?1)?+?1;}//?獲取右側節點索引getRightIndex(i)?{return?(i?<<?1)?+?2;}//?上移shiftUp(index)?{if?(index?==?0)?return;//?獲取父節點const?parentIndex?=?this.getParentIndex(index);//?如果父節點的值大于當前節點的值?就需要進行交換if?(this.heap[parentIndex]?>?this.heap[index])?{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[index])?{//?進行節點交換this.swap(leftIndex,?index);//?繼續進行下移this.shiftDown(leftIndex)}//?如果右側節點小于當前的值if?(this.heap[rightIndex]?<?this.heap[index])?{this.swap(rightIndex,?index);this.shiftDown(rightIndex)}}//?插入元素insert(value)?{//?插入到堆的底部this.heap.push(value);//?然后上移：?將這個值和它的父節點進行交換，知道父節點小于等于這個插入的值this.shiftUp(this.heap.length?-?1)}//?刪除堆項pop()?{//?把數組最后一位?轉移到數組頭部this.heap[0]?=?this.heap.pop();//?進行下移操作this.shiftDown(0);}//?獲取堆頂元素peek()?{return?this.heap[0]}//?獲取堆大小size()?{return?this.heap.length}} 復制代碼

2）數組中的第k個最大元素

//?輸入?[3,2,1,5,6,4]?和?k?=?2 //?輸出?5//?時間復雜度?O(n?*?logK)?K就是堆的大小 //?空間復雜度?O(K)?K是參數k var?findKthLargest?=?function?(nums,?k)?{//?使用上面js實現的最小堆類，來構建一個最小堆const?h?=?new?MinHeap();//?遍歷數組nums.forEach(n?=>?{//?把數組中的值依次插入到堆里h.insert(n);if?(h.size()?>?k)?{//?進行優勝劣汰h.pop();}})return?h.peek() }; 復制代碼

3）前 K 個高頻元素

//?nums?=?[1,1,1,2,2,3],?k?=?2 //?輸出:?[1,2]//?時間復雜度?O(n?*?logK)? //?空間復雜度?O(k) var?topKFrequent?=?function?(nums,?k)?{//?統計每個元素出現的頻率const?map?=?new?Map();//?遍歷數組?建立映射關系nums.forEach(n?=>?{map.set(n,?map.has(n)???map.get(n)?+?1?:?1);})//?建立最小堆const?h?=?new?MinHeap();//?遍歷映射關系map.forEach((value,?key)?=>?{//?由于插入的元素結構發生了變化，所以需要對?最小堆的類?進行改造一下,改造的方法我會寫到最后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.heap[index].value)?{ //?????this.swap(leftIndex,?index); //?????this.shiftDown(leftIndex) //???}//???if?(this.heap[rightIndex]?&&?this.heap[rightIndex].value?<?this.heap[index].value)?{ //?????this.swap(rightIndex,?index); //?????this.shiftDown(rightIndex) //???} //?} 復制代碼

四、常見算法及算法思想

1. 排序

把某個亂序的數組變成升序序或者降序的數組， js比較常用sort方法進行排序

1）冒泡排序

• 比較所有相鄰元素，如果第一個比第二個大就交換他們

• 執行一次后可以保證最后一個數字是最大的

• 重復執行 n-1 次，就可以完成排序

//?時間復雜度?O(n?^?2)?n為數組長度 //?空間復雜度?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])?{//?交換數據[this[j],?this[j?+?1]]?=?[this[j?+?1],?this[j]];}}} } 復制代碼

2）選擇排序

• 找到數組中最小的值,選中它并放到第一位

• 接著找到數組中第二小的值,選中它并放到第二位

• 重復上述步驟執行 n-1 次

//?時間復雜度：O(n ^ 2) n為數組長度 //?空間復雜度：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++)?{//?如果當前這個元素?小于最小值的下標?就更新最小值的下標if?(this[j]?<?this[indexMin])?{indexMin?=?j;}}//?避免自己和自己進行交換if?(indexMin?!==?i)?{//?進行交換數據[this[i],?this[indexMin]]?=?[this[indexMin],?this[i]];}} } 復制代碼

3）插入排序

• 從第二個數，開始往前比較

• 如它大就往后排

• 以此類推進行到最后一個數

//?時間復雜度?O(n?^?2) Array.prototype.insertionSort?=?function?()?{//?遍歷數組?從第二個開始for?(let?i?=?1;?i?<?this.length;?i++)?{//?獲取第二個元素const?temp?=?this[i];let?j?=?i;while?(j?>?0)?{//?如果當前元素小于前一個元素?就開始往后移動if?(this[j?-?1]?>?temp)?{this[j]?=?this[j?-?1];}?else?{//?否則就跳出循環break}//?遞減j--;}//?前一位置賦值為當前元素this[j]?=?temp;} } 復制代碼

4）歸并排序

• 分：把數組劈成兩半?在遞歸的對子數組進行分操作，直到分成一個個單獨的數

• 合：把兩個樹合并為有序數組，再對有序數組進行合并， 直到全部子數組合并為一個完整的數組

//?時間復雜度?O(nlogn)?分需要劈開數組，所以是logn，?合則是n //?空間復雜度?O(n) Array.prototype.mergeSort?=?function?()?{const?rec?=?(arr)?=>?{//?遞歸終點if?(arr.length?===?1)?return?arr//?獲取中間索引const?mid?=?arr.length?>>?1;//?通過中間下標,進行分割數組const?left?=?arr.slice(0,?mid);const?right?=?arr.slice(mid);//?左邊和右邊的數組進行遞歸,會得到有序的左數組,和有序的右數組const?orderLeft?=?rec(left);const?orderRight?=?rec(right);//?存放結果的數組const?res?=?[];while?(orderLeft.length?||?orderRight.length)?{//?如左邊和右邊數組都有值if?(orderLeft.length?&&?orderRight.length)?{//?左邊隊頭的值小于右邊隊頭的值?就左邊隊頭出隊,否則就是右邊隊頭出隊res.push(orderLeft[0]?<?orderRight[0]???orderLeft.shift()?:?orderRight.shift())}?else?if?(orderLeft.length)?{//?把左邊的隊頭放入數組res.push(orderLeft.shift())}?else?if?(orderRight.length)?{//?把右邊的隊頭放入數組res.push(orderRight.shift())}}return?res}const?res?=?rec(this)//?把結果放入原數組res.forEach((n,?i)?=>?this[i]?=?n) } 復制代碼

> 合并兩個有序鏈表

//?時間復雜度O(n)?n為鏈表1和鏈表2的長度之和 //?空間復雜度O(1) var?mergeTwoLists?=?function?(list1,?list2)?{//?新建一個新鏈表?作為返回值const?res?=?{val:?0,next:?null}//?指向新鏈表的指針let?p?=?res;//?建立兩個指針let?p1?=?list1;let?p2?=?list2;//?遍歷兩個鏈表while?(p1?&&?p2)?{//?如果鏈表1?小于?鏈表2的值?就接入鏈表1的值if?(p1.val?<?p2.val)?{p.next?=?p1;//?需要往后移動p1?=?p1.next;}?else?{//?否則接入鏈表2的值p.next?=?p2;//?需要往后移動p2?=?p2.next;}//?p永遠要往后移動一位p?=?p.next;}//?如果鏈表1或者鏈表2還有值,就把后面的值全部接入新鏈表if?(p1)?{p.next?=?p1;}if?(p2)?{p.next?=?p2;}return?res.next; }; 復制代碼

5）快速排序

• 分區：從數組中任意選擇一個?基準， 所有比基準小的元素放在基準前面，比基準大的元素放在基準后面

• 遞歸：?遞歸的對基準前后的子數組進行分區

//?時間復雜度?O(nlogN) //?空間復雜度?O(1) Array.prototype.quickSort?=?function?()?{const?rec?=?(arr)?=>?{//?如果數組長度小于等于1?就不用排序了if?(arr.length?<=?1)?{?return?arr?}//?存放基準前后的數組const?left?=?[];const?right?=?[];//?取基準const?mid?=?arr[0];for?(let?i?=?1;?i?<?arr.length;?i++)?{//?如果當前值小于基準就放到基準前數組里面if?(arr[i]?<?mid)?{left.push(arr[i]);}?else?{//?否則就放到基準后數組里面right.push(arr[i]);}}//?遞歸調用兩邊的子數組return?[...rec(left),?mid,?...rec(right)];};const?res?=?rec(this);res.forEach((n,?i)?=>?this[i]?=?n); } 復制代碼

2. 搜索

找出數組中某個元素的下標，js中通常使用indexOf方法進行搜索

1）順序搜索

• 就比如indexOf方法，?從頭開始搜索數組中的某個元素

2）二分搜索

• 從數組中的中間位置開始搜索，如果中間元素正好是目標值，則搜索結束

• 如果目標值大于或者小于中間元素，則在大于或者小于中間元素的那一半數組中搜索

• 數組必須是有序的，如不是則需要先進行排序

//?時間復雜度：O(log n) //?空間復雜度：O(1) Array.prototype.binarySearch?=?function?(item)?{//?代表數組的最小索引let?low?=?0;//?和最大索引let?higt?=?this.length?-?1;while?(low?<=?higt)?{//?獲取中間元素索引const?mid?=?(low?+?higt)?>>?1;const?element?=?this[mid];//?如果中間元素小于于要查找的元素?就把最小索引更新為中間索引的下一個if?(element?<?item)?{low?=?mid?+?1}?else?if?(element?>?item)?{//?如果中間元素大于要查找的元素?就把最大索引更新為中間索引的前一個higt?=?mid?-?1;}?else?{//?如果中間元素等于要查找的元素?就返回索引return?mid;}}return?-1 } 復制代碼

> 猜數字大小

//?時間復雜度?O(logn)?分割成兩半的?基本都是logn //?空間復雜度?O(1) var?guessNumber?=?function?(n)?{//?定義范圍最小值和最大值const?low?=?1;const?high?=?n;while?(low?<=?high)?{//?獲取中間值const?mid?=?(low?+?high)?>>>?1;//?這個方法是?leetcode?中的方法//?如果返回值為-1?就是小了//?如果返回值為1??就是大了//?如果返回值為0??就是找到了?const?res?=?guess(mid);//?剩下的操作就和二分搜索一樣if?(res?===?0)?{return?mid}?else?if?(res?===?1)?{low?=?mid?+?1;}?else?{high?=?mid?-?1;}} }; 復制代碼

3. 分而治之

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

1）歸并排序

• 分：把數組從中間一分為二

• 解：遞歸地對兩個子數組進行歸并排序

• 合：合并有序子數組

2）快速排序

• 分：選基準，按基準把數組分成兩個子數組

• 解：遞歸地對兩個子數組進行快速排序

• 合：對兩個子數組進行合并

3）二分搜索

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

> 分而治之思想：猜數字大小

//?時間復雜度?O(logn)? //?空間復雜度?O(logn)?遞歸調用棧?所以是logn var?guessNumber?=?function?(n)?{//?遞歸函數?接受一個搜索范圍const?rec?=?(low,?high)?=>?{//?遞歸結束條件if?(low?>?high)?return;//?獲取中間元素const?mid?=?(low?+?high)?>>>?1;//?判斷是否猜對const?res?=?guess(mid)//?猜對if?(res?===?0)?{return?mid}?else?if?(res?===?1)?{//?猜大了return?rec(mid?+?1,?high)}?else?{//?猜小了return?rec(low,?mid?-?1)}}return?rec(1,?n) }; 復制代碼

> 分而治之思想：翻轉二叉樹

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

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

//?時間復雜度?o(n)?n為樹的節點數量 //?空間復雜度?o(h)?h為樹的節點數 var?isSameTree?=?function?(p,?q)?{if?(!p?&&?!q)?return?trueif?(p?&&?q&&?p.val?===?q.val&&?isSameTree(p.left,?q.left)&&?isSameTree(p.right,?q.right))?return?truereturn?false }; 復制代碼

> 分而治之思想：對稱二叉樹

//?時間復雜度?O(n) //?空間復雜度?O(n)? var?isSymmetric?=?function?(root)?{if?(!root)?return?trueconst?isMirror?=?(l,?r)?=>?{if?(!l?&&?!r)?return?trueif?(l?&&?r?&&?l.val?===?r.val&&?isMirror(l.left,?r.right)&&?isMirror(l.right,?r.left))?return?truereturn?false}return?isMirror(root.left,?root.right) }; 復制代碼

4. 動態規劃

動態規劃是算法設計中的一種思想，將一個問題分解為相互重疊的子問題，通過反復求解子問題來解決原來的問題

1）斐波那契數列

//?時間復雜度?O(n)? //?空間復雜度?O(n) function?fib(n)?{let?dp?=?[0,?1,?1];for?(let?i?=?3;?i?<=?n;?i++)?{//?當前值等于前兩個值之和dp[i]?=?dp[i?-?1]?+?dp[i?-?2];}return?dp[n]; } 復制代碼

2）爬樓梯

//?正在爬樓梯,?需要n階才能到達樓頂 //?每次只能爬?1?或者?2?個臺階,?有多少中不同的方法可以到達樓頂//?時間復雜度?O(n)?n是樓梯長度 //?空間復雜度?O(1) var?climbStairs?=?function?(n)?{if?(n?<?2)?return?1let?dp0?=?1;let?dp1?=?1for?(let?i?=?2;?i?<=?n;?i++)?{[dp0,?dp1]?=?[dp1,?dp1?+?dp0]}return?dp1 }; 復制代碼

5. 貪心算法

貪心算法是算法設計中的一種思想，期盼通過每個階段的局部最優選擇，從而達到全局的最優，但?結果并不一定是最優

1）分發餅干

//?每個孩子都有一個胃口g.?每個孩子只能擁有一個餅干 //?輸入:?g?=?[1,2,3],?s?=?[1,1] //?輸出:?1 //?三個孩子胃口值分別是1,2,3??但是只有兩個餅干,所以只能讓胃口1的孩子滿足//?時間復雜度?O(nlogn)? //?空間復雜度?O(1) var?findContentChildren?=?function?(g,?s)?{//?對餅干和孩子胃口進行排序g.sort((a,?b)?=>?a?-?b)s.sort((a,?b)?=>?a?-?b)//?是第幾個孩子let?i?=?0s.forEach((n)?=>?{//?如果餅干能滿足第一個孩子if?(n?>=?g[i])?{?//?就開始滿足第二個孩子i?+=?1}})return?i } 復制代碼

2）買賣股票的最佳時機Ⅱ

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

6. 回溯算法

回溯算法是算法設計中的一種思想，一種漸進式尋找并構建問題解決方式的策略，會先從一個可能的動作開始解決問題，如不行，就回溯選擇另外一個動作，直到找到一個解

1）全排列

//?輸入?[1,?2,?3] //?輸出?[[1,?2,?3],?[1,?3,?2],?[2,?1,?3],?[2,?3,?1],?[3,?1,?2],?[3,?2,?1]]//?時間復雜度?O(n!)?n!?=?1?*?2?*?3?*?···?*?(n-1)?*?n; //?空間復雜度?O(n) var?permute?=?function?(nums)?{//?存放結果const?res?=?[];const?backTrack?=?(path)?=>?{//?遞歸結束條件?if?(path.length?===?nums.length)?{res.push(path)return}//?遍歷傳入數組nums.forEach(n?=>?{//?如果子數組中有這個元素就是死路，?需要回溯回去走其他路if?(path.includes(n))?return;//?加入到子數組里backTrack(path.concat(n))})}backTrack([])return?res; }; 復制代碼

2）子集

//?輸入?[1,2,3] //?輸出?[?[3],?[1],?[2],?[1,2,3],?[1,3],?[2,3],?[1,2],?[]?]//?時間復雜度?O(2?^?N)?每個元素都有兩種可能 //?空間復雜度?O(N) var?subsets?=?function?(nums)?{//?存放結果數組const?res?=?[];const?backTrack?=?(path,?l,?start)?=>?{//?遞歸結束條件if?(path.length?===?l)?{res.push(path)return}//?遍歷輸入的數組長度?起始位置是startfor?(let?i?=?start;?i?<?nums.length;?i++)?{//?遞歸調用?需要保證子集的有序,?start為?i+1backTrack(path.concat(nums[i]),?l,?i?+?1)}};//?遍歷輸入數組長度for?(let?i?=?0;?i?<=?nums.length;?i++)?{//?傳入長度?起始索引backTrack([],?i,?0)}return?res }; 復制代碼

五、結語

本文中，僅對常見和常用的數據結構與算法進行了演示

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

文中如有錯誤，歡迎大家在評論區指正，如果本文對你有幫助， 記得點贊👍和關注??

關于本文

來自：Ali2333

https://juejin.cn/post/7094056264283471908

總結

以上是生活随笔為你收集整理的一篇关于 JS 常用的数据结构与算法万字总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。