栈Stack

后进先出 ，数组模拟
常用操作： push、 pop、stack[stack.length-1]看栈顶
image.pngimage.png
image.png
vscode里通过打断点+F5 可以操作，通过单步调试 单步跳出，在左侧可以直观的看到call stack的执行过程
image.png
练习：lc有效的括号
image.png
image.png

队列 Queue

先进先出 ， 数组模拟
常用操作： push、 shift 、 queue[0] 看队头
**image.png
练习：lc993 最近请求次数
image.png
image.png

链表 LinkedList

使用Object模拟链表
image.png

image.png image.png
链表是用next指，原型链是通过proto指，图里的的->就表示proto
image.png
面试题1: 手写instanceof： 遍历A的原型链 ，如果能找到B.prototype，就返回true

image.png
面试题2：
image.png // value a ; undefined; value a; value b
链表与前端结合： 使用链表指针获取JSON的节点值
image.png

练习：lc237 lc206 lc2 lc83 lc141

集合Set

无序、唯一
常用操作： 去重、判断某元素是否在集合中、求交集
image.png
image.png
for of
Set里key 和value 是一样的
Set 变 Array const arr = […set] 、 const arr = Array.from(set)
Array 变 Set const set = new Set([1,2,3])
差集：加个！

练习：lc349

字典Map

image.png

练习 349 20 1 3 76

树 Tree

image.png
image.png
DFS 用递归 BFS 用队列
image.pngimage.png
二叉树： js里通常用Object模拟二叉树
image.png
前中后序 遍历
1.递归版（太简单了）
2.非递归版（函数调用栈 ） ？？
层序

前端与树：遍历JSON的所有节点值
image.png
渲染AntDeisgn的树组件？

练习 102 94 112 104 111

图graph

image.png
image.png
1.邻接矩阵
image.png
2.邻接表 ： 数组形式 、链表形式
image.png
js 邻接表
image.png

DFS

image.png
image.png // 2013

BFS

image.png

image.png //2031 visited？

练习 65 417 133

堆 heap
完全二叉树
image.png
image.png
image.png用最小堆
同理 地K小 用最大堆

JS实现最小堆类
image.png

215 347 23

排序

排序 sort
搜索 indexOf 不存在返回-1
排序
image.png
搜索
image.png
21 374

分治

分 —>递归—>合
image.png
image.pngimage.png
应用场景：归并、快排、二分搜索、翻转二叉树…..
练习 374 226 100 101

DP

与分治最大的区别就是：子问题是否独立。 如果重叠—DP 如果独立—分治
eg fibonacci vs 翻转二叉树
image.pngimage.png
DP步骤： 定义子问题—反复执行

练习 ：70 198

贪心

image.png
image.png
455
122

回溯

image.pngimage.png
46 全排列
78 子集

image.png
image.png

image.png
image.png