一、前言

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

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

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

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

二、基本概念

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

1. 時間復雜度

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

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

• O(1)

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

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

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

• 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)
??????}
????}
復制代碼

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

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

2. 空間復雜度

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

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

占用越少 代碼寫的就越好

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

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

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

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

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

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

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

1. 棧

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

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

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

const?stack?=?[];

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

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

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

//?時間復雜度?O(n)?n為二進制的長度
//?空間復雜度?O(n)?n為二進制的長度
const?dec2bin?=?(dec)?=>?{
??//?創(chuàng)建一個字符串
??let?res?=?"";

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

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

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

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

??//?返回這個字符串
??return?res;
};
復制代碼

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

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

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

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

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

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

??????//?如果不是左括號?且棧為空?肯定不是一個有效的括號?返回false
??????if?(!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. 隊列

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

按照常識理解就是銀行排號辦理業(yè)務,?先去領(lǐng)號排隊的人,?先辦理業(yè)務

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

const?queue?=?[];

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

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

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

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

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

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

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

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

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

3. 鏈表

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

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

js中類似于鏈表的典型就是原型鏈, 但是js中沒有鏈表這種數(shù)據(jù)結(jié)構(gòu)，我們可以通過一個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）刪除鏈表中的節(jié)點

//?時間復雜和空間復雜度都是?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)?=>?{

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

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

????//?如果當前節(jié)點的值等于下一個節(jié)點的值
????if?(p.val?===?p.next.val)?{

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

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

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

4）反轉(zhuǎn)鏈表

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

//?時間復雜度?O(n)?n為鏈表的長度
//?空間復雜度?O(1)
var?reverseList?=?function?(head)?{

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

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

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

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

????//?將當前節(jié)點的下一個節(jié)點指向新鏈表
????p1.next?=?p2;

????//?將新鏈表指向當前節(jié)點
????p2?=?p1;

????//?將當前節(jié)點指向臨時變量
????p1?=?tmp;
??}

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

reverseList(list
復制代碼

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

1）去重

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

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

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

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

5. 字典

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

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

1）兩數(shù)之和

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

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

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

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

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

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

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

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

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

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

??return?res;
};
復制代碼

3）字符的有效的括號

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

//?時間復雜度?O(n)?n為s的字符長度
//?空間復雜度?O(n)?
const?isValid?=?(s)?=>?{

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

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

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

??//?遍歷字符串
??for?(let?i?=?0;?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是字符串中不重復字符的個數(shù)
var?minWindow?=?function?(s,?t)?{
??//?定義雙指針維護一個滑動窗口
??let?l?=?0;
??let?r?=?0;

??//?建立一個字典
??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?=?""

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

????//?如果字典里有這個字符
????if?(need.has(c))?{
????
??????//?減少字典里面的次數(shù)
??????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?
??????//?獲取左指針的字符
??????const?c2?=?s[l];

??????//?如果字典里有這個字符
??????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
};
復制代碼

6. 樹

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

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

1）普通樹

//?這就是一個常見的普通樹形結(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:?[],
????????}
??????],
????}
??],
}
復制代碼

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

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

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

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

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

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

2）二叉樹

樹中每個節(jié)點?最多只能有兩個子節(jié)點

?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
????}
??}
}
復制代碼

> 二叉樹的先序遍歷

• 訪問根節(jié)點
• 對根節(jié)點的左子樹進行先序遍歷
• 對根節(jié)點的右子樹進行先序遍歷

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

??console.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);

??}
}
復制代碼

> 二叉樹的中序遍歷

• 對根節(jié)點的左子樹進行中序遍歷
• 訪問根節(jié)點
• 對根節(jié)點的右子樹進行中序遍歷

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


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

??//?新建一個棧
??const?stack?=?[];

??//?先遍歷所有的左節(jié)點
??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;
??}
}
復制代碼

> 二叉樹的后序遍歷

• 對根節(jié)點的左子樹進行后序遍歷
• 對根節(jié)點的右子樹進行后序遍歷
• 訪問根節(jié)點

//?后序遍歷?遞歸
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)
????//?負負為正
????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);
??}
};
復制代碼

> 二叉樹的最大深度

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

//?時間復雜度?O(n)?n為樹的節(jié)點數(shù)
//?空間復雜度?有一個遞歸調(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é)點就把深度數(shù)量更新
??????res?=?Math.max(res,?l);
????}
????dfs(n.left,?l?+?1)
????dfs(n.right,?l?+?1)
??}

