时间复杂度：可以当作执行多少次
| O(1) 执行1次  | O(n）执行了N次  | O(1)+O(n)=O(n)  |
| O(n)*O(n)=O(n^2)  | O(logN)  |
空间复杂度：是内存占用空间的大小
| O(1) 只声明了单个变量 | O（n) 声明了一个数组  | O(n^2) 矩阵  |
栈 stack：
后进先出的数据接口 所有后进先出的场景都可以用栈呢！ JS中用Array实现栈的功能
常用操作：push pop 查看栈顶stack[lengtn-1]
const stack = []; stack.push(1); stack.push(2); const item1 = stack.pop(); const item2 = stack.pop();
栈的使用场景：
需要后进先出的场景：十进制转二进制 判断字符串的括号是否有先 函数调用堆栈
十进制转二进制：
后出来的余数排在高位，把余数依次入栈，再依次出栈，就得到了二进制
有效的括号：
判断括号是否有效闭合
越靠后的左括号，对应的右括号越靠前
左括号入栈 右括号出栈 最后栈空了就是合法滴
函数调用堆栈：
最后被调用的函数，最先执行完，JS解释器就是使用栈来控制函数的调用顺序
9
const func1 = () => {
func2();
};
const func2 = () => {
func3();
};
const func3 = () => {};
func1(); 先按照fn1 fn2 fn3的顺序扔到栈里 执行时是fn3 fn2 fn1 小结:
所有后进先出的场景，都可以只用栈 常用操作是 push pop stacn[stack.length-1]访问栈顶元素
也可以把栈看作只有一个出口
两道思考题：
用ES6的class 封装一个stack类 写push pop peek方法
class Stack{
constructor(){
this.stack = [];
}
push(val){
this.stack.push(val)
}
pop(){
this.stack.pop();
}
peek(){
return this.stack[this.stack.length-1]
}
} 用栈这个结构 将十进制转为二进制function binary(num) {
const stack = [];
let str = '';
while (num) {
const c = num % 2;
stack.push(c);
num = Math.floor(num / 2)
}
while (stack.length) {
str = str + stack.pop();
}
return str
} 写这个的时候，一不小心把str 用 const定义了 这肯定不行 用const定义后不可以更改 像stack这种用方法操作是没问题的 但要是重新赋值str=str+巴拉巴拉 这肯定不行呢！通过这个错误深刻领会一下const let的差距 不错！ 补充一个API：
数组求和用reduce
stack.reduce((total,num) =>{return total + num}) 最大矩形问题：
一个比较难得算法题 单独整理一下：
队列 Queue
一个先进先出的数据结构 JS里同样没队列 还是用Array来实现
const queue = []; queue.push(1); queue.push(2); const item1 = queue.shift(); const item2 = queue.shift();
应用场景：
先进先出 比如 JS异步任务队列 计算最新请求次数
JS异步队列（这个我熟悉了！）：
JS是单线程 无法处理异步的并发任务 就使用queue进行异步任务
计算最近请求次数：
有新请求就入队 3000ms前发出的请求出队 队列的长度就是最近请求次数
链表
多个元素组成的列表，但元素存储不连续，用next指针连在一起
数组增删非首尾元素时往往需要移动元素
而列表增删非首尾元素，不用移动，改变指针就得了
JS中还是没有链表！还得用Object模拟！大无语！JS！你可真行！
用next来当作指针 形成一个嵌套的链表
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;
// 遍历链表
let p = a;
while (p) {
console.log(p.val);
p = p.next;
}
// 插入
const e = { val: 'e' };
c.next = e;
e.next = d;
// 删除e
c.next = d; 例题
反转链表
先考虑反装两个节点：将n+1的next指向n即可
因此，反转反转多个节点，使用双指针遍历链表
步骤：
- 双指针：一前一后遍历
- 反转双指针
应用场景：
原型链：
原型链上的节点就是各种原型属性
原型链通过__proto__属性进行连接（相当于next属性）
如果A沿着原型链能找B.prototype，那么A instanceof B返回true
如果在A上没有找到x属性，就顺着原型链往上找（利用A.hasOwnProperty来验证某一个属性属于它自己，还是原型)
手写instanceof
JSON：
11
const json = {
a: { b: { c: 1 } },
d: { e: 2 },
};
const path = ['a', 'b', 'c'];//路径
let p = json;
path.forEach((k) => {
p=p[k]; //将按照path的顺序来遍历json 得到c的val 1
}); 集合
集合是无序且唯一的数据结构，JS中的集合就是Set！
集合可以用来：去重，判断某元素是否在集合中，求交集
// 去重 const arr = [1, 1, 2, 2]; const arr2 = [...new Set(arr)];//把集合转为数组 // 判断元素是否在集合中 const set = new Set(arr); const has = set.has(3); // 求交集 set没有直接求交集的方法 需要用数组的filter筛选 const set2 = new Set([2, 3]); const set3 = new Set([...set].filter(item => set2.has(item)));补充：filter函数
filter() 方法创建一个新的数组，新数组中的元素是通过检查指定数组中符合条件的所有元素。在return后面判断结果，取布尔值，true的话就添入新的filter数组中，false的话，不会添进filter的数组中
所以,往filter里放判断的条件就行了，filter自然会进行布尔值判断
例题
两个数组的交集
求交集，且输出结果无序且唯一，所以肯定要使用Set
步骤：
- 用Set对数组nums1去重
- 去重后遍历，并筛选出nums2也包含的值
应用场景：
ES6中的Set
- 使用Set对象：new add delete has size
- 迭代Set：多种迭代方法 Set和Array互转 求交集/差集
let mySet = new Set();
mySet.add(1);
mySet.add(5);
mySet.add(5);//Set里是===
mySet.add('some text');
let o = { a: 1, b: 2 };
mySet.add(o);
mySet.add({ a: 1, b: 2 });//这两个对象看起来一样 实际不一样 所以能添加
const has = mySet.has(o);
mySet.delete(5);
//一些迭代方法
for(let [key, value] of mySet.entries()) {console.log(key, value)};
//但set的key value都是一样的
const myArr = Array.from(mySet);
const mySet2 = new Set([1,2,3,4]);
//求交集
const intersection = new Set([...mySet].filter(x => mySet2.has(x)));
//求差集
const difference = new Set([...mySet].filter(x => !mySet2.has(x))); 字典
与集合类似，字典也是一种存储唯一值的数据结构，但它以 键值对 的形式来存储
就是我们在ES6中新增的Map
常用操作是键值对的增删改查
const m = new Map();
// 增
m.set('a', 'aa');
m.set('b', 'bb');
// 删
m.delete('b');
// m.clear(); 全部清空
// 改
m.set('a', 'aaa');
//查
console.log(m.has('a')); 例题
lc的第一道题 这个都不会就完蛋了
分析题目：
把nums想象成相亲者 target为匹配条件 用字典建立一个介绍所
二叉树
一种分层数据的抽象模型：如DOM树 级联选择 树形控件
级联选择：
JS中没有树，但可以用Object和Array构建树 (Vnode形式）
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: [],
},
{
val: 'e',
children: [],
}
],
},
{
val: 'c',
children: [
{
val: 'f',
children: [],
},
{
val: 'g',
children: [],
}
],
}
],
};
树的常用操作：
深度/广度优先遍历，先中后序遍历
深度广度优先遍历：
尽可能深得搜索树的分支
算法口诀：访问根节点 再对根节点的children挨个进行深度优先遍历（是一个递归的过程）
const dfs = (root) => {
console.log(root.val);
root.children.forEach(dfs);
};
dfs(tree);
广度优先遍历
先访问离根节点最近的节点
口诀：
- 新建一个队列 被根节点入队
- 把队头出队并访问
- 把队头的children挨个入队
- 重复第二三步 直到队列为空
const bfs = (root) => {
const q = [root];//新建队列 根节点root入队
while (q.length > 0) {
const n = q.shift();//队头先弹出
console.log(n.val);//访问这个队头
n.children.forEach(child => {
q.push(child);//把队头的children入队
});
}
};
bfs(tree); 还是要记得！！用forEach ！！！！！！！
二叉树：
树中每个节点最多只能有两个子节点 在JS中通常用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,
},
},
};
module.exports = bt; 访问根节点
对根节点的左子树进行先序遍历
对根节点的右子树进行先序遍历
/根/左/右
const bt = require('./bt');
const preorder = (root) => {
if (!root) { return; }
console.log(root.val);
preorder(root.left);
preorder(root.right);
};
preorder(bt); 非递归版（使用栈进行模拟）
const preorder = (root) => {
if (!root) { return; }
const stack = [root];//根节点
while (stack.length) {
const n = stack.pop();//弹出根节点
console.log(n.val);//访问根节点
if (n.right) stack.push(n.right);
if (n.left) stack.push(n.left);//后进先出 所以要后压left
}
};
preorder(bt); 中序：
对根节点的左子树进行中序遍历
访问根节点
对根结点的右子树进行中序遍历
const bt = require('./bt');
const inorder = (root) => {
if (!root) { return; }
inorder(root.left);
console.log(root.val);
inorder(root.right);
};
inorder(bt); 非递归版
const inorder = (root) => {
if (!root) { return; }
const stack = [];
let p = root;
while (stack.length || p) {
while (p) {
stack.push(p);
p = p.left;
}//把所有的左节点push进stack中
const n = stack.pop();//从栈顶开始往外弹出
console.log(n.val);//访问
p = n.right;//从右边开始 做一次新的遍历
}
};
inorder(bt); 后序：
- 对根结点的左子树进行后续遍历
- 对根节点的右子树进行后序遍历
- 访问根节点
const bt = require('./bt');
const postorder = (root) => {
if (!root) { return; }
postorder(root.left);
postorder(root.right);
console.log(root.val);
};
postorder(bt); const postorder = (root) => {
if (!root) { return; }
const outputStack = [];
const stack = [root];
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);
}
};
postorder(bt); 后序遍历较为负责 但可以把它倒过来 变成：根 右 左 这就跟先序遍历很像了！
所以利用先序遍历来做
首先用先序遍历的思路 来实现一个倒过来的后序
最后弹出访问 就实现了后序遍历
前端与树结合：
遍历JSON的所有节点：
const json = {
a: {
b: {
c: 1
}
},
d: [1, 2]
}
const dfs = (n，path) => {
console.log(n,path);
Object.keys(n).forEach(k => {
dfs(n[k],path.concat(k));
})
};
dfs(json,[]) 通过Object.keys 来获取子节点图
图是网络结构的抽象模型，一组由边连接的节点。
JS中还是没有图 但是可以用Object 和 Array等来构造
| 邻接矩阵 | 邻接表 |
 |  |
