再談前端算法，你這回明白了嗎？
楔子 -- 青蛙跳臺(tái)階
一只青蛙一次可以跳上一級(jí)臺(tái)階，也可以跳上二級(jí)臺(tái)階，求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共需要多少種跳法。
分析: 當(dāng)n=1的時(shí)候，①只需要跳一次即可；只有一種跳法，即f(1)=1；
當(dāng)n=2的時(shí)候，①可以先跳一級(jí)再跳一級(jí)，②也可以直接跳倆級(jí)；共有倆種跳法，即f(2)=2；
當(dāng)n=3的時(shí)候，①一階一階跳即可；
②他可以從一級(jí)臺(tái)階上跳倆階上來
③也可從二級(jí)臺(tái)階上跳一階上來;即共有f(3)=f(2)+f(1)；所以當(dāng)有n階臺(tái)階時(shí)，且當(dāng)n>2的時(shí)候，根據(jù)上面式子可推導(dǎo)出→ f(n)=f(n-1)+f(n-2)
圖片
所以很直白的看出就是個(gè) 斐波那契數(shù)列 ，有一點(diǎn)不同的是，斐波那契數(shù)列從1,1,2,3,5,8,13…開始的，而我們這是以1,2,3,5,8,13…開始的，少了前面的1
什么是算法
解決一系列問題的具體步驟
算法是一組用于解決特定問題或執(zhí)行特定任務(wù)的有限步驟序列。這些步驟按照確定的順序執(zhí)行，以達(dá)到所需的結(jié)果。在計(jì)算機(jī)科學(xué)中，算法通常用于描述數(shù)據(jù)處理、自動(dòng)化處理和數(shù)學(xué)運(yùn)算的過程。算法可以用來解決各種問題，包括排序、搜索、路徑規(guī)劃等。
算法實(shí)例 ：實(shí)現(xiàn)一個(gè)LRU緩存
LRU是Least Recently Used（最近最少使用）的縮寫。
在計(jì)算機(jī)科學(xué)中，LRU是一種頁面置換算法，通常用于操作系統(tǒng)的虛擬內(nèi)存管理中。
該算法根據(jù)頁面（或者其他資源）的最近使用情況來進(jìn)行置換，當(dāng)需要置換時(shí)，選擇最近最少被使用的頁面進(jìn)行替換。
這樣可以保證最常用的頁面保留在內(nèi)存中，從而提高性能。
實(shí)例：vue keep-alive 緩存
LRU -- 最近使用
實(shí)現(xiàn) LRUCache
緩存，有一個(gè)大小 const lru = new LRUCache(capacity)
提示
const lru = new LRUCache(2)
lru.put(1,1)
lru.put(2,2) // {1:1,2:2}
lru.get(1)
lru.put(3,3) // {1:1,3:3}
lru.get(2) // -1 (找不到)
lru.put(4,4) // {4:4,3:3}實(shí)現(xiàn)代碼
// 函數(shù)的 get 和 put 必須以 O(1)的時(shí)間復(fù)雜度運(yùn)行
// get，得是個(gè)hash（Map，Set），而不能是數(shù)組
// ES6 迭代器
const LRUCache = function(capacity){
this.cacheQueue = new Map()
this.capacity = capacity
}
LRUCache.prototype.get = function(key){
if(this.cacheQueue.has(key)){ // 如果找到了，這個(gè)key對(duì)應(yīng)的value要提升新鮮度
const result = this.cacheQueue.get(key)
// 刪掉，然后再放進(jìn)去，這樣，這個(gè)就能在cacheQueue的隊(duì)尾(隊(duì)尾為最新鮮地方)
this.cacheQueue.delete(key)
this.cacheQueue.set(key,result)
return result
}
return -1 // 如果沒有找到key，則直接返回 -1
}
LRUCache.prototype.put = function(key,value){
if(this.cacheQueue.has(key)){
// 如果找到了， 刪掉
this.cacheQueue.delete(key)
}
if(this.cacheQueue.size >= this.capacity){
// 刪除map的第一個(gè)元素，即最長時(shí)間未使用的
this.cacheQueue.set(key,value)
this.cacheQueue.delete(this.cacheQueue.keys().next().value)
} else {
this.cacheQueue.set(key,value)
}
}擴(kuò)展：ES6 Map
ES6的Map是一種內(nèi)置的數(shù)據(jù)結(jié)構(gòu)，它存儲(chǔ)鍵值對(duì)并允許你通過鍵快速查找值。
Map對(duì)象類似于對(duì)象，但不同之處在于Map的鍵可以是任意數(shù)據(jù)類型，而對(duì)象的鍵只能是字符串或Symbol。
Map還保留了插入順序，這意味著當(dāng)你遍歷一個(gè)Map對(duì)象時(shí)，它會(huì)按照插入順序返回鍵值對(duì)。
Map的創(chuàng)建和初始化：
要?jiǎng)?chuàng)建一個(gè)新的Map，你需要使用new Map()語法。
例如：
const myMap = new Map();添加鍵值對(duì)：
你可以使用Map對(duì)象的set()方法添加鍵值對(duì)。
例如：
myMap.set('key1', 'value1');
myMap.set('key2', 'value2');獲取鍵值對(duì)：
你可以使用Map對(duì)象的get()方法獲取鍵對(duì)應(yīng)的值。
例如：
const value1 = myMap.get('key1'); // 返回 'value1'
const value2 = myMap.get('key2'); // 返回 'value2'檢查Map中是否存在某個(gè)鍵：
你可以使用Map對(duì)象的has()方法檢查Map中是否存在某個(gè)鍵。
例如：
const hasKey1 = myMap.has('key1'); // 返回 true
const hasKey3 = myMap.has('key3'); // 返回 false刪除鍵值對(duì)：
你可以使用Map對(duì)象的delete()方法刪除鍵值對(duì)。
例如：
myMap.delete('key1');遍歷Map：
你可以使用Map對(duì)象的keys()、values()或entries()方法遍歷Map中的鍵或值。
例如：
for (const key of myMap.keys()) {
console.log(key); // 輸出鍵名
}
for (const value of myMap.values()) {
console.log(value); // 輸出值
}
for (const [key, value] of myMap.entries()) {
console.log(key, value); // 輸出鍵名和值
}
myMap.forEach((value, key) => {
console.log(key + ' = ' + value);
});獲取Map的大?。?/h4>myMap.size; // 返回Map的大小
myMap.size; // 返回Map的大小更多詳細(xì)內(nèi)容，請(qǐng)微信搜索“前端愛好者“， 戳我 查看 。
算法實(shí)例 ：求環(huán)狀鏈表
leecode的地址：https://leetcode.cn/problems/linked-list-cycle/
鏈表：常見 -- react源碼
圖片
思路：快慢指針，兩個(gè)（起點(diǎn)相同位置）指針，n步驟以后指針相遇
圖片
實(shí)現(xiàn)代碼
head.next 指向下一個(gè)值
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let fast = slow = head
while(fast && fast.next){
fast = fast.next.next
slow = slow.next
if(fast === slow){
return true
}
}
return false
};擴(kuò)展：鏈表
鏈表是一種數(shù)據(jù)結(jié)構(gòu)，其中的元素以節(jié)點(diǎn)的形式按順序排列。
每個(gè)節(jié)點(diǎn)都包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的引用。
相比數(shù)組，鏈表在插入和刪除元素時(shí)更靈活，因?yàn)樗鼈儾恍枰B續(xù)的存儲(chǔ)空間。
舉例來說，一個(gè)簡(jiǎn)單的鏈表可以被定義如下：
Node 1: 23 -> Node 2
Node 2: 47 -> Node 3
Node 3: 95 -> null在這個(gè)例子中，鏈表中的每個(gè)節(jié)點(diǎn)包含一個(gè)值和指向下一個(gè)節(jié)點(diǎn)的引用。
第一個(gè)節(jié)點(diǎn)包含值23，同時(shí)指向第二個(gè)節(jié)點(diǎn)，依此類推。最后一個(gè)節(jié)點(diǎn)指向null，表示鏈表的結(jié)束。
通過使用鏈表，我們可以輕松地插入或刪除節(jié)點(diǎn)，而無需移動(dòng)其他節(jié)點(diǎn)。
這使得鏈表在某些場(chǎng)景下比數(shù)組更為適用。
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上 非連續(xù)、非順序 的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。
鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。
每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。
鏈表有很多種不同的類型，包括單向鏈表、雙向鏈表以及循環(huán)鏈表。
鏈表可以在多種編程語言中實(shí)現(xiàn)，例如C、C++和Java等。
算法實(shí)例 ：二又樹的前序、中序、后序遍歷
圖片
前序遍歷 - 根左右
先走根節(jié)點(diǎn)，然后左，然后右
圖片
中序遍歷 - 左根右
先走左節(jié)點(diǎn)，然后根節(jié)點(diǎn)，然后右節(jié)點(diǎn)
圖片
后序遍歷 - 左右根
先走左節(jié)點(diǎn)，然后右節(jié)點(diǎn)，然后再根節(jié)點(diǎn)
圖片
舉例
圖片
前/先序遍歷: GDAFEMHZ 中序遍歷: ADEFGHMZ 后序遍歷: AEFDHZMG
圖片
前序遍歷: A-B-D-F-G-H-I-E-C 中序遍歷: F-D-H-G-I-B-E-A-C 后序遍歷: F-H-I-G-D-E-B-C-A
實(shí)現(xiàn)代碼
const treeRoot = {
val: 1,
left: {
val: 2,
left: {
val: 4,
},
right: {
val: 5,
}
},
right: {
val: 3,
left: {
val: 6,
},
right: {
val: 7,
}
}
}
// 前序
const preOrder = function(node){
if(node){
// 如果有根節(jié)點(diǎn)
console.log(node.val)
preOrder(node.left)
preOrder(node.right)
}
}
preOrder(treeRoot)
// 中序
const inOrder = function(node){
if(node){
// 如果有根節(jié)點(diǎn)
inOrder(node.left)
console.log(node.val)
inOrder(node.right)
}
}
inOrder(treeRoot)
// 后序
const nextOrder = function(node){
if(node){
// 如果有根節(jié)點(diǎn)
nextOrder(node.left)
nextOrder(node.right)
console.log(node.val)
}
}
nextOrder(treeRoot)（二叉樹）層序遍歷
leetcode地址：https://leetcode.cn/problems/binary-tree-level-order-traversal/
圖片
輸入：root = [3,9,20,null,null,15,7] 輸出：[[3],[9,20],[15,7]]
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if(!root) return []
let queue = [root]
let result = []
// 開始遍歷
while(queue.length){
let temQueue = []
let temResult = []
let len = queue.length
for(let i = 0; i < len; i++){
let node = queue.shift()
temResult.push(node.val)
node.left && temQueue.push(node.left)
node.right && temQueue.push(node.right)
}
// 循環(huán)完畢
result.push(temResult)
temResult = []
queue = temQueue
}
return result
};（二叉樹）的層級(jí)
leetcode地址：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
直接return 上面層序的lengh
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var maxDepth = function(root) {
if(!root) return []
let queue = [root]
let result = []
// 開始遍歷
while(queue.length){
let temQueue = []
let temResult = []
let len = queue.length
for(let i = 0; i < len; i++){
let node = queue.shift()
temResult.push(node.val)
node.left && temQueue.push(node.left)
node.right && temQueue.push(node.right)
}
// 循環(huán)完畢
result.push(temResult)
temResult = []
queue = temQueue
}
return result.length
};使用DP方法
let maxDepth = function(root){
if(!root) return 0 // 如果沒有根節(jié)點(diǎn)，則直接返回0
// 找左右叉的最大值
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1
}類數(shù)組轉(zhuǎn)數(shù)組有多少種方法
const arrayLike = document.querySelectorAll('div')
圖片
擴(kuò)展運(yùn)算符
[...arrayLike]prototype
Array.prototype.slice.call(arrayLike)
Array.prototype.concat.apply([],arrayLike)Array.from
Array.from(arrayLike)Array.apply
Array.apply(null,arrayLike)擴(kuò)展：數(shù)組常用哪些方法？
數(shù)組常用方法很多，主要包括以下幾個(gè)：
- 1. find()：返回?cái)?shù)組中符合測(cè)試函數(shù)條件的第一個(gè)元素值。
const numbers = [10, 20, 30, 40];
const result = numbers.find(num => num > 25);
// 結(jié)果為30- 2. findIndex()：返回?cái)?shù)組中符合測(cè)試函數(shù)條件的第一個(gè)元素索引。
const numbers = [10, 20, 30, 40];
const index = numbers.findIndex(num => num > 25);
// 結(jié)果為2（即元素30對(duì)應(yīng)的索引）- 3. forEach()：對(duì)數(shù)組的每個(gè)元素執(zhí)行提供的函數(shù)。
const numbers = [1, 2, 3];
numbers.forEach(num => console.log(num * 2));
// 輸出2, 4, 6- 4. map()：對(duì)數(shù)組的每個(gè)元素執(zhí)行提供的函數(shù)，并返回結(jié)果組成的新數(shù)組。
const numbers = [1, 2, 3];
const doubled = numbers.map(num => num * 2);
// 結(jié)果為[2, 4, 6]- 5. filter()：使用給定函數(shù)測(cè)試所有元素，并返回由所有通過測(cè)試的元素組成的新數(shù)組。
const numbers = [10, 15, 20, 25, 30];
const greaterThan20 = numbers.filter(num => num > 20);
// 結(jié)果為[25, 30]這些方法在處理數(shù)組時(shí)非常有用，并且能夠簡(jiǎn)化一些常見的操作。