??dfs(root,?1)

??return?res
}
復制代碼

> 二叉樹的最小深度

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


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

??while?(q.length)?{
????//?取出當前節(jié)點
????const?[n,?l]?=?q.shift();
????
????//?如果是葉子節(jié)點直接返回深度就可
????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]);
??}

}
復制代碼

> 二叉樹的層序遍歷

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


//?時間復雜度?O(n)?n為樹的節(jié)點數(shù)
//?空間復雜度?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é)點數(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
};
復制代碼

7. 圖

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

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

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


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


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

1）有效數(shù)字

//?生成數(shù)字關(guān)系圖?只有狀態(tài)為?3?5?6?的時候才為一個數(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?},
}


//?時間復雜度?O(n)?n是字符串長度
//?空間復雜度?O(1)?
var?isNumber?=?function?(s)?{

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

??//?遍歷字符串
??for?(c?of?s.trim())?{
????//?把字符進行轉(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就是錯誤
????if?(state?===?undefined)?return?false
??}

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

8. 堆

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

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

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

2）JS實現(xiàn)一個最小堆

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

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

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

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

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


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

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

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

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

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

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

??????//?進行節(jié)點交換
??????this.swap(leftIndex,?index);

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

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

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

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

??//?刪除堆項
??pop()?{

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

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

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

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

}
復制代碼

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

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

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

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

??//?統(tǒng)計每個元素出現(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ā)生了變化，所以需要對?最小堆的類?進行改造一下,改造的方法我會寫到最后
????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)
//???}
//?}
復制代碼

四、常見算法及算法思想

1. 排序

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

1）冒泡排序

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

//?時間復雜度?O(n?^?2)?n為數(shù)組長度
//?空間復雜度?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]];
??????}
????}
??}
}
復制代碼

2）選擇排序

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

//?時間復雜度：O(n ^ 2) n為數(shù)組長度
//?空間復雜度：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)?{

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

3）插入排序

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

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

??//?遍歷數(shù)組?從第二個開始
??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?{

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

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

????//?前一位置賦值為當前元素
????this[j]?=?temp;
??}
}
復制代碼

4）歸并排序

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

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

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

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

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

????//?左邊和右邊的數(shù)組進行遞歸,會得到有序的左數(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)?{

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

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

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

????return?res
??}

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

??//?把結(jié)果放入原數(shù)組
??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???????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）快速排序

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

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

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

????//?取基準
????const?mid?=?arr[0];

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

????????//?否則就放到基準后數(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);
}
復制代碼

2. 搜索

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

1）順序搜索

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

2）二分搜索

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

//?時間復雜度：O(log n)
//?空間復雜度：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];

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

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

??return?-1
}
復制代碼

> 猜數(shù)字大小

//?時間復雜度?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）歸并排序

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

2）快速排序

• 分：選基準，按基準把數(shù)組分成兩個子數(shù)組
• 解：遞歸地對兩個子數(shù)組進行快速排序
• 合：對兩個子數(shù)組進行合并

3）二分搜索

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

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

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

??//?遞歸函數(shù)?接受一個搜索范圍
??const?rec?=?(low,?high)?=>?{
??
????//?遞歸結(jié)束條件
????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)
};
復制代碼

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

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

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

//?時間復雜度?o(n)?n為樹的節(jié)點數(shù)量
//?空間復雜度?o(h)?h為樹的節(jié)點數(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
};
復制代碼

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

//?時間復雜度?O(n)
//?空間復雜度?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)
};
復制代碼

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

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

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

//?時間復雜度?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?1

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

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

????return?dp1
};
復制代碼

5. 貪心算法

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

1）分發(fā)餅干

//?每個孩子都有一個胃口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?=?0

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

????return?i
}
復制代碼

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

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

??return?profit
};
復制代碼

6. 回溯算法

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

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)?{
??//?存放結(jié)果
??const?res?=?[];

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

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

??????//?加入到子數(shù)組里
??????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)?{
??//?存放結(jié)果數(shù)組
??const?res?=?[];

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

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

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

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


??return?res
};
復制代碼

五、結(jié)語

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

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

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

關(guān)于本文

來自：Ali2333

https://juejin.cn/post/7094056264283471908