图的常用操作：
深度优先遍历 ：
尽可能深得搜索图的分支
口诀：
- 访问根节点
- 对根节点的没访问过的相邻节点挨个进行深度优先遍历
如果不限制，会陷入循环
const visited = new Set()
const dfs = function (n){
console.log(n);
visited.add(n);
graph[n].forEach(c =>
if(!visited.has(c)){
dfs(c)
}
}; 广度优先遍历：
先访问离根节点最近的
- 新建一个队列，把根节点入队
- 把队头出头并访问
- 把队头没访问过的相邻节点入队
- 重复2 3 步
const visited = new Set();
visited.add(2);
const q = [2];
while (q.length) {
const n = q.shift();
console.log(n);
graph[n].forEach(c => {
if (!visited.has(c)) {
q.push(c);
visited.add(n);
}
});
} 记录一道例题 力扣65
图中有7个状态，只有6 3 5的状态是合法状态 最终停留在635才是true 不能走到或者最后无路可走 都是false
堆(好麻烦 这个也放一放吧）
堆是一种特殊的完全二叉树，即每一层都完全填满，最后一层只缺少右节点
所有节点都大于等于他的子节点（ 最大堆）或小于等于他的子节点（最小堆）
在JS中通常使用数组表示堆：
通过这种结构：
可以利用堆 找出第K个最大元素：
用JS实现最小堆列：
插入时：
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
} 使用shiftUp getParentIndex(i) {
return (i - 1) >> 1;
}
shiftUp(index) {
if (index == 0) { return; }
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
} class MinHeap {
constructor() {
this.heap = [];
}
swap(i1, i2) {
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
getParentIndex(i) {
return (i - 1) >> 1;
}
getLeftIndex(i) {
return i * 2 + 1;
}
getRightIndex(i) {
return i * 2 + 2;
}
shiftUp(index) {
if (index == 0) { return; }
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] > this.heap[index]) {
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[index]) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if (this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
this.heap[0] = this.heap.pop();
this.shiftDown(0);
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}
const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);
h.pop(); 
京公网安备 11010502036488号