-
Notifications
You must be signed in to change notification settings - Fork 0
/
NOTE.txt
155 lines (154 loc) · 8.55 KB
/
NOTE.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
基础概念
时间复杂度
O(a)、O(n)、O(logN)...：描述算法的运行时间
空间复杂度
O(a)、O(n)、O(n^2)...：描述算法在运行过程中临时占用存储空间大小
栈
后进先出，使用array实现
arr.push(...); arr.pop()
使用场景：十进制转二进制、有效的括号、函数调用堆栈
队列
先进先出，保证有序，使用array实现
arr.push(...); arr.shift()
使用场景：食堂排队打饭、JS异步中的任务队列、计算最近请求次数
链表
元素的存储不连续，用 next 指针连在一起
数组增删非首尾元素时往往需要移动元素，而链表只需更改next指针的指向
使用object实现，next属性指向下一对象
遍历链表：定义指针，每次循环后指向 next 指向的对象
插入元素：将前一元素的next指向新元素，将新元素的next指向下一元素
删除元素：将前一元素的next指向需删除元素的下一元素；如只有删除元素，将值更改为下一元素值，再删除下一元素
使用场景：反转列表、两数相加、JS原型链、链表指针获取JSON节点值
原型链
对象的原型对象 Object.prototype
原型链通过 __proto__ 属性连接原型对象
obj.__proto__ = Object.prototype,
func.__proto__ = Function.prototype, func.__proto__.__proto__ = Object.prototype
arr.__proto__ = Array.prototype, arr.__proto__.__proto__ = Object.prototype
使用场景
若 a.__proto__ = b.prototype，则 a instanceof b = true
若从 A 对象上没有找到属性 x，将沿着原型链查询 x 属性
集合
无序且唯一的数据结构，元素不可重复，使用 ES6 中的 Set 实现
使用场景：去重、判断元素是否在集合中、求交集等
ES6 Set
方法：add、has、delete、clear
属性：size
迭代遍历：
for (let item of mySet) {}
for (let item of mySet.keys()) {}
for (let item of mySet.values()) {}
for (let [key, value] of mySet.entries()) {} // key = value
转换数组：
[...mySet]、Array.from(mySet)
字典
以键值对形式存储唯一值的数据结构，使用 ES6 中的 Map 实现
使用场景：键值对的增删改查
ES6 Map
方法：set(k, v)、delete(k)、clear()、get(k)
属性：size
树
一种分层数据的抽象模型，使用object与array实现
使用场景：DOM树、级联选择、树形控件等
前端与树：遍历JSON的所有节点值、渲染AntD树组件
常用操作
深度优先遍历：优先遍历深层节点 => 递归遍历子节点
广度优先遍历：优先遍历离根节点近的节点 => 将根节点压入队列，循环：出队、将子节点压入队列
先中后序遍历（二叉树）
二叉树
遍历方式
先序遍历：中 => 左 => 右
中序遍历：左 => 中 => 右
后序遍历：左 => 右 => 中
层序遍历：即广度优先遍历
遍历方法：递归；栈（先进先出 shift；先进后出 pop）
遍历算法
最大深度：使用深度优先遍历，判断叶子节点的层级大小
最小深度：使用广度优先遍历，最先发现的叶子节点层级最小
图
网络结构的抽象模型，是一组由边连接的节点，使用object和array构建图
使用场景：表示二元关系，如航班、道路等
图的表示法：邻接矩阵（二维矩阵）、邻接表（对象+数组/链表）、关联矩阵
常用操作
深度优先遍历：尽可能深的搜索图的分支
1. 访问根节点
2. 对根节点没访问过的相邻节点进行深度优先遍历（递归）
广度优先遍历：优先遍历离根节点近的节点
1. 新建一个队列，将根节点入队
2. 将队头出队并访问
3. 将队头的没访问过的相邻节点入队
堆
一种特殊的完全二叉树：每层节点完全填满，或仅缺少右边节点的若干节点
所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点
JS 使用一维array表示堆，位置索引公式：
任意节点的左侧子节点的位置: 2 * index + 1
任意节点的右侧子节点的位置: 2 * index + 2
任意节点的父节点的位置: (index - 1) / 2 的商
作用/使用场景
高效快速的找出最大值/最小值 => 堆顶，时间复杂度为 O(1)
找出第 K 个最大/小元素，如查找第K个最大元素：
1. 构建一个最小堆，将元素依次插入堆中（插入堆尾，需上移排序）
2. 当堆的容量超过K，就删除堆顶（需下移排序）
3. 插入结束后，堆顶就是第K个最大元素（小于堆中其他元素）
JS实现最小堆要素
构建一个类，声明数组遍历，用于存放堆的元素
插入
添加新元素：插入堆底，即数组尾部
尾数上移：不断与父节点交换，直到满足父节点小于等于插入值
大小为 N 的堆中，插入元素的时间复杂度为 O(logN)
删除堆顶
将数组尾部元素移出，并赋值给堆顶（直接删除堆顶会破坏堆的结构）
堆顶下移：不断与子节点交换，直到满足子节点大于等于新堆顶
大小为 N 的堆中，删除堆顶的时间复杂度为 O(logN)
获取堆顶：返回数组头部元素
获取堆大小：返回数组长度
排序算法
冒泡排序
比较相邻元素，如果第一个比第二个大则进行交换，可保证最后一个数是最大的
执行 n-1 轮，时间复杂度为 O(n^2)
选择排序
找到数组中的最小值，将其放到第一位(交换)；继续找第二小的值，放在第二位；……
执行 n-1 轮，时间复杂度为 O(n^2)
插入排序
从第二个数开始往前比，当前数较小则交换，并往前继续比较，当前数较大时停止往前比较
执行 n-1 轮，时间复杂度为 O(n^2)
归并排序
思路
分：把数组分为两半，再递归的对子数组进行“分”操作，直到分为单独的数
合：把两个数合为有序数组，再最有序数组进行合并，直到合并完整
递归过程
新建空数组res存放最终排序结果
比较两个有序数组的头部，较小者头部出队并推入res；重复执行
分的时间复杂度为O(logN)，合的时间复杂度为O(n)，总的时间复杂度为 O(n*logN)
实际应用：火狐排序
快速排序
思路
分区：从数组中任意选一个基准数，比基准小的放基准前面，大的放在后面
基准数取随机数，可以保证在平均情况下，算法的期望运行时间是线性的 => O(n)
递归：递归对基准前后的子数组进行分区排序
递归的时间复杂度为O(logN)，分区的时间复杂度为O(n)，总的时间复杂度为 O(n*logN)
实际应用：Chrome 排序
搜索算法
顺序搜索
遍历数组，返回 index/-1，时间复杂度为O(n)
二分搜索
折半搜索，前提是数组是有序的
从数组中间元素开始搜索，比对大小，小则从前半部分继续搜索，大则从后半部分继续搜索
每次比较范围缩小一半，时间复杂度为O(logN)
设计思想
分而治之
将一个问题分为多个和原问题相似的小问题，递归解决小问题，再将结构合并以解决原来的问题
子问题独立
场景：归并排序、快速排序、二分搜索
动态规划
将一个问题分为相互重叠的子问题，通过反复求解子问题，来解决原来的问题
子问题重叠
步骤：定义子问题，反复执行
场景：斐波那契数列
贪心算法
期盼通过每个阶段的局部最优选择，从而达到全局的最优，但结果不一定是最优
回溯算法
一种渐进式寻找并构建问题解决方式的策略
先从一个可能的动作开始解决问题，不行则回溯并选择另一个动作，直至问题解决
场景：全排列
步骤：递归模拟出所有情况；不符合则回溯（停止递归）