重学前端（四）-数据结构与算法
前言
最近在撸vue 和react的源码，虽然晦涩难懂，但是却发现新大陆，发现了数据结构和算法在前端的重要性，比如在react中，发现react的fiber树，对应的实际上是一个叫链表的数据结构，我们es6中新出的Map的数据结构其实就是对应字典的数据结构而Set对应的就是集合的数据结构，他是一个无序且唯一的数据结构。而在vue 中也是大量的用到栈和队列的数据结构，于是，遍寻资料，学习一番，记录如下，如有错误，请大佬指点！
学习须知
我在学习数据结构与算法时，请教了许多人，他们就告诉我直接刷题，于是我打开力扣准备开始刷题之旅，然而，刷了一阵之后发现，由于没有系统的知识体系，学得快，忘得也快，最大的感触就是不能举一反三，终于意识到，知识体系的重要性了。
于是，重新翻开大学崭新的数据结构与算法，温习一遍。
基础知识
首先我们的数据结构分那么几种，我们必须要彻底了解数据结构都有哪些，这样在遇见算法时我们才能清晰的知道应该用怎样的数据结构去解决问题。
栈
栈是一种遵从后进先出（LIFO）原则的数据结构。
如上图所示，栈顶和栈低，在上图中，我们可以清晰的看到，先入栈的数据由于被压在栈底，如果想要出栈，那么必须等前方的数字都出栈才能轮到他，于是就形成了我们的后进先出的数据结构（强调一下栈是一种数据结构）
然而在我们前端中是没有栈这种数据结构的，但是我们有万能的数组，使用它可以模拟出栈，并且还能衍生出栈的操作方法，我们知道在es标准中数组有两个标准方法push和pop其实，他们就可以表示出栈和入栈的操作方法，好，废话少说让我们开始吧！
class Stack {
constructor() {
this.stack = []
// 栈的长度
this.size = 0
}
// 入栈
push(i) {
this.stack[this.size] = i
this.size++
}
// 出栈
pop() {
if (this.stack.length > 0) {
const last = this.stack[--this.size]
this.stack.length--
return last
}
}
// 查看栈顶元素
peek() {
return this.stack[this.size - 1];
}
// 栈是否为空
isEmpty() {
return stack.length === 0;
}
// 清空栈
clear() {
this.stack = []
}
// 查看栈元素
see(){
console.log(this.stack)
return this.stack
}
}
到此为止，一个简单的前端栈的实现就完成了
而在我们前端中，我们常说的调用堆栈，其实就是使用栈的数据结构，你会发现他完全符合最先压入最后弹出
队列
队列是一种遵从先进先出原则的数据结构。
如上图所示，我们发现最先进入的数据，只能先出去，他具有先进先出的特性。然而，在js的语法中同样的没有队列的数据结构，但是我们依然可以用数据来模拟队列的数据结构，由于队列是先进先出，那么，也就是如上图所示，我们首先需要模拟原生的入队push方法，再模拟原生的shift方法，ok 废话少说开始吧！
class Queue {
constructor() {
// 创建一个队列
this.queue = []
// 队列长度
this.size = 0
}
// 入队列
push(i) {
this.queue[this.size] = i
this.size++
}
// 出队列
shift() {
if (this.queue.length === 0) {
return
}
const first = this.queue[0]
//将后面的赋值给前面的
for (let i = 0; i < this.queue.length - 1; i++) {
this.queue[i] = this.queue[i + 1]
}
this.queue.length--
return first
}
//获取队首
getFront() {
return this.queue[0];
}
//获取队尾
getRear() {
return this.queue[this.size - 1]
}
// 清空队列
clear() {
this.queue = []
}
// 查看队列元素
see() {
console.log(this.queue)
return this.queue
}
}
到此为止一个简单的队列就实现了
其实，在前端中我们的异步事件就完全符合队列的数据结构，先进先出，学到这里，你还觉的前端不需要学习数据结构吗？
链表
用链式存储的线性表统称为链表
上面就是链表的定义，有没有感觉晦涩难懂，其实他本质上就是一个多元素组成的列表，只不过他的元素存储不连续，需要再用next指针关联。这就是一个链表的结构，无图无真相，上图
上图就是一个简单的链表结构，就是这么的朴实且无华，然而，在日常的使用中，人们发现链表的形态也是多种多样的，于是就给他做了单向链表，和双向链表的区分
单向链表
如上图所示，就是一个简单的单项链表，单向链表(单链表)是链表的一种，它由节点组成，每个节点都包含下一个节点的指针，下图就是一个单链表，表头为空，表头的后继节点是"结点10"(数据为10的结点)，"节点10"的后继结点是"节点20"(数据为10的结点)
双向链表!
如上图所示，双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
说完这些概念，我们发现前端中也没有链表这种数据结构，然而，我们可以用对象来实现一个简单的链表结构，
var a = { name: '大佬1' }
var b = { name: '大佬1' }
var c = { name: '大佬1' }
var d = { name: '大佬1' }
var e = { name: '大佬1' }
// 建立链表
a.next=b
b.next=c
c.next=d
d.next=e
如此一来我们的链表就建立完成，这是有人就会问了，链表的数据结构到底有啥好处呢，还没有数组方便呢？ 我们发现，链表的存储不是连续的，他们通过next去关联，所以我们执行删除的时候，只需要去改变next指针，便可自然而然的执行删除操作，但是，你如果想在数组中去删除，你会发现，相当的麻烦
当然，既然链表是一种数据结构，那么，我们一定会有相应的操作，下面我们看看都有啥吧
// 遍历链表
let p = a
while (a) {
console.log(a)
p = a.next()
}
// 插入链表
const f={name:'大佬1'}
//模拟在a元素后插入
a.next=f
f.next=b
// 删除链表
// 在删除f
a.next=b
上文中我们模拟了在js中链表的遍历，插入以及删除，如此发现，其实链表的数据结构还没有我们操作数组难呢
集合
集合是由一组无序但彼此之间又有一定相关性的成员构成的, 每个成员在集合中只能出现一次.他是一个无序且唯一的数据结构
在之前的数据结构中，前端都没有对应的实现，终于的，我们的集合在前端中有了自己的集合构造器，他就是大名鼎鼎的-Set，通常的我们用它来执行数组去重，接下来我们来看看他都有什么魔力吧！
Set
set是es6新出的一种数据结构，Set对象是值的集合，你可以按照插入的顺序迭代它的元素。 Set中的元素只会出现一次，即 Set 中的元素是唯一的。接下来让我们来看看set的基本操作
// 创建一个 集合
var s = new Set([1, 2, 3, '3', 4]);
//添加一个key
s.add(5);
//重复元素在Set中自动被过滤
s.add(5);
console.log(s);//Set {1, 2, 3, 4,5}
//删除一个key
s.delete(2);
// 判断是否有这个元素
s.has(3)
console.log(s);//Set{1, 3, "3", 4, 5}//注意数字3和字符串'3'是不同的元素。
既然是集合，那么我们怎么能没有求交集，并集呢？然而比较可惜的是，set 并没有给我们提供对应的操作方法，不过，不要紧，我们有数组，可以利用数组求出交集
// 并集
const arr1=new Set([1,2,4])
const arr2=new Set([2,3,4,5])
new Set([...arr1, ...arr2])
//交集
const arr1=new Set([1,3,4,6,7,9])
const arr2=new Set([2,3,4,5,6,7])
const arr=new Set([...arr1].filter((item)=>{arr2.has(item)}))
字典
字典 是一种以键-值对形式存储唯一数据的数据结构
那你就会说了，这玩意不就是个对象吗？拿他和对象有啥区别呢？我们先来看怎样使用，估计你就能一眼看出区别了，在es6中，我们可以用Map这个构造器去创建一个字典
Map
废话少说，直接上代码
// 创建一个字典
const map=new Map([
['a',1],
['b',2]
]);
console.log(map);
上图所示，就是我们的字典的数据结构，你发现他的原型不同，并且存储结构也不同，那么有的同学又问了，都有了对象了，而且能实现Map的功能，为啥还要开发一个Map，这里我的理解是，为了让对象的功能和作用更纯粹，从而使得这门语言规范法，标准化，以及打开变函数式编程的大门，接下来，我们来简单的使用字典的增删改查
// 字典的增删改查
// 获取长度
console.log(map.size);
// 增加key 可以是个非原始类型
console.log(map.set([1,2],''));
map.set('name','李丽').set('age',18);
// 查询
console.log(map.get('name'));
// 删除
console.log(map.delete('name'));
// 是否含有
console.log(map.has('name'));
说了这么多，我们来看看字典的用处吧比如：求出数组中三个最大的三个数的下标
// 求最大的三个数 并且求出下标
// =======解题思路=======
//1、采用的是暴力求解法，那么我们可以利用字典的特点存储最大的三个值
//2、还有种比较好理解的办法利用排序，在之前文章里写过
function maxThree(arr) {
var i = 0;
var j = 0;
var tmp = arr[0]
var v = 0
var b = new Map()
// 遍历三次分别找到最大的三个值
while (i < 3) {
while (j < arr.length) {
if (tmp < arr[j] && !b.has(j)) {
tmp = arr[j]
v = j
}
j++
}
b.set(v, tmp)
i++
j = 0
tmp = 0
}
// console.log(b)
}
maxThree([1, 3, 4, 5, 6, 7, 9, 1, 1, 9, 2, 8, 3, 4, 5,])
图
图是一种网络结构的抽象模型，它是一组由边连接的顶点组成
是不是有点蒙，接下来我们直接上一个"图"
如上图所示，由一条边连接在一起的顶点称为相邻顶点，A和B是相邻顶点，A和D是相邻顶点，A和C是相邻顶点......A和E是不相邻顶点。一个顶点的度是其相邻顶点的数量，A和其它三个顶点相连，所以A的度为3，E和其它两个顶点相连，所以E的度为2......路径是一组相邻顶点的连续序列，如上图中包含路径ABEI、路径ACDG、路径ABE、路径ACDH等。简单路径要求路径中不包含有重复的顶点，如果将环的最后一个顶点去掉，它也是一个简单路径。例如路径ADCA是一个环，它不是一个简单路径，如果将路径中的最后一个顶点A去掉，那么它就是一个简单路径。如果图中不存在环，则称该图是无环的。如果图中任何两个顶点间都存在路径，则该图是连通的，如上图就是一个连通图。如果图的边没有方向，则该图是无向图，上图所示为无向图，反之则称为有向图，
上图所示，就是一个有向图，他们其实本质就是为了表示任何的二元关系，并且给他抽象成一个图的数据结构，比我们的地铁图，就可以抽象成图的数据结构，而我们的两个地铁站之间就是只能用一条线链接，这就是表示多个二元关系
那么在我们的js中，同样的没有图我们同样的可以使用数组和对象来表示一个图，如果用数组去表示，就会给起一个名字叫做邻接矩阵，而我们如果将数组和对象混用那么就起个名字叫做邻接表，本质上就是表示上的不同
邻接矩阵
如上图所示我们就将一个图抽象成了邻接矩阵表示，其实本质就是用一个二维数组去表示连接点之间的关系，好，废话少说，我们接下来用邻接矩阵代码去表示一个简单的图
比如说我们要用邻接矩阵去表示如下图
var matrix=[
[0,1,0,0,0],
[0,0,1,1,0],
[0,0,0,0,1],
[1,0,0,0,0],
[0,0,0,1,0]
]
如上代码所示，其实他的本质就是在横向和纵向同时都有A、B、C、D、E 当横向的与纵向的形成关联时，则修改当前对应项为1，如果就可以用矩阵的形式表达各个顶点之间的关系，好了，到此邻接矩阵表示法，到此为止，其实难点并不是画一个邻接矩阵，而是将抽象的业务逻辑转化成一个邻接矩阵去解决问题，比如在电商界大名鼎鼎的sku，由于业务复杂度较高，所有，我们写的算法往往业务逻辑极其复杂，这时邻接矩阵就能发挥威力 有兴趣可以看看大佬的分分钟学会前端sku算法（商品多规格选择）
邻接表
说起邻接表，表示起来就比邻接矩阵直观多了，邻接矩阵相当的抽象，那么上图我们怎样用邻接表去表示呢? 由于邻接表比较简单，使用用例创建，
class Graph {
constructor() {
this.vertices = []; // 用来存放图中的顶点
this.adjList = new Map(); // 用字典的数据结构来存放图中的边
}
// 向图中添加一个新顶点
addVertex(v) {
if (!this.vertices.includes(v)) {
this.vertices.push(v);
this.adjList.set(v, []);
}
}
// 向图中添加a和b两个顶点之间的边
addEdge(a, b) {
// 如果图中没有顶点a，先添加顶点a
if (!this.adjList.has(a)) {
this.addVertex(a);
}
// 如果图中没有顶点b，先添加顶点b
if (!this.adjList.has(b)) {
this.addVertex(b);
}
this.adjList.get(a).push(b); // 在顶点a中添加指向顶点b的边
}
}
let graph = new Graph();
let myVertices = ['A', 'B', 'C', 'D', 'E'];
myVertices.forEach((v) => {
graph.addVertex(v);
});
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('E', 'D');
graph.addEdge('D', 'A');
console.log(graph);
如图，邻接表也完整映射出图的关系
树
在计算机科学中，树是一种十分重要的数据结构。树被描述为一种分层数据抽象模型，常用来描述数据间的层级关系和组织结构。树也是一种非顺序的数据结构。
如上图所示，这就是一个树形象展示，而在我们前端中，其实是和树打交道最多的了，比如dom树、级联选择、属性目录控件这是我们最常听见的名词了吧，他其实就是一个树的数据结构。在我们前端js中同样的也没有树的数据结构。但是我们可以用对象和数组去表示一个树。
var tree={
value:1,
children:[
{
value:2,
children:[
{
value:3
}
]
}
]
}
如上所示，我们就简单的实现了一个树的数据结构，但是你觉得这就够了吗？他是远远不够的，在我们的树中，有着很多被大众普遍接受的算法，叫做深度优先遍历（DFS），和广度优先遍历(BFS)，首先我们来一个dom 树，然后再来分析它
如上图所示，我将dom转化成了树形结构
深度优先遍历（DFS）
深度优先遍历顾名思义，就是紧着深度的层级遍历，他是纵向的维度对dom树进行遍历，从一个dom节点开始，一直遍历其子节点，直到它的所有子节点都被遍历完毕之后再遍历它的兄弟节点，如此往复，直到遍历完他所有的节点
他的遍历层级依次是：
div=>ul=>li=>a=>img=>li=>span=>li=>p=>button
用js 代码表示如下：
//将dom 抽象成树
var dom = {
tag: 'div',
children: [
{
tag: 'ul',
children: [
{
tag: 'li',
children: [
{
tag: 'a',
children: [
{
tag: 'img'
}
]
}
]
},
{
tag: 'li',
children: [
{
tag: 'span'
}
]
},
{
tag: 'li'
}
]
},
{
tag: 'p'
},
{
tag: 'button'
}
]
}
var nodeList = []
//深度优先遍历算法
function DFS(node, nodeList) {
if (node) {
nodeList.push(node.tag);
var children = node.children;
if (children) {
for (var i = 0; i < children.length; i++) {
//每次递归的时候将 需要遍历的节点 和 节点所存储的数组传下去
DFS(children[i], nodeList);
}
}
}
return nodeList;
}
DFS(dom, nodeList)
console.log(nodeList)
结果也相当的一致
广度优先遍历（BFS）
所谓广度优先遍历，也是同样的道理，就是紧着同级的遍历，该方法是以横向的维度对dom树进行遍历，从该节点的第一个子节点开始，遍历其所有的兄弟节点，再遍历第一个节点的子节点，完成该遍历之后，暂时不深入，开始遍历其兄弟节点的子节点 他的遍历层级依次是：
div=>ul=>p=>button=>li=>li=>li=>a=>span=>img
用js 代码表示如下：
function BFS(node, nodeList) {
//由于是广度优先，for循环不是很优雅，我们可以使用队列来解决
if (node) {
var q = [node]
while (q.length > 0) {
var item = q.shift()
nodeList.push(item.tag)
if (item.children) {
item.children.forEach(e => {
q.push(e)
})
}
}
}
}
BFS(dom, nodeList)
console.log(nodeList)``
那么结果也显而易见
在我们之前的代码中，描述的都是多叉树，而在数据结构中，还有一个相当重要的概念，叫做二叉树
二叉树
二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。
说了这么多概念，那么二叉树到底是啥？我们来看一张图，相信就能胜过千言万语
如图所示长这样就是二叉树
以上就是二叉树的概念，但是，在前端中，目前我还没有见到二叉树的应用（如有大佬知道请告知），但是仍然不妨碍我们来学习他，而在二叉树中最有名的当属先序遍历，中序遍历，以及后序遍历
那么在我们前端中二叉树应该怎么表示呢？我们可以用object来表示一个二叉树
const bt = {
val: 1,
left: {
val: 2,
left: {
val: 4,
left: null,
right: null,
},
right: {
val: 5,
left: null,
right: null,
},
},
right: {
val: 3,
left: {
val: 6,
left: null,
right: null,
},
right: {
val: 7,
left: null,
right: null,
},
},
}
以上数据结构就是一个简单的二叉树，他会有当前节点的值，以及一个左子树，和右子树，接下来，才是重点部分，二叉树的创建以及遍历
创建二叉树
// arr=[6,5,6,8,9,1,4,3,6] 将数组根据下标为0的大小转换成二叉树
arr = [6, 5, 6, 8, 9, 1, 4, 3, 6]
class BinaryTreeNode {
constructor(key) {
// 左节点
this.left = null;
// 右节点
this.right = null;
// 键
this.key = key;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
insert(key) {
const node = new BinaryTreeNode(key)
if (this.root === null) {
this.root = node
} else {
this.insertNode(this.root, node)
}
}
// 抽离递归比较部分逻辑
insertNode(node, newNode) {
if (node.key < newNode.key) {
if (node.left) {
this.insertNode(node.left, newNode)
} else {
node.left = newNode
}
} else {
if (node.right) {
this.insertNode(node.right, newNode)
} else {
node.right = newNode
}
}
}
}
const tree = new BinaryTree();
arr.forEach(key => {
tree.insert(key)
});
console.log(tree)
中序遍历
中序遍历(inorder)：先遍历左节点，再遍历自己，最后遍历右节点，输出的刚好是有序的列表
中序遍历 有递归版本和 非递归的版本，此处使用递归版本
// 是对象中的一个方法
inorderTransverse(root, arr) {
if (!root) return;
this.inorderTransverse(root.left, arr);
arr.push(root.key);
this.inorderTransverse(root.right, arr);
}
// 使用
const arrTransverse = []
tree.inorderTransverse(tree.root, arrTransverse)
console.log(arrTransverse)
先序遍历
先序遍历(preorder)：先自己，再遍历左节点，最后遍历右节点
preorderTransverse(root, arr) {
if (!root) return;
arr.push(root.key);
this.preorderTransverse(root.left, arr);
this.preorderTransverse(root.right, arr);
}
后序遍历
后序遍历(postorder)：先左节点，再右节点，最后自己
// 由于后序遍历的非递归版本比较巧妙，我们使用非递归版本
postorderTransverse(root, arr) {
// 创建一个栈
var stack = [];
// 将根节点压入栈顶
stack.push(root);
while (stack.length > 0) {
let node = stack.pop();
// 利用unshift按照顺序压入数组
arr.unshift(node.key);
if (node.left) {
stack.push(node.left);
}
if (node.right) {
stack.push(node.right);
}
}
}
// 调用
const arrTransverse = []
tree.postorderTransverse(tree.root, arrTransverse)
真题演练
本题来自力扣226题，并且是一个火爆的面试题，原因是这是一道Homebrew包管理工具的作者，去谷歌面试写不出来的题
// 1
// 2 3
// 4 5 6 7
// 将如上二叉树翻转过来
//===== 解题思路======
//1、如果想翻转二叉树，使用分治思想是一种比较好理解的方式
//2、主要就是递归每一层，递归到当前层只需要交换当前层的二叉树即可
function invertTree(bt) {
if (!bt) {
return bt
}
//利用解构赋值交换两个数
[bt.left, bt.right] = [invertTree(bt.right), invertTree(bt.left)];
return bt
}
console.log(invertTree(bt))
堆
堆是什么? 在前端中甚至都很少提过这个概念，其实，堆是一种特殊的完全二叉树
在之前的树中我们介绍了树，同样介绍了二叉树，那什么是完全二叉树呢？
如上图所示，就是一个完全二叉树，也可以叫满二叉树（有的文献定义满二叉树不是完全二叉树，没统一的标准和规范定义），但是完全二叉树不一定都是满二叉树比如
上图中，就是一个完全二叉树，却不是一个满二叉树,那完全二叉树的定义是啥呢？
若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。
说白了就是二叉树的每层子节点必须填满，最后一层如果不是满的，那么必须只缺少右边节点，那么我们又说，堆是一中特殊的完全二叉树，那么他又什么特点呢？
- 所有的节点都大于等于或者小于等于它的子节点
- 如果每个节点都大于等于它的子节点是最大堆
- 如果每个节点都小于等于它的子节点是最小堆
那么在js需要使用数组来表示一个堆，为啥呢？我的理解是由于堆是一个完全二叉树，他的每个节点必须填满，那么每一层就能在数组中找到固定的位置，这样的话，就不需要对象了
接下来有人又会问了，堆有啥用，这么复杂，其实我我们看堆的结构就能发现，堆的时间复杂度是O(1) 它能够快速找到堆中的最大值和最小值，接下来我们手写一个实践一个最小堆类吧
class MinHeep {
constructor() {
this.heap = []
}
// 插入方法
insert(val) {
this.heap.push(val)
this.shiftUP(this.heap.length - 1)
}
// 交换方法
swap(i, v) {
var temp = this.heap[i]
this.heap[i] = this.heap[v]
this.heap[v] = temp
}
// 上移方法
shiftUP(index) {
if (index === 0) { return }
var preIindex = this.getParentIndex(index)
if (this.heap[preIindex] > this.heap[index]) {
this.swap(preIindex, index)
}
}
getParentIndex(i) {
// 求商的方法
return (i - 1) >> 1
}
}
var h=new MinHeep()
h.insert(3)
h.insert(1)
h.insert(2)
h.insert(7)
h.insert(4)
console.log(h.heap)
如此，我们就实现了最小堆，打印数组来看，你就会发现是，堆顶元素一定是最小的
时间复杂度空间复杂度
相信很多人在刷算法的时候，听到最多的一个词就是时间复杂度和空间复杂度，那么他到底是什么呢？
首先我们来论一论算法到底是什么？算法就是操作数据、解决程序问题的一组方法，那么既然是一组方法，他就有好的方法，和坏的方法，于是人么就发明了两个维度去计算好坏，一个就是时间维度，一个就是空间维度
时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。
简而言之，就是你使用的for循环越多，那么你的时间复杂度就越大，你声明的变量越多那么你的空间复杂度就越大。你以为这就够了吗？贴心的大佬们还总结了一套关于时间复杂度和空间复杂度的表示方法。
表示方法
目前行业中公认叫做「 大O符号表示法 」什么意思呢？举个例子
var a=1
a++
上述代码中，我们发现并并没有for循环 他的执行步骤也不随着某个变量的变化而变化，那么他就叫做O(1)，其实计算时间复杂度有一套比较无法的公式，我们在此不在赘述有兴趣请移步大佬房间算法的时间与空间复杂度（一看就懂）
我们只需记住时间复杂度量级有：
- 常数阶O(1)
- 对数阶O(logN)
- 线性阶O(n)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K次方阶O(n^k)
- 指数阶(2^n)
从上之下的时间复杂度越来越大，接下来来举几个例子，理解一下
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
我们发现他的时间是随着n的变化而变化 那么他的时间复杂度就是O(n)
int i = 1;
while(i复制代码由于i每次都是倍数递增 那么他的循环次数就会比n小，那么他的时间复杂度就为(logN) 那么以此类推如果如果循环套循环就是平方阶
空间复杂度度就比较简单了，空间复杂度比较常用的有：O(1)、O(n)、O(n²)， 说白了就是你声明的变量多少，比如
//O(1)
var a=1
a++
// 声明数组，有n个元素O(n)
var a=new Array(n)
高级思想
看完了基础知识，细再来盘点一下高级思想
排序算法
我们算法中，排序算法首屈一指，也是面试重灾区，很多人都挂在上面，其实排序算法理清楚以后相当简单，也就分为那么几种冒泡排序、选择排序、插入排序、归并排序、快速排序、搜索排序 等
冒泡排序
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 3、针对所有的元素重复以上的步骤，除了最后一个。 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
function bubble(arr){
let tem = null;
//外层i控制比较的轮数
for(let i=0;iarr[j+1]){
//当前项大于后一项,交换位置
tem = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tem;
}
}
}
return arr
}
由于冒泡排序有两个嵌套循环，所以他的时间复杂度为O(n²)，由于这个时间复杂度相当的高，所以在排序算法中，冒泡排序属于性能较差的所以工作中基本用不到，只是在面试中使用
选择排序
1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 3、重复第二步，直到所有元素均排序完毕。
//先选择出最小的值组个比较调换位置
function selectSort(arr){
let length = arr.length;
for(let i=0;iarr[j]){
min = j
}
}
if(min!=i){
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
return arr
}
选择排序我们发现他也是两个for循环，那么相应的他也是O(n²)，性能较差
插入排序
1、从第二个数字往前比。 2、比他大的往后排，以此类推直接排到末尾
function insertSort(arr) {
let length = arr.length;
for(let i = 1; i < length; i++) {
let temp = arr[i];
let j = i;
for(; j > 0; j--) {
if(temp >= arr[j-1]) {
break; // 当前考察的数大于前一个数，证明有序，退出循环
}
arr[j] = arr[j-1]; // 将前一个数复制到后一个数上
}
arr[j] = temp; // 找到考察的数应处于的位置
}
return arr;
}
// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10]
console.log(insertSort(arr));
插入排序我们发现他也是两个for循环，那么相应的他也是O(n²)，性能较差
归并排序
1、把数组劈成两半，在递归的对子数组进行劈开的操作，知道分成一个个单独的数 2、把两个数组合并成有序数组，在对有序数组进行合并直到全部子数组合并为一个完整数组
function mergeSort(arr) {
// 劈开数组
if (arr.length === 1) { return arr }
const mid = Math.floor(arr.length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid, arr.length)
// 递归
const orderLeft = mergeSort(left)
const orderRight = mergeSort(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
}
var arr = [1, 4, 6, 7, 9, 5]
console.log(mergeSort(arr))
由于分的操作是一个递归，并且是给劈成两半那么他的时间复杂度就是O(logN)由于合并是一个while 的循环那么总体的时间复杂度就是O(nlogN) ，如此一来归并排序就达到了可用程度，于是大名鼎鼎的火狐浏览器的sort排序用的就是归并排序这个算法。
快速排序
1、首先需要分区，从数组送任意选择一个基准，然后将前后的值跟跟基准去比较，如果比基准小，那么放入左边数组，否则放入右边数组 2、递归的对子数组进行分区知道最后和合并排序号的子数组
var arr = [2, 4, 3, 5, 1]
function quickSort(arr) {
if (arr.length === 1 || arr.length === 0) { return arr }
const left = [], right = []
// 找到基准,暂时取下标0
const mid = arr[0]
// 注意由于0被取了，从1开始
for (let i = 1; i < arr.length; i++) {
if (arr[i] < mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
// 递归
console.log(left, right)
return [...quickSort(left), mid, ...quickSort(right)]
}
console.log(quickSort(arr))
看完快速排序的代码，是不是发现他跟归并排序很像，没错，的思路确实很像，都是分治思想，同样的他们的时间复杂度也都是O(nlogN) ，并且谷歌浏览器的sort排序用的就是快速排序,那说了这么多，他们有什么区别呢?
区别就是进行分组的策略不同，合并的策略也不同。归并的分组策略：是假设待排序的元素存放在数组中，那么把数组前面的一半元素作为一组，后面一半作为另一组。而快速排序则是根据元素的值来分的，大于某个值的元素一组，小于某个值的元素一组。
快速排序在分组的时候已经根据元素的大小来分组了，而合并时，只需要把两个分组合并起来就可以了，归并排序则需要对两个有序的数组根据大小合并
搜索算法
说完排序算法，我们再来鼓捣鼓捣搜索，搜索也是我们面试的高频考点，虽然工作中基本用不上，但是为了装逼，怎么能不会呢？接下来我们来看搜索都有那些？常用的一般就两种顺序搜索、二分搜索
顺序搜索
顺序搜索呢是一个非常低效的搜索方式，主要思路就是遍历目标数组，发现一样就返回 ，找不到就返回-1
// 挂载原型上不用传两个值
Array.prototype.sequentialSearch = function(item) {
for(let i = 0; i < this.length; i+=1) {
if(this[i] === item) {
return i;
}
}
return -1;
};
const res = [1,2,3,4,5].sequentialSearch(3)
console.log(res);
我们发现顺序搜索，其实就是一个单纯的遍历，那么他的时间复杂度就是O(n)
二分搜索
二分搜索顾名思义，就是给数组劈开一半然后查找，如此一来就减少了数组查找次数，大大提高了性能
他首先从数组中间开始，如果命中元素那么就返回结果，如果未命中，那么就比较目标值和已有值的大小，若查找值小于中间值，则在小于中间值的那一部分执行上一步操作，反正一样，但是必须有一个前提条件，数组必须是有序
Array.prototype.binarySearch=function( key) {
var low = 0;
var high = this.length - 1;
while (low <= high) {
var mid = parseInt((low + high) / 2);
if (key === this[mid]) {
return mid;
}
else if (key < this[mid]) {
high = mid + 1;
}
else if (key > this[mid]) {
low = mid - 1;
}
else {
return -1;
}
}
}
var arr = [1,2,3,4,5,6,7,8];
console.log(arr.binarySearch(3));
由于每次搜索范围都被缩小一半，那么他的时间复杂度就是O(logN)
分治思想
分而治之是什么呢？
分而治之是算法设计中的一种方法，或者思想
他并不是一种具体的数据结构，而是一种思想，就相当与在我们编程中的范式，比如说我们编程中有aop （切面编程）、oop（对象编程）、函数式编程、响应式编程，分层思想等，那么，我们的算法思想和编程思想的地位是一致的，可见他有多么重要，要归正传！分而治之到底是什么？
他其实就是将一个待解决的问题分解成多个小问题递归解决，再将结果合并以解决原来的问题
其实分治思想我们之前已经见过了，我们的归并排序和快速排序都是典型的分而治之的应用
动态规划
动态规划和分而治之类似，也是算法设计中的一种方法，同样的他也是将一个问题分解成相互重叠的子问题，通过去求解子问题，来达到求解原来的问题的目的
看到这里你是不是觉得跟分治思想一样，其实他们有区别的，区别呢就是在分解这块，分治思想是将问题分解成相互独立的子问题，他们彼此是没有重叠的，而动态规划则是分解成相互重叠的子问题，他们相互之间是有关联的，举个例子，拿出来经典的斐波那契数列，他就是动态规划的典型应用
斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34
接下来我们就来看看这个数列
如上图所示，他是不是有一个规律 0+1=1、1+1=2、1+2=3....如此往复，我们就可以总结出来一个公式
我们可以发现他的当前元素和前两个元素有着特殊的关联，我们给这种关联定义成一个函数F,么我们是不是就可以总结出来F(n)=F(n-1)+F(n-2)
如此一来我们就用一个关联的公式去去求出所有的斐波那契数列的值，这就是斐波那契数列的典型应用，其实啊，波那契数列在数学和生活以及自然界中都非常有用，在此我就不深入研究了（主要我也到这了，在深入露馅），如有兴趣请移步 斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？
真题演练
接下来，我们来一道力扣和面试的经典问题---爬楼梯问题
当前题来自力扣70题
//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。
// 示例
// 输入： 2
// 输出： 2
// 解释： 有两种方法可以爬到楼顶。
// 1. 1 阶 + 1 阶
// 2. 2 阶
// =======分析=========
// 首先我们假设只有3阶，那么我先定义好，我最后一步可以是两阶，也可能是一阶，
// 如果最后一步是两阶,我们就能知道之前就只有一种方法才能达到最后一步是两阶梯
// 如果最后一步是一阶我们就是知道之前有两种方法可以到达最后一阶梯
// 由于我们的最后一步的阶梯数定死了，所以，他的阶梯数量就是之前的方法之和
// 如此我们就可以推导出f(n)=f(n-1)+f(n-2) 公式
var climbStairs = function (n) {
// 由于我们的公式是f(n)=f(n-1)+f(n-2),所有当n小于2的时候我们直接返回，兼容边界条件
if (n < 2) { return 1 }
// 我们先定义初始的能求值的数组,下标0为1是由于我们只有一阶的时候也只有一种方法
const dp = [1, 1]
//套用公式
for (let i = 2; i < n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
// 返回当前阶梯的方法
return dp[n]
};
贪心算法
贪心算法也是算法设计中的一种方法，他是通过每个阶段的局部最优选择，从而达到全局最优
然后事实往往事与愿违，虽然都是局部最优选择，但是结果却不一定最优，但是一定比最糟好。正是由于永远不会命中下下签，而且看着还是上上签，使得的贪心算法这种设计思路留存到了今天。
ok，接下来举个例子，我们有1，2，5三种面值硬币，现在要求是我们使用最少的面值硬币来凑成11块钱，那如果使用贪心算法，我们为了使用的硬币最少，上来是不是需要选个5，接着在选个5，最后选个1，如此一来我们只需要三个硬币就能凑齐11块钱，当然在这种情况下，他就是最优解，那么如果我们给硬币换一下，我们需要1，3，4三种面值硬币，我们需要凑够6块钱，如果按照贪心算法，那么 组合就是4+1+1， 然而实际的最优解确实3+3只需要两个就可以了。
真题演练
当前题来自力扣122题
//定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
// 举例输入: [7,1,5,3,6,4] 输出: 7
//解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
//随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。S
//======= 解题思路 =========
// 1、由于我们在开始之初就能拿到股票的走势数组，那么也就是我们已知股票的结果
// 2、既然已知股票结果，那么利用贪心算法的原则，我们只考虑局部最优解
// 3、只需要遍历整个数组发现是上涨的交易日，我们就进行买卖操作，下降的则不动，这样永远不会亏损
// 4、使用贪心算法的思路就是不管怎样，我不能赔钱，这样做的好处就是容易理解，如果使用动态规划，还要总结公式
var maxProfit = function (prices) {
var profit = 0
for (var i = 1; i < prices.length; i++) {
tmp = prices[i] - prices[i - 1]
//只有上涨我才买卖
if (tmp > 0) {
profit += profit
}
}
return profit
};
回溯算法
回朔算法也是算法设计当中的一种思想，是一种渐进式寻找并构建问题解决方式的一种策略
基本思路就是找一条可能的路去走，如果走不通，回到上一步，继续选择另一条路，知道问题解决，回朔算法是一种暴力求解法，有着一种试错的思想，因为其简单粗暴而闻名，故而通常的也被称为通用求解法。
举个例子，我们在上学的时候都会遇见全排列问题，就是将1，2，3 用不同的顺序去排列不能重复，然后让求出有多少种排列方式，那么这就是一道典型的用回朔算法思想去解决的问题。
解题思路
1、用递归模拟所有的情况
2、遇到包含重复元素的情况，就返回上一步（官话叫做回溯）
3、搜集并返回所有的没有重复的顺序
//给定一个 没有重复 数字的序列，返回其所有可能的全排列。
//输入: [1,2,3]
//输出:
//[
//[1,2,3],
//[1,3,2],
//[2,1,3],
//[2,3,1],
//[3,1,2],
//[3,2,1]
//]
//=========题目解析===========
//1、采用回溯算法求解
//2、将不重复数字一次放入数组的每个位置，如果满足条件，取出来，否则回溯寻找下一组
//3、使用递归实现回溯思路
const permute = (nums) => {
const res = [];
var dfs = function (path) {
if (path.length === 3) { res.push(path); return }
nums.forEach(element => {
if (path.includes(element)) { return }
// 多层递归实现回溯
dfs(path.concat(element))
});
}
dfs([])
console.log(res)
};
permute([1, 2, 3])
一些套路
滑动窗口、双指针
本题来自力扣第三题
// 无重复最长子串
//输入: s = "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//=======解题思路========
// 1、 这种题目是需要有解提套路的，比如，使用双指针，比如使用滑动窗口
var lengthOfLongestSubstring = function (s) {
var l = 0, r = 0, max = 0;// 建立两个指针先指向下标0
const mapObj = new Map()
while (r < s.length) {
// 两层判断防住重复元素不在滑动窗口内的情况
if (mapObj.has(s[r]) && mapObj.get(s[r]) >= l) {
l = mapObj.get(s[r]) + 1
}
max = Math.max(r - l + 1, max)
mapObj.set(s[r], r)
r++
}
console.log(max)
};
lengthOfLongestSubstring('djcqwertyuhjjkkiuy')
善于利用Map
本题来自力扣第一题 本题梦想开始的地方，初始看到本题第一反应就是暴力求解法，两层遍历，然而参考别人的套路发现使用Map直接能给时间复杂度降到O(n)，果真自古套路得人心
//给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
//你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
//给定 nums = [2, 7, 11, 15], target = 9
//因为 nums[0] + nums[1] = 2 + 7 = 9
//所以返回 [0, 1]
//=======解题思路=========
//1、 本题有暴力解法和非暴力解法
//2、 非暴力解法如果不是有人提拔，一般人很难想到
//3、 我们需要想象我们找到目结果就是凑对，相当于婚介所找对象
//4、 思路就是来的元素全部存档，当有别的元素进来时，在已存档的元素中去凑出目标结果
var twoSum = function (nums, target) {
var obj = new Map()
nums.forEach((item, i) => {
// 如果找到返回
if (obj.has(nums[i])) {
console.log([obj.get(nums[i]), i])
} else {
// 记录对象,并存储下标
obj.set(target - nums[i], i)
}
})
};
twoSum([2, 7, 11, 15], 18)
快慢指针
本题来自力扣第141题 环形链表
本题是对对我影响比较大的题，他很大程度上改变了我的想法和观念，让我明白，想要学好算法，就得考死记硬背，记住套路，真正的算法能力全是实打实练出来的
// 判断是否是环形链表
//输入：head = [3,2,0,-4], pos = 1
//输出：true
//解释：链表中有一个环，其尾部连接到第二个节点。
//========解题思路==========
//1、在我最初的时候也是暴力求解法也是正常人的思维所能想到的
//2、历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。
//3、然而我看了大佬们的清奇的解题思路震惊了，估计想几天也想不到
//4、他们使用的就是快慢指针其实也是双指针
//5、思路就是建立两个指针，一个每次走两个next，一个每次走一个next ，如果最后两个相遇，说明一定是环形链表
/**
* @param {ListNode} head
* @return {boolean}
*/
var head = {
val: 3
}
var head1 = {
val: 2
}
var head2 = {
val: 0
}
var head3 = {
val: -4
}
head.next = head1
head1.next = head2
head2.next = head3
// head3.next = head1
var hasCycle = function (head) {
var slow = head
var fast = head
// 如果是环形指针就用户按递归下去直到retrun 跳出函数
// 如果不是环形指针就会有尽头，这是最巧妙的地方
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
// 表示相遇了，返回环形指针
if (slow == fast) {
console.log(true)
return true
}
}
console.log(false)
return false
};
hasCycle(head)
思虑清奇的套路题暂时到这，后续刷到慢慢更新
最后
断断续续一个月算法的学习心得终于写完了，以上是本人的学习算法的方法，首先了解基本的数据结构知识，再去有目的性的刷相关题目，这样数据结构和算法的体系算是印在我的脑海中了，本以为能在力扣大杀四方了，没想到，还是处处碰壁，终于明白，自古套路得人心是，想要将算法攻克，没有速成办法，他就像背单词，今天你看懂了，可能明天就忘了，想要掌握算法，只有四个字---唯手熟尔，也就是你见的多了，自然就会了，因为我们正常人的思维，是远远想不到这些解题套路的，唯有看的多了，才能举一反三，以后的路还很长，写此文章只为记录探索过程，以及引起还未入门同志的兴趣，不对之处望大佬批评指正，路漫漫，其修远兮，大家加油！