上大学的时候老师讲数据结构总是不以为然，工作一年了也没有对这方面的知识有点清晰的理解和感触。前段时间看到大佬公众号的文章，才对算法这种虚无缥缈的东西有了个清晰的认知。
文章链接：https://mp.weixin.qq.com/s/Sj4mB0V9TXHB5XpQLsrTEw
本文学习记录自修言大佬的掘金小册：《前端算法与数据结构面试：底层逻辑解读与大厂真题训练》
推荐大家也去看看，还有修言大佬的设计模式小册也不错！！！
对于一个斐波那契数列的求解，你能想到多少种方法？
最简单的---递归：
function fib(n){
if(n == 1 || n == 2){
return 1;
}
return fib(n - 2) + fib(n - 1);
}运行fib(50)的时候，在我笔记本上跑了将近107秒，如图：
运用算法进行优化---备忘录解法：
核心：去除很多不必要的重复运算
let fib = (function(){
let memo = new Map();
return function (n){
// 查找记忆中有无这个计算
// 没有就继续递归
let memorized = memo.get(n);
if(memorized){
return memorized;
}
if(n == 1 || n == 2){
return 1;
}
let f1 = fib(n - 1);
let f2 = fib(n - 2);
// 将计算记忆到Map中
memo.set(n - 1,f1);
memo.set(n - 2,f2);
return f1 + f2;
};
})();运算时长如图：
只是去除不必要的重复计算就得到了这么大的性能提升，这就是算法的魅力所在。
算法再优化---动态规划
看似上面的备忘录解法已经很完美了，实际上不是，虽然备忘录解法把无用的重复求解都优化了，在速度上达到了比较优的程度。
但是对于第一次求解，未被记忆化的值来说，还是会进入递归调用逻辑。
比如 f(10000)，那么必然会递归调用 f(9999)、f(9998) ...... f(0)，而在递归的过程中，这些调用栈是不断叠加的，当函数调用的深处，栈已经达到了成千上万层。
此时它就会报出一个我们熟悉的错误：
RangeError: Maximum call stack size exceeded
at c:\codes\leetcode-javascript\动态规划\斐波那契数列-509.js:20:19
at c:\codes\leetcode-javascript\动态规划\斐波那契数列-509.js:32:14
我们回过头来思考一下，备忘录的思路下我们的解法路径是「自顶向下」的，如果我们把思路倒置一下，变成「自底向上」的求解呢？
也就是说，对于 fib(10000)，我们从 fib(1), fib(2), fib(3) ...... fib(10000)，
从最小的值开始求解，并且把每次求解的值保存在“记忆”（可以是一个数组，下标正好用来对应 n 的解答值）里，下面的值都由记忆中的值直接得出。
这样等到算到 10000 的时候，我们想要求解的值自然也就得到了，直接从 记忆[10000] 里取到值返回即可。
那么这种解法其实只需要一个 for 循环，而不需要任何递归的逻辑。
let fib = function (n){
let dp = [];
// 初始条件
dp[0] = 0;
dp[1] = 1;
// 从2开始，不断用之前记忆的值
// 填充数组
for(let i = 2; i <= n; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};运行时长如图：
我们可以看到，堆栈超出问题已经解决，这就是算法的魅力和和对应使用场景的必要性。
直接赋值：
const arr = [1,2,3,4];构造函数创建：
const arr = new Array();
const arr1 = Array();
// 创建空数组，此时等价为：
const arr = [];创建固定长度的空数组：
const arr = new Array(4);
创建固定长度的数组并每个值都确定：
// 初始化一个长度为7的数组，全部填充为1
const arr = (new Array(7)).fill(1);-
通过数组的下标，依次访问每个值
const len = arr.length; for(let i=0;i<len;i++){ console.log(arr[i],i); }
-
通过传入函数中的参数获取值和下标
forEach((item,index)=>{ console.log(item,index); })
-
map的循环和forEach差不多，只是map返回一个新数组，常常用于对原数组的批量修改等const newArr = arr.map((item,index)=>{ console.log(item,index); // 每个元素在原有基础上加一，返回值的必需的，否则新数组为空 return item +1 })
个人建议如果没有特殊需要，统一使用for循环执行遍历，因为从性能上看，for循环遍历是最快的。
二维数组就是数组中嵌套数组（每个元素都是数组）
正常的一位数组：
const arr = [1,2,3,4,5];数组结构分布：
二维数组：
const arr = [
[1,2,3,4,5],
[1,2,3,4,5],
[1,2,3,4,5],
[1,2,3,4,5],
[1,2,3,4,5]
]二维数组的结构分布：
在数学中，形如这样长方阵列排列的复数或实数集合，被称为“矩阵”。因此二维数组的别名就叫“矩阵”
使用fill填充二维数组
const arr = (new Array(7)).fill([]);
乍一看没毛病，只是在你修改数组中的某一个位置的时候，问题出现了
arr[0][0] = 1;会出现：
出现这个是因为fill的工作机制，在你传入一个参数给fill的时候，如果这个入参的类型是引用类型，那么 fill 在填充坑位时填充的其实就是入参的引用。也就是说下图中虽然看似我们在7个位置初始化了一个数组，其实这7个数组对应了同一个引用、指向的是同一块内存空间，它们本质上是同一个数组。因此当你修改第0行第0个元素的值时，第1-6行的第0个元素的值也都会跟着发生改变。
本着安全的原则，这里我推荐大家采纳的二维数组初始化方法非常简单（而且性能也不错）。直接用一个 for 循环来解决：
const len = arr.length
for(let i=0;i<len;i++) {
// 将数组的每一个坑位初始化为数组
arr[i] = []
}我们要访问二维数组，需要进行两层遍历
// 缓存外部数组的长度
const outerLen = arr.length
for(let i=0;i<outerLen;i++) {
// 缓存内部数组的长度
const innerLen = arr[i].length
for(let j=0;j<innerLen;j++) {
// 输出数组的值，输出数组的索引
console.log(arr[i][j],i,j)
}
}一维数组用 for 循环遍历只需一层循环，二维数组是两层，三维数组就是三层。依次类推，N 维数组需要 N 层循环来完成遍历。
在 JavaScript 中，栈和队列的实现一般都要依赖于数组，大家完全可以把栈和队列都看作是“特别的数组”。
-
unshift添加元素到数组头部const arr = [1,2] arr.unshift(0) // [0,1,2]
-
push添加元素到数组尾部push方法返回的是push进数组的元素个数const arr = [1,2] arr.push(3) // [1,2,3]
-
splice任意位置添加元素const arr = [1,2] arr.splice(1,0,3) // [1,3,2]
-
shift删除头部const arr = [1,2,3] arr.shift() // [2,3]
-
pop删除尾部pop方法返回的是从数组中弹出的那一个元素const arr = [1,2,3] arr.pop() // [1,2]
-
splice删除任意位置const arr = [1,2,3] arr.splice(2,1) // [1,2]
栈是一种后进先出(LIFO，Last In First Out)的数据结构。
操作元素都只从尾部开始，就实现了先进后出。
// 初始状态，栈空
const stack = []
// 入栈过程
stack.push('1')
stack.push('2')
stack.push('3')
stack.push('4')
stack.push('5')
// 出栈过程，栈不为空时才执行
while(stack.length) {
// 单纯访问栈顶元素（不出栈）
const top = stack[stack.length-1]
console.log('现在为', top)
// 将栈顶元素出栈
stack.pop()
}
// 栈空
stack // []队列是一种先进先出（FIFO，First In First Out）的数据结构。
操作元素时添加从尾部操作，删除从头部操作，类似排队。
const queue = []
queue.push('1')
queue.push('2')
queue.push('3')
while(queue.length) {
// 单纯访问队头元素（不出队）
const top = queue[0]
console.log(top,'取餐')
// 将队头元素出队
queue.shift()
}
// 队空
queue // []
链表和数组类似，它们都是有序的列表、都是线性结构（有且仅有一个前驱、有且仅有一个后继）。不同点在于，链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的。
链表可分为单向链表和双向链表：
- 单向链表：只可单向访问，只能访问到下一个结点的位置
- 双向链表：每个结点都有指向下一结点位置的指针和指向上一结点位置的指针，通过访问指针来访问到上个结点/下个结点
这个“离散”是相对于数组的“连续”来说的：
数组在内存中最为关键的一个特征，就是它一般是对应一段位于自己上界和下界之间的、一段连续的内存空间。
而链表中的结点，内存空间是不连续的。一个内容为1->2->3->4->5的链表，在内存中的形态可以是散乱如下的：
在数组中，我们可以通过遍历循环去获取每个元素的值和下标，而这在链表中是行不通的，但是在链表的每一个结点中，都包括了数据和指针。JS 中的链表，是以嵌套的对象的形式来实现的：
{
// 数据域
val: 1,
// 指针域，指向下一个结点
next: {
val:2,
next: ...
}
} 数据即这个结点的值，指针指向下一个结点的内存地址（引用类型），现在知道某一个结点的值和位置，也就知道了下一个结点的位置，通过位置获取到下一个结点的值。
要想访问链表中的任何一个元素，我们都得从头开始逐个访问下一个结点的位置，知道访问到目标结点为止。为了确保起点结点是可抵达的，我们有时还会设定一个 head 指针来专门指向链表的开始位置：
创建链表结点，我们需要一个构造函数
function ListNode(val){
this.val = val;
this.next = null;
}然后我们通过构造函数创建结点，多个结点组成了链表：
const node = new ListNode(1)
node.next = new ListNode(2)创建一个新结点，将链表中尾部结点的next指向新结点
创建一个新结点，要插入位置的上个结点的next指向新结点，新结点的next指向要插入位置的结点
插入前：
插入后：
代码表述：
// 如果目标结点本来不存在，那么记得手动创建
const node3 = new ListNode(3)
// 把node3的 next 指针指向 node2（即 node1.next）
node3.next = node1.next
// 把node1的 next 指针指向 node3
node1.next = node3要想删除链表中的某个结点，我们只需要将那个结点的上个位置的结点的next直接指向他下个结点（直接跳过本结点）：
举个🌰，将上面新加的node3删除：
node1.next = node3.next 在涉及链表的操作中，重点不是定位目标结点，而是定位目标结点的前驱结点。
一个根结点，任意多个子结点：
计算机中的树：
关于树结构：
- 树的层次计算规则：根结点所在的那一层记为第一层，其子结点所在的就是第二层，以此类推。
- 结点和树的“高度”计算规则：叶子结点高度记为1，每向上一层高度就加1，逐层向上累加至目标结点时，所得到的的值就是目标结点的高度。树中结点的最大高度，称为“树的高度”。
- “度”的概念：一个结点开叉出去多少个子树，被记为结点的“度”。比如我们上图中，根结点的“度”就是3。
- “叶子结点”：叶子结点就是度为0的结点。在上图中，最后一层的结点的度全部为0，所以这一层的结点都是叶子结点。
二叉树就是满足一下条件的树：
-
可以没有根结点，作为一棵空的树
-
如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。如下图：
注意，二叉树不能被简单定义为每个结点的度都是2的树。普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定、不能交换的。对应到图上来看，也就意味着 B 和 C、D 和 E、F 和 G 是不能互换的。
在JavaScript中，二叉树可以使用对象来定义，结构分为三部分：
- 数据域：这个结点的值
- 左侧子结点（左子树根结点）的引用
- 右侧子结点（右子树根结点）的引用
在定义二叉树构造函数时，我们需要把左侧子结点和右侧子结点都预置为空：
// 二叉树结点的构造函数
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}创建一个值为1的二叉树结点：
const node = new TreeNode(1);
以这个结点为根结点，我们可以通过给 left/right 赋值拓展其子树信息，延展出一棵二叉树。因此从更加细化的角度来看，一棵二叉树的形态实际是这样的：
以一定的顺序规则，逐个访问二叉树的所有结点，这就是遍历。根据顺序规则的不同，遍历方式有一下四种：
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历
按照实现方式不同，遍历方式又可以分为以下两种：
- 递归遍历（先、中、后序遍历）
- 迭代遍历（层次遍历）
我们都知道，在一个函数中，如果出现了在函数体中调用了自身，这就是一个递归函数。简单来说，一个函数在反复调用自己的时候，递归也就产生了。一个递归函数需要两个必需条件：
- 递归式（函数体---你要重复做什么）
- 递归边界（出口---达到什么条件时停止递归）
现在我们再来看二叉树，一个完整的二叉树应该由这三部分组成：
- 根结点
- 左子树
- 右子树
对于二叉树的遍历，就可以看做是对这三个部分的遍历，在保证“左子树一定先于右子树遍历”的前提下，有三种遍历顺序：
- 根结点=>左子树=>右子树
- 左子树=>根结点=>右子树
- 左子树=>右子树=>根结点
上面的三个遍历顺序，就对应了二叉树的先、中、后序遍历。在这三种遍历顺序中，根结点的遍历分别被安排在了开始位置、中间位置和末尾位置，所谓的“先序”、”中序“和“后序”遍历也就是指的根结点的遍历时机。
遍历顺序如图
如果有 N 多个子树，那么我们在每一棵子树中都要进行的遍历如下：
上面的二叉树结构为：
const root = {
val: "A",
left: {
val: "B",
left: {
val: "D"
},
right: {
val: "E"
}
},
right: {
val: "C",
right: {
val: "F"
}
}
};编码实现：
// 所有遍历函数的入参都是树的根结点对象
function preorder(root) {
// 递归边界，root 为空
if(!root) {
return
}
// 输出当前遍历的结点值
console.log('当前遍历的结点值是：', root.val)
// 递归遍历左子树
preorder(root.left)
// 递归遍历右子树
preorder(root.right)
}遍历顺序如图
动图解释如下：
编码实现：
// 所有遍历函数的入参都是树的根结点对象
function inorder(root) {
// 递归边界，root 为空
if(!root) {
return
}
// 递归遍历左子树
inorder(root.left)
// 输出当前遍历的结点值
console.log('当前遍历的结点值是：', root.val)
// 递归遍历右子树
inorder(root.right)
}遍历顺序如图：
动图解释如下：
编码实现：
function postorder(root) {
// 递归边界，root 为空
if(!root) {
return
}
// 递归遍历左子树
postorder(root.left)
// 递归遍历右子树
postorder(root.right)
// 输出当前遍历的结点值
console.log('当前遍历的结点值是：', root.val)
}在JavaScript中，是没有哈希表这种数据结构的，我们可以使用JavaScript的特性实现一个自己的哈希表
哈希表是一种键值对的数据结构，键是唯一的，这跟JavaScript的Object类似，Object的属性也是唯一的，属性和值的映射就和键值对一样，我们通过操作Object的属性和值模拟哈希表的键值对。
put：往哈希表中加入一个键值对get：获取一个指定键的值remove：删除指定键关联的键值对getSize：获取键值对的数量clear：清空哈希表containsKey：判断哈希表是否存在指定的值getKeys：获取哈希表中所有的键（列表）getValues：获取哈希表中所有值（列表）
// 实现一个简单的哈希表结构
function HashTable(){
this.size = 0;
this.entry = {};
// put 方法
this.put = function(key,value){
if(!this.containsKey(key)){
++this.size
}
this.entry[key] = value;
}
// get方法
this.get = function(key){
return (this.containsKey(key) ? this.entry[key] : null);
}
// remove方法
this.remove = function(key){
if(this.containsKey(key) && (delete this.entry[key])){
--this.size;
}
}
// containsKey方法
this.containsKey = function(key){
return (key in this.entry)
}
// containsValue方法
this.containsValue = function(value){
for(let key in this.entry){
if(this.entry[key] === value){
return true
}
}
return false
}
// getKeys方法
this.getKeys = function(){
return Object.keys(this.entry)
}
// getValues方法
this.getValues = function(){
return Object.values(this.entry)
}
// getSize方法
this.getSize = function(){
return this.size
}
// clear方法
this.clear = function(){
this.size = 0;
this.entry = {};
}
}复杂度是评价一个算法或者一段程序运行时效性的重要参考。
时间复杂度，即运行一段程序代码要花多长时间
我们先看这一段代码，一共会执行多少次？
function traverse(arr){
const len = arr.length;
for(let i=0;i<len;i++){
console.log(arr[i]);
}
}首先，函数体里的第一行代码，它只会被执行一次，然后是循环体里的输出函数，arr数组有多长，它就会执行多少次，然后循环体里的判断语句i < len会比递增语句多执行一次，递增语句i++将会执行n次，判断语句执行了n+1次，将总执行次数记为T(n)
T(n) = 1 + n + 1 (n+1) + n = 3n+3我们再看一个n*n的二维数组遍历：
function traverse(arr) {
const outLen = arr.length
for(let i=0;i<outLen;i++) {
const inLen = arr[i].length
for(let j=0;j<inLen;j++) {
console.log(arr[i][j])
}
}
}很明显，函数体内的第一行代码只会执行一次，而内部的输出函数因为我们是两层循环，所以将会执行 n*n = n^2次，总执行次数的计算为：
总执行次数记为T(n)
T(n) = 1 + 1 + (n+1) + n + n + n + n*(n+1) + n*n + n*n = 3n^2 + 5n + 3代码的执行次数，可以反映出到吗的执行时间。算法的事件复杂度，它反映的不是算法的逻辑代码到底被执行了多少次，而是随着输入规模的增大，算法对应的执行总次数的一个变化趋势。我们尝试对T(n)做如下处理：
- 若
T(n)是常数，那么无脑简化为1 - 若
T(n)是多项式，我们只保留次数最高的那一项，并且将其常数系数无脑改为1
// T(n) = 10;
// O(n) = 1;
// T(n) = 3n^2 + 5n +3;
// O(n) = n^2;在我们的实际操作中，遍历N维数组，需要N层循环，我们就只需要关心最内层循环体会被执行多少次就行了。我们可以看出，遍历规模为n的一位数组时，最内层的循环会执行n次，对应的时间复杂度就是O(n)；遍历规模为n*n的二维数组时，最内层循环会执行n*n次，所以时间复杂度就表示为O(n^2)
以此类推，规模为n*m的二维数组最内层循环会执行n*m次，对应的时间复杂度就是O(n*m)；规模为n*n*n的三维数组最内层循环会执行n^3次，所以时间复杂度就表示为O(n^3)
我们再看以下函数：
function fn(arr) {
const len = arr.length
for(let i=1;i<len;i=i*2) {
console.log(arr[i])
}
}这个函数的时间复杂度的计算，就要看i < len这个条件是在i递增多少次之后才不成立，假设i在以i = i*2的规则递增了x次之后，i < len不成立，我们得到：
2^x >= nx解出来，就是要大于或等于以2为底的n的对数
也就是说，只有当x小于log2n的时候，循环才会执行。在涉及到对数的时间复杂度计算的时候，底数和系数都是要被简化掉的，所以这里的时间复杂度O(n)表示为：
O(n) = logn常见的算法时间复杂度：
- 二分查找：
O(logn) - 二叉树遍历：
O(n)（每个结点只访问一次） - 有序的二维矩阵：
O(n) - 归并排序：
O(nlogn)
常见的时间复杂度按照从小到大的顺序排列，有一下几种：
| 常数时间 | 对数时间 | 线性时间 | 线性对数时间 | 二次时间 | 三次时间 | 指数时间 |
|---|---|---|---|---|---|---|
| O(1) | O(logn) | O(n) | O(nlogn) | O(n^2) | O(n^3) | O(2^n) |
空间复杂度是对一个算法在运行过程中临时占用的内存空间大小的量度。和时间复杂度相似，它是内存增长的一个趋势。
举个🌰：
function traverse(arr) {
const len = arr.length
for(let i=0;i<len;i++) {
console.log(arr[i])
}
}在整个函数中，占用内存空间的有这几个变量：arr、len、i
后面尽管咱们做了很多次循环，但是这些都是时间上的开销。循环体在执行时，并没有开辟新的内存空间，所以这个函数对内存的占用是恒定的，它对应的空间复杂度就表示为O(1)
再看下面这个🌰，我们初始化一个规模为n的数组，并且要求这个数组的每个元素的值和它的索引始终是相等的：
function init(n) {
let arr = []
for(let i=0;i<n;i++) {
arr[i] = i
}
return arr
}在这个函数中，涉及到的内存变量有：n、arr、i
注意：这里的arr并不是一个一成不变的数组。arr的大小是由输入的n来确定的，它会随着n的增大而增大、呈一个线性关系。所以这个算法的空间复杂度表示为O(n)
由此类推，加入要初始化一个规模为n*n的数组，那么它的空间复杂度就是O(n^2)