前端js写数据结构与算法

1、什么是数据结构与算法

数据结构：是指数据对象中数据元素之间的相互关系。包括集合结构、线性结构、树形结构、图形结构。

算法：解决问题的思路。

2、时间复杂度

1.是什么?

执行当前算法所“花费的时间”

2.干什么?

在写代码的过程中，就可以大概知道代码运行的快与慢

3，表示

大0表示法《解析数论》

0表示有很多，例举几个:0(1)、0(n)、0(n^2)、o( logn).. .

列如：

0(1)：一般的代码运行一次

0(n)：一个for循环

0(n^2)：两个for循环

o( logn)：while语句

总结：时间复杂度越低运行越快

//0(1)
let a = 1;
//0(n)
let n = 100;
let arr = [];
for (let i = 0; i < n; i++) {
  arr.push(1);
}

3、空间复杂度

1.是什么?

执行当前算法需要占用多少内存空间

2.表示法

0(1)、0(n)、0(n^2)...

和时间复杂度的理解一样

//0(1)
let a = 1;
//0(n)
let n = 100;
let arr = [];
for (let i = 0; i < n; i++) {
  arr.push(1);
}

4、栈-后进先出

5、算法题（栈）——有效的括号（字节考）

解题：

6、算法题（栈）——删除字符串中的所有相邻重复项

解题：

7、算法题（栈）——路径简化

解题：

8、队-先进先出

为什么?JavaScript 是单线程?

（1）JavaScript 语言的一大特点就是单线程，也就是说，同一个时间只能做一件事。那么为什么 JavaScript 不能有多个线程呢 ?这样能提高效率啊。

（2）JavaScript 的单线程，与它的用途有关。作为浏览器脚本语言，JavaScript 的主要用途是与用户互动，以及操作 DOM。这决定了它只能是单线程，否则会带来很复杂的同步问题。比如，假定 JavaScript 同时有两个线程，一个线程在某个 DOM 节点上添加内容，另一个线程删除了这个节点，这时浏览器应该以哪个线程为准?

（3）所以，为了避免复杂性，从一诞生，JavaScript 就是单线程，这已经成了这门语言的核心特征，将来也不会改变

JS执行流程

1、主线程读取JS代码，此时同步环境，形容对应的堆和执行栈。

2、主线程遇到异步任务，会推给异步线程进行处理

3.异步进行处理完毕，将对应的异步任务推入任务队列

4，主线程查询任务队列，执行微任务，将其按照顺序执行，全部执行完毕。

5，主线程查询任务队列，执行宏任务，取得第一个宏任务，执行完毕。

6，重复以上4，5步骤

9、算法题（队）最近的请求次数

解题：

10、链表的简介

1.什么是链表

多个元素存储的列表1

2.链表中的元素在内存中不是顺序存储的，而是通过”next"指针联系在一起的。

链表结构***js中的原型链 原理就是?链表结构

二、链表和数组的区别

1.数组:有序存储的，在中间某个位置删除或者添加某个元素其他元素要跟着动。

2.链表中的元素在内存中不是顺序存储的，而是通过"next"指针联系在一起的。

链表

三、链表的种类

单向链表

双向链表

11、instanceof原理（判断数据类型）

通过原型链匹配数据类型

12、算法题（链）—环形链表（小米考）

、、

解题：

13、算法题（链）—删除链表中的节点

解题：

14、算法题（链）—删除排序链表种的重复元素

解题：

15、算法题（链）—反转链表

解题：

16、字典和哈希表简介

字典：键值对存储的，类似于is的对象 (键[key]字典:都是字符串类型或者会转换成字符串类型)

字典?==》map来表示的，map的键不会转换类型

在js中没有哈希表，哈希表是字典一种实现

区别一:如果找key对应的value需要遍历key，那么想要省去遍历的过程，用哈希表来表示。

区别二: 排列顺序

字典是根据添加的顺序进行排列的哈希表不是添加的顺序进行排列的

哈希表例子：

17、算法题（哈希表）—两数之和

解题：

18、算法题（哈希表）—存在重复元素

解题：

方式一：

方式二：

19、算法题（哈希表）—两个数组的交集

解题：

20、算法题（哈希表）—独一无二的出现次数

解题：

21、算法题（哈希表）— 无重复字符的最长子串

解题：

22、树

一种分层数据的抽象模型，

简单来说: 分层级关系的

23、深度优先遍历

主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底...，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

技巧:

1，访问根节点

2.对根节点的children挨个进行深度优先搜索

24、广度优先遍历

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。

技巧:

1. 新建一个队列，把根节点入队
2. 把队头出队

3、把队头的children挨个入队

4、重复2和3步，直到队列为空为止

25、二叉树

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

26、算法题（二叉树）——二叉树的前序遍历

前序遍历就是先遍历根节点，然后遍历左节点，最后是右节点；

解题：

方法一：递归思想，数据量少效率高

方法二：栈方法，数据量多的时候效率高

27、算法题（二叉树）——二叉树的中序遍历

中序遍历就是先遍历左节点，然后遍历中间的根节点，最后是右节点；

方法一：

方法二：栈方法，数据量多的时候效率高

28、算法题（二叉树）——二叉树的后序遍历

后序遍历就是先遍历左节点，然后遍历是右节点，最后是中间的根节点。

解题：

方法一：递归思想，数据量少效率高

方法二：栈方法，数据量多的时候效率高

29、算法题（二叉树）——二叉树的最小深度

解题：

30、算法题（二叉树）——二叉树的最大深度

解题：

31、算法题（二叉树）——翻转二叉树

解题：

32、算法题（二叉树）——相同的树

解题：

33、堆

1、堆是什么?

堆都能用树来表示，并且一般树的实现都是利用链表

而二叉堆是一种特殊的堆，它用完全二叉树表示，却可以利用数组实现

平时使用最多的是二又堆，它可以用完全二叉树表示，二叉堆易于存储，并且便于索

***堆数据结构像树，但是，是通过数组来实现的 (不是通过链表:二又堆)

2、在堆的实现时，需要注意:

因为是数组，所以父子节点的关系就不需要特殊的结构去维护了，索引之间通过计算就可以得到，省掉了很多麻烦。如果是链表结构，就会复杂很多;

完全二叉树要求叶子节点从左往右填满，才能开始填充下一层，这就保证了不需要对数组整体进行大片的移动。这也是随机存储结构(数组)的短板:删除一个元素之后整体往前移是比较费时的。这个特性也导致堆在删除元素的时候，要把最后一个叶子节点补充到树根节点的缘由

二又堆想树的样子我可以理解，但将它们安排在数组里的话，通过当前下标怎么就能找到父节点和子节点呢?

34、算法题（堆）——数组中的第K个最大的元素

解题：（百度。。。）

35、排序算法

工具：通过动画可视化数据结构和算法<br> - VisuAlgo

36、冒泡排序

1. 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

37、选择排序

首先在未排序序列中找到最小(大) 元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小(大)元素，

然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕

38、插入排序

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

39、快速排序

1. 在数组中选一个基准数（通常为数组第一个或者中间值）；

2. 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边；

3. 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。