考试时允许使用草稿纸，请提前准备纸笔。考试过程中允许上厕所等短暂离开，但请控制离开时间

笔试得分60%一般通过，面试答对80%才能通过

目录考试范围收录选择题常用设计模式原则创建型单例模式工厂模式结构型代理模式装饰器模式行为型职责链模式观察者模式操作系统进程程序、进程、线程⭐死锁并发和并行处理机调度调度层次调度基本准则调度方式调度算法⭐内存管理连续空间分配策略算法⭐页面置换算法⭐数据结构链表数组和链表栈压栈的出入序列n个不同元素进栈，出栈序列数栈指针表达式求值队列顺序存储链式存储树二叉树n叉树满二叉树哈夫曼树（最优二叉树）Huffman二叉排序树/二叉查找树BST（BinarySearch/SortTree）平衡二叉树AVL大根堆最小生成树森林先序确定的二叉树个数带权路径长度WPL图完全图最短路径拓扑排序关键路径模式匹配BF模式匹配KMP模式匹配内部排序算法T(n)和S(n)应用平均查找长度ASL顺序/线性查找折半/二分查找分块/索引顺序查找散列(Hash)表递归递归和递推的区别十进制转换为二进制迷宫求解算法（编程题）经验常用输出考核方式ACM模式JavaScript(V8)JavaScript(Node)核心代码模式链表判断链表是否有环二叉树(反)序列化二叉树前序遍历（迭代）中序遍历（迭代）后序遍历（迭代）层序遍历判断对称二叉树判断完全二叉树判断平衡二叉树二叉树的镜像最近公共祖先数组和树扁平结构(一维数组)转树数组扁平化排序快速排序*归并排序*堆排序回溯全排列N皇后动态规划(DynamicProgramming，DP)斐波那契(Fibonacci）数列（递归）数塔（递推）最长公共子序列(LCS)最长回文子串最小路径和背包01背包完全背包散列/哈希Hash数字千位分割图DFS深度优先搜索​编辑BFS广度优先搜索常用方法异或运算^MathNumberMapSetset判断值相等的机制数组去重（⭐手写）ArrayString正则表达式RegularExpression(RegExp)字面量和字符串regexp.test和regexp.exec常用修饰符lastIndex分组回溯引用匹配选择匹配：(子模式)|(子模式)惰性匹配：最小化匹配前/后向查找：匹配括号中的内容（不包含括号）技巧反义字符边界量词应用str.split()str.match()str.replace()str.serach()合法的URL常用字符元字符表[A-z]和[a-zA-Z]规范*命名规范常量变量，函数类*注释HTMLCSSJS

考试范围收录

选择题总集合={前端，计算机基础（数据库，操作系统，数据结构与算法，计算机网络），行测}；

编程题总集合={常规算法（到具体情景），js手写，Dom操作}

例如：

• 美团：前端，计算机基础，行测，常规算法（前端：计算机基础=1:1）
• 小红书：前端，计算机基础，常规算法（前端：计算机基础=3：1）
• SHINE：前端，js手写
• 携程，京东：是先行测
• 百度：前端，计算机基础，常规算法，Dom操作

选择题

⭐是常考考点，其他是作为理解原理的补充，原理部分在大厂笔面试中会考到

常用设计模式

原则

• S–SingleResponsibilityPrinciple单一职责原则
  • 一个程序只做好一件事
  • 如果功能过于复杂就拆分开，每个部分保持独立
  • 例如：Promise每个then中的逻辑只做好一件事
• O–OpenClosedPrinciple开放/封闭原则
  • 对扩展开放，对修改封闭
  • 增加需求时，扩展新代码，而非修改已有代码
  • 例如：Promise如果新增需求，扩展then
• L–LiskovSubstitutionPrinciple里氏替换原则
  • 子类能覆盖父类
  • 父类能出现的地方子类就能出现
• I–InterfaceSegregationPrinciple接口隔离原则
  • 保持接口的单一独立
  • 类似单一职责原则，这里更关注接口
• D–DependencyInversionPrinciple依赖倒转原则
  • 面向接口编程，依赖于抽象而不依赖于具体
  • 使用方只关注接口而不关注具体类的实现

//checkType('165226226326','mobile')

//result：false

letcheckType=function(str,type){

switch(type){

case'email':

return/^[\w-](\.[\w-])*@[\w-](\.[\w-])$/.test(str)

case'mobile':

return/^1[3|4|5|7|8][0-9]{9}$/.test(str);

case'tel':

return/^(0\d{2,3}-\d{7,8})(-\d{1,4})?$/.test(str);

default:

returntrue;

}

}

想添加其他规则就得在函数里面增加case。违反了开放-封闭原则（对扩展开放，对修改关闭）

给API增加一个扩展的接口:

letcheckType=(function(){

letrules={

email(str){

return/^[\w-](\.[\w-])*@[\w-](\.[\w-])$/.test(str);

},

mobile(str){

return/^1[3|4|5|7|8][0-9]{9}$/.test(str);

}

};

//暴露接口

return{

//校验

check(str,type){

returnrules[type]?rules[type](str):false;

},

//添加规则

addRule(type,fn){

rules[type]=fn;

}

}

})();

//调用方式

//使用mobile校验规则

console.log(checkType.check('188170239','mobile'));

//添加金额校验规则

checkType.addRule('money',function(str){

return/^[0-9](.[0-9]{2})?$/.test(str)

});

//使用金额校验规则

console.log(checkType.check('18.36','money'));

创建型

单例模式

一个类只有一个实例，并提供一个访问它的全局访问点。

classLoginForm{

constructor(){

this.state='hide'

}

show(){

if(this.state==='show'){

alert('已经显示')

return

}

this.state='show'

console.log('登录框显示成功')

}

hide(){

if(this.state==='hide'){

alert('已经隐藏')

return

}

this.state='hide'

console.log('登录框隐藏成功')

}

}

LoginForm.getInstance=(function(){

letinstance

returnfunction(){

if(!instance){

instance=newLoginForm()

}

returninstance

}

})()

letobj1=LoginForm.getInstance()

obj1.show()

letobj2=LoginForm.getInstance()

obj2.hide()

console.log(obj1===obj2)

优点：

• 单例模式可以保证内存里只有一个实例，减少了内存的开销。
• 单例模式设置全局访问点，可以优化和共享资源的访问。
• 只会实例化一次。简化了代码的调试和维护

缺点：

• 单例模式一般没有接口，扩展困难
• 有可能导致模块间的强耦合从而不利于单元测试。

应用：登录框

工厂模式

工厂模式定义一个用于创建对象的接口，这个接口由子类决定实例化哪一个类。

该模式使一个类的实例化延迟到了子类。

而子类可以重写接口方法以便创建的时候指定自己的对象类型。

classProduct1{

product(){

console.log("生产一线");

}

}

classProduct2{

product(){

console.log("生产二线");

}

}

classFactory{

constructor(){

this.Product1=Product1;

this.Product2=Product2;

}

create(name,callBack){

constproduct=newthis[name]();

product.product();

returncallBack("susess");

}

}

letp=newFactory();

p.create("Product1",(res)=>{

console.log(res);

});

优点：

• 工厂职责单一化易于维护
• 有利于消除对象间的耦合，提供更大的灵活性

缺点：添加新产品时，需要编写新的具体产品类,一定程度上增加了系统的复杂度

结构型

• 装饰者模式：扩展功能，原有功能不变且可直接使用
• 代理模式：显示原有功能，但是经过限制之后的

代理模式

是为一个对象提供一个代用品或占位符，以便控制对它的访问

应用：

• ES6的proxy
• HTML元素事件代理

1.给"ul"标签添加点击事件

2.当点击某"li"标签时，该标签内容拼接"."符号。如：某"li"标签被点击时，该标签内容为".."

注意：

1.必须使用DOM0级标准事件（onclick）

target表示当前触发事件的元素

currentTarget是绑定处理函数的元素

只有当事件处理函数绑定在自身的时候，target才会和currentTarget一样

<ul>

<li>.</li>

<li>.</li>

<li>.</li>

</ul>

<scripttype="text/javascript">

document.querySelector('ul').onclick=event=>{

event.target.innerText='.'

}

</script>

装饰器模式

动态地给某个对象添加一些额外的职责，是一种实现继承的替代方案

classCellphone{

create(){

console.log('生成一个手机')

}

}

classDecorator{

constructor(cellphone){

this.cellphone=cellphone

}

create(){

this.cellphone.create()

this.createShell(cellphone)

}

createShell(){

console.log('生成手机壳')

}

}

//测试代码

letcellphone=newCellphone()

cellphone.create()

console.log('------------')

letdec=newDecorator(cellphone)

dec.create()

优点：

• 方便动态的扩展功能，且提供了比继承更多的灵活性。

缺点：

• 多层装饰比较复杂。

应用：

• ES7Decorator
• 比如现在有4种型号的自行车，我们为每种自行车都定义了一个单独的类。现在要给每种自行车都装上前灯、尾灯和铃铛这3种配件。如果使用继承的方式来给每种自行车创建子类，则需要4×3=12个子类。但是如果把前灯、尾灯、铃铛这些对象动态组合到自行车上面，则只需要额外增加3个类

行为型

职责链模式

使多个对象都有机会处理请求，从而避免请求的发送者和接受者之间的耦合关系，将这些对象连成一条链，并沿着这条链传递该请求，直到有一个对象处理它为止

//请假审批，需要组长审批、经理审批、总监审批

classAction{

constructor(name){

this.name=name

this.nextAction=null

}

setNextAction(action){

this.nextAction=action

}

handle(){

console.log(`${this.name}审批`)

if(this.nextAction!=null){

this.nextAction.handle()

}

}

}

leta1=newAction("组长")

leta2=newAction("经理")

leta3=newAction("总监")

a1.setNextAction(a2)

a2.setNextAction(a3)

a1.handle()

优点：

• 简化了对象。使得对象不需要知道链的结构

缺点：

• 不能保证某个请求一定会被链中的节点处理，这种情况可以在链尾增加一个保底的接受者节点来处理这种即将离开链尾的请求。
• 使程序中多了很多节点对象，可能再一次请求的过程中，大部分的节点并没有起到实质性的作用。他们的作用仅仅是让请求传递下去，从性能当面考虑，要避免过长的职责链到来的性能损耗。

应用：

• JS中的事件冒泡
• 作用域链
• 原型链

观察者模式

constp1=newPromise((resolve,reject)=>{

setTimeout(()=>{

resolve('result')

},

1000);

})

p1.then(res=>console.log(res),err=>console.log(err))

分析Promise的调用流程：

• Promise的构造方法接收一个executor()，在newPromise()时就立刻执行这个executor回调
• executor()内部的异步任务被放入宏/微任务队列，等待执行
• then()被执行，收集成功/失败回调，放入成功/失败队列
• executor()的异步任务被执行，触发resolve/reject，从成功/失败队列中取出回调依次执行

观察者模式：收集依赖->触发通知->取出依赖执行

在Promise里，执行顺序是then收集依赖->异步触发resolve->resolve执行依赖。

classMyPromise{

//构造方法接收一个回调

constructor(executor){

this._resolveQueue=[]//then收集的执行成功的回调队列

this._rejectQueue=[]//then收集的执行失败的回调队列

/*由于resolve/reject是在executor内部被调用,

因此需要使用箭头函数固定this指向,否则找不到this._resolveQueue*/

let_resolve=(val)=>{

//从成功队列里取出回调依次执行

while(this._resolveQueue.length){

constcallback=this._resolveQueue.shift()

callback(val)

}

}

//实现同resolve

let_reject=(val)=>{

while(this._rejectQueue.length){

constcallback=this._rejectQueue.shift()

callback(val)

}

}

//newPromise()时立即执行executor,并传入resolve和reject

executor(_resolve,_reject)

}

//then方法,接收一个成功的回调和一个失败的回调，并push进对应队列

then(resolveFn,rejectFn){

this._resolveQueue.push(resolveFn)

this._rejectQueue.push(rejectFn)

}

}

操作系统

进程

程序、进程、线程⭐

程序：（静态）以文件形式存于硬盘进程：（传统OS）资源分配和独立调度的基本单位，进程实体的运行过程线程：（引入线程的OS）独立调度的基本单位进程的状态和转换

运行就绪：仅缺处理机阻塞/等待：等待资源（除处理机）可用或输入/输出完成创建：正创建；结束：正消失；

<--时间片/优先级--新建---创建--->就绪---调度--->运行----退出--->终止事件发生↖阻塞↙等待事件

死锁

⭐常考类型：进程Pi各需资源SXi个，则Smin/Nmax不死锁条件：S=∑(Xi-1)1

定义：多进程∵资源竞争而造成相互等待的僵局，无外力作用下都无法继续推进原因：非剥夺资源的竞争进程的非法推进顺序（含信号量使用不当）充要：

等待循环Pi的资源必须由Pi1满足（当各类资源＝1，则循环等待＝死锁）

必要条件：b->a、c->d

互斥访问非剥夺资源请求和保持循环等待

处理预防避免检测分配严格，宁愿闲置资源折中，运行时判断是否可能死锁宽松，并发性最强只要允许就分配操作破坏必要条件之一：一次请求all；剥夺；按资源序分配算法通过是否安全状态，找可能的安全序列定期检查是否死锁优点适用突发处理，不必剥夺不必剥夺，限制条件弱，系统性能较好不延长进程初始化时间，允许对死锁现场处理缺点效率低，进程初始化时间长；饥饿剥夺次数过多；不便灵活申请资源需知将来需求资源；可能长时阻塞进程剥夺解除死锁，造成损失

预防：

破坏必要条件：

互斥访问：某些场合必须保证互斥，∴实现可能性小：非剥夺资源：释放已获得，造成前段工作失效；反复申请释放，增加开销，降低吞吐

（常用于易于保存和恢复的资源，eg：CPU的寄存器内存资源；而非打印机etc）

请求和保持：预先静态分配（一次申请完）；饥饿循环等待：资源编号，只能按递增申请，同类资源一次申请完

（需编号稳定，限制了设备增加；可能用资源和规定顺序不同，造成浪费资源；编程麻烦）

避免：（死锁=>不安全状态）

银行家算法：Max，Need，Allocation，Available

检测：

死锁定理：S状态的资源分配图不可完全简化解除：

剥夺（暂停）：挂起某些进程，并抢夺资源（应防止被挂起的进程长期得不到资源）撤销（关闭）：（按进程优先级撤销代价）撤销部分甚至全部进程，并抢夺资源回退（回放）：一/多个进程回退到足以避免死锁，自愿释放资源（要求系统保持进程的历史信息，设置还原点）

并发和并行

并发：逻辑上的同时发生（simultaneous）一个处理器同时处理多个任务。
并行：物理上的同时发生，是指多个处理器或者是多核的处理器同时处理多个不同的任务。

处理机调度

调度层次

多道批处理系统大多有作业调度，其他系统则不需要

低级/作业调度：外/辅存后备--->入内存，建进程，分资源，获竞争处理机权利中级/内存调度：暂不能运行--->外存挂起（提高内存利用率系统吞吐量）高级/进程调度：按某种方法/策略分配

调度基本准则

CPU利用率系统吞吐量：单位时间内CPU完成的作业量周转时间＝作业完成时间－提交时间＝t总；带权周转时间＝等待时间＝∑等待处理机时间；（判断效率）响应时间＝首次响应时刻－提交时刻；

调度方式

非剥夺/抢占式：适用多数批处理系统剥夺/抢占式：提高系统吞吐率响应率

调度算法⭐

（含作业/进程）平均等待时间：时间片轮转较长（上下文切换费时）；短作业优先最短FCFS短作业优先高响应比RR多级反馈队列抢占x√√√对内算法?非抢占√√（默认）√（默认）x对内算法?适用无批处理OS无分时通用

FCFS先来先服务（FirstComeFirstServe）：利于长作业，CPU繁忙型作业SJF短作业优先：一个/若干估计运行时间最短作业入内存SPF短进程优先：一个最短进程调度，分配处理机优先级：静优先级取决进程类型（系统>用户），要求资源（I/O>计算），用户要求

动态priority＝nicek1*cpuTime-k2*waitTime（k1，k2>0调整所占比例）

高响应比优先（主要作业）＝FCFSSJF；无饥饿

t总/t实＝响应比Rp＝

时间片轮转RR（主要分时）：长短取决系统响应时间，就绪进程数，系统处理能力多级反馈队列＝时间片优先级：

特点：

级↓的就绪队列，优先级↑，时间片↑新进程入内存，先1级，时间片用完则降级；第n级队列时间片轮转i级队列空，才执行i1级队列若执行j级队列时，k级队列入进程（k<j），则抢占，当前进程回j队列末尾

优势：

终端型作业用户：短作业优先（大多交互型，常短小）短批处理作业用户：周转时间短长批处理作业用户：经过前几个队列的部分执行，不会长时间无响应

内存管理

内存空间的扩充：从逻辑上扩充，虚拟存储/自动覆盖技术

源程序->可在内存中执行的程序：

编译：编译程序编译源代码成若干个目标模块链接：链接程序链接目标模块所需库函数，形成一个完整的装入模块（形成逻辑地址）装入：装入程序将装入模块装入内存（形成绝对地址）

相对/逻辑地址：编译后，每个目标模块都从0号单元开始编址逻辑地址空间：各个目标模块的相对地址构成的统一从0号单元开始编址的集合（内存管理的具体机制完全透明，只有系统编程人员才涉及，用户程序/程序员只需知道逻辑地址）物理地址空间：内存中物理单元的集合地址重定位：逻辑地址->物理地址

连续空间分配策略算法⭐

分配策略算法首次适应FF最佳适应BF最坏适应WF邻近适用NF空闲分区链接地址递增容量递增容量递减循环首次适应性能最简单、快、好最多外部碎片很快没大内存块内存末尾碎片比较（∵留下了高地址的大空闲区，∴更可能满足进程）优于顺序：FF可能>BF>WF，FF通常>NF

页面置换算法⭐

最佳(OPT)置换算法：替换最长时间内/永久不再被访问∵最低缺页率，不可实现，∴只拿来评价其他算法先进先出(FIFO)置换算法（队列）：Belady异常（分配物理块数↑，页故障数↑）最近最久未使用(LRU)置换算法（堆栈）：性能接近OPT，但需寄存器栈；困难，开销大理论可证明，堆栈类算法不可能出现Belady异常时钟(CLOCK)/最近未使用(NRU)置换算法：循环扫描缓冲区简单CLOCK算法：

使用位：每一帧关联一个附加位/访问位使用位置1：首次装入/再被访问候选帧集合：看做循环缓冲区，有一个指针与之关联替换：按装入顺序扫描/上次扫描位置，扫描查找到0的帧，之前的1帧置0

改进型CLOCK算法：修改位m（修改过的页，被替换前，需写回外存）

替换第一个帧（u＝0，m＝0）重新扫描，替换第一个帧（u＝0，m＝1），跳过的帧u置0指针回到最初位置，所有帧u置0，重复①

数据结构

链表

指针：是结点的相对地址，即数组下标，即游标分配：预先分配连续的内存空间结束标志：next=-1

a-->b-->c^下标datanext021b42a134c-1

​​​​​​​数组和链表

数组静态分配内存，链表动态分配内存;
数组在内存中连续，链表不连续;
数组元素在栈区，链表元素在堆区;
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n);
数组增删元素的时间复杂度O(n)，链表的时间复杂度O(1);

栈

压栈的出入序列

（以入栈12345为例）（1）出栈p首时，p前的序列A，只能逆序出栈，且插在A中每个元素后面eg：4****；4_3_2_1_（2）p出栈序列的前一个元素p1，可能为p的前面的或后一个结点eg：出栈p1,3则p1可能=1,2;4

n个不同元素进栈，出栈序列数

合法的出栈序列的数量=出栈序列的总数-非法序列的数量

卡特兰数Catalan

栈指针

操作初始S.top=-1，即top指向栈顶S.top=0共享栈，top指向栈顶栈顶元素S.data[S.top]S.data[S.top-1]S.data[S.top]进栈S.data[top]=x;S.data[top]=x;S.data[--top1]=x;出栈x=S.data[top--];x=S.data[--top];x=S.data[top1];栈空S.top==-1;S.top=0;top1==MaxSize;top0=0;栈满S.top==MaxSize-1;S.top==MaxSize;top1-top0=1;

缺点：数组上界约束入栈，对最大空间估计不足时，可能上溢（整个存储空间满时）共享栈：栈顶向共享空间延伸，栈底在两端，优点：更有效利用存储空间

表达式求值

将表达式构建成中序二叉树，然后先序求值

前，中，后缀指op在两操作数中的位置

中缀表达式：ABx（C-D）-E/F依赖运算符的优先级；处理括号后缀表达式：ABCD-xEF/-已考虑运算符优先级，无括号

后缀表达式

组成：只有操作数运算符；表达：原运算式对应的表达式树的后续遍历计算表达式值：

初始设置一个空栈，顺序扫描后缀表达式若为操作数，则压入栈若为操作符<op>，则连续从栈中退出两个操作数Y和X，形成运算指令X<op>Y，计算结果重新压入栈所有表达式项都扫描完，栈顶即为结果

中缀转换为前/后缀：（手工）

按运算符优先级，对所有运算单位加（）运算符移到相应的（）前/后面去掉括号

中缀转换为后缀：以a*b(-c)为例

根本：栈存放暂时不能确定运算次序的操作符算法思想：

从左到右扫描中缀表达式扫到数，加入后缀扫到符：

‘（’：入栈‘）’：栈内运算符依次出栈，直至栈内遇到‘（’，然后直接删除‘（’其他运算符：优先级＞栈顶的非‘（’运算符时or栈空or栈顶‘(’，直接入栈

否则，依次弹出当前处理符≤栈内优先级的运算符，直到遇‘(’or优先级<当前处理符待处理序列栈后缀表达式当前扫描元素动作a*b(-c)aa加入后缀表达式*b(-c)a**入栈b(-c)*abb加入后缀表达式(-c)*ab<栈顶*，弹出*(-c)ab入栈(-c)ab*((入栈-c)(ab*-栈顶为(，-入栈c)(-ab*cc加入后缀表达式)(-ab*c)把栈中(之后的符号入后缀，并删(ab*c-扫描完毕，运算符依次退栈，入后缀ab*c-完成

具体转换过程（在中缀表达式后‘#’表示表达式结束，题中不算操作符）

操作符#（*,/,-）isp栈内优先01536icp栈外优先06421步骤扫描项项类型动作栈内输出0‘#’进栈，读下一符号#1a操作数直接输出#a2*操作符isp(‘#’)<icp(‘*’)，进栈#*3b操作数直接输出#*b4操作符isp(‘*’)>icp(‘’)，退栈并输出#*5isp(‘#’)<icp(‘’)，进栈#6（操作符isp(‘-’)<icp(‘（’)，进栈#（7-操作符isp(‘（’)<icp(‘-’)，进栈#（-8c操作数直接输出#（-c9）操作符isp(‘-’)>icp(‘）’)，退栈并输出#（-10isp(‘（’)==icp(‘）’)，直接退栈#11#操作符isp(‘’)>icp(‘#’)，退栈并输出#12isp(‘#’)==icp(‘#’)，退栈，结束

队列

顺序存储

队非空时，Q.front指向队头元素的上一个元素，Q.rear指向队尾元素Q.front指向队头元素，Q.rear指向队尾元素的下一个位置∵假溢出：初始Q.front==Q.rear=0;“队满”Q.front==Q.rear∴循环队列

初始Q.front=Q.rear=0;队长：(Q.rear-Q.frontMaxSize)%MaxSize出队/入队时，Q.front或Q.rear顺时针1：

x=Q.data[Q.front];Q.front=(Q.front1)%MaxSize

链式存储

链队列

优点：不存在队满甚至溢出适用：数据元素波动大，或者多个队列队空：

无头结点：Q.rear=NULL，Q.front=NULL带头结点：Q.front==Q.rear

（带头结点，增删操作统一）

入队：...s->next=NULL...出队：...Q.front->next=p->next，if(Q.rear==p){Q.rear=Q.front;}...

树

二叉树

N0=1N2

当有n个节点时，能组成种形态的二叉树：

卡特兰数其他的应用：一个栈的进栈序列为1，2，3，...，n，有多少个不同的出栈序列

n叉树

对于含有N个结点的n叉树树，除了头结点外还有N-1个结点，每一个节点都有一条线连接到上一层（由叶到根可以遍历），则共有N-1个指针非空。总的指针数为n*N。则空指针为：n*N-（N-1）

满二叉树

1. 结点数：2^h-1

结点i的

1. 父结点：└i/2┘
2. 左孩子结点：2i
3. 右孩子结点：2i1

哈夫曼树（最优二叉树）Huffman

目的：找出存放一串字符所需的最少的二进制编码

最小的两个合成组成二叉树。在频率表中删去他俩，并加入新的根结点。重复该步骤

默认是小在左，大在右，，所以哈弗曼编码不唯一

例如：频率表B:45,C:13D:69E:14F:5G:3

度m的哈夫曼树只有度为0和m的结点∴Nm=(n-1)/(m-1)

固定长度编码：待处理的字符串序列中，每个字符用同样长度的二进制位可变长度编码：频率高的字符短编码；平均编码长度减短，压缩数据前缀编码：没有一个编码是另外一个编码的前缀哈夫曼是前缀，可变长度编码

二叉排序树/二叉查找树BST（BinarySearch/SortTree）

左子树的关键字＜根结点＜右子树的关键字判断是否为BST：中序序列递增=>B为BST，即pre<bt->data

平衡二叉树AVL

任一结点的左子树和右子树的深度之差≤1插入：若需调整，则每次调整对象必为最小不平衡二叉树

查找：Nh表示深度为h最少结点数，则N0=0，N1=1，N2=2，Nh=Nh-1Nh-21

大根堆

左/右子树的关键字≤根结点，完全二叉树

最小生成树

1. 定义：连通，无向带权图的生成树，权值之和最小的
2. 唯一：当任意环中边的权值相异，则最小生成树唯一

普里姆Prim算法

克鲁斯卡Kruskal算法

共同

基于贪心算法

特点

从顶点开始扩展最小生成树

按权递增次序，选择不构成环的边

T(n)

O(|V|^2)

O(|E|log2|E|)

堆存放E，每次选最小权值边O(log2|E|)

T所有边看成等价类，每次边，看成求等价类∴并查集描述T，

∴构造T需O(|E|)

适用

稠密图

稀疏图

森林

对应树森林1次对应二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历

先序确定的二叉树个数

∵先序中序可唯一确定一棵二叉树其关系就如入栈序列出栈序列可唯一确定一个栈∴先序确定二叉树个数，即先序确定中序个数，NLR确定LNR，LN、NL相当于压栈，R相当于进了立即出∴h(n)=Catalan卡特兰数=

带权路径长度WPL

WPL=∑（weight*路径边数）=(162130)*2(1012)*3=200

查找次数=路径上的结点数，路径长度=路径上的边数

图

完全图

1. 无向：任意两个顶点间，只有一条边，n(n-1)/2条边
2. 有向：任意两个顶点间，只有方向相反的两条弧，n(n-1)条弧

最短路径

Dijkstra算法

Floyd算法

问题

单源最短路径（单起源到各个顶点的最短距离，从源点的临近点开始）

各个顶点之间的最短路径

拓扑排序

1. DAG：有向无环图DirectedAcyclineGraph
2. 拓扑排序：DAG中，每个顶点只出现一次，对每个<u,v>，序列中，u在v前
3. 唯一：图为线性有序序列时，唯一；若存在顶点有多个后继则不唯一
4. 邻接矩阵：
5. 算法：

1. 输出并删除一个没有前驱的结点
2. 删除以该结点为弧头的边
3. 重复（1）（2），直到DAG为空或者不存在无前驱的结点（环）

关键路径

1. 关键路径：最长路径，工程所需时间

关键活动：最长路径上的边ve(k)：事件k最早发生时间ve(k)=0（源点），ve(k)=Max{ve(j)Weight(j,k)}vl(k)：事件k最迟发生时间vl(k)=ve(k)（汇点），vl(k)=Min{vl(j)-Weight(j,k)}e(i)：活动ai最早开始时间<vk,vj>，e(i)=vl(k)l(i)：活动ai最迟开始时间<vk,vj>，l(i)=vl(j)-Weight(k,j)d(i)：l(i)-e(i)，为0的即关键活动

适度缩短关键活动，可以缩短工期，过度时，关键活动可能变成非关键活动多关键路径时，缩短所有关键路径才缩短工期，除非有“桥”---所有关键路径的共有活动

模式匹配

主串S，长n，模式串T，长m。T在S中首次出现的位置

BF模式匹配

最坏T(n)=O(m*n)

KMP模式匹配

1. next[j]：T的第j个字符失配于S中的第i个字符，需要用T的第next[j]个字符与S中的第i个字符比较

abcdeabf（f失配，第next[j]=3个字符c比较）T起点开始，和失配点结束的最大公共前缀

1. next[1]=0：i;
2. next[2]=1，next[j]：i不变;

模式匹配过程：

1. S中第i个char，T中第j个char
2. j指向失配点/j=m（全部匹配成功）为一趟

虽KMP的T(n)=O(mn)，

但实际中BF的T(n)接近O(mn)，

∴至今采用

只有T中有很多部分匹配，KMP才明显快

内部排序算法

T(n)和S(n)

任何基于比较的算法，都可用二叉树描述判定过程，∴T(n)至少=O(nlog2n)

操作内部排序思想稳定平均S(n)T(n)平均最坏最好插入直接查找；elem插入到有序，顺序找位√1n2n2顺序n逆序折半查找；直接插入的优化，折半找位x1n2与初始序列无关希尔分治；分组直接插入排序d个组L[i,id,...,ikd]x1n1.3n2依赖f(d)交换冒泡擂台；无序中两两比较，不等则交换，至最值√1n2n2逆序n顺序快速分治；取pivot，调整至L[1...k-1]＜L(k)≤L[k1...n]xlog2nnlog2nn2最不平衡nlog2n最平衡选择简单擂台；第i趟L[i...n]，初始min=i，swap(L(min),L(i))x1n2n2逆序n2顺序堆擂台；完全二叉树，根>子结点（大根堆）x1nlog2nnlog2n逆序nlog2n顺序2-路归并分治；分组排序，两两合并相邻有序序列√nnlog2nnlog2n逆序nlog2n顺序基数多key；从优先级min的开始入队分配，收集√rd(nr)与初始序列无关

顺序/链式存储均可：（与下标无关）直接插入，冒泡，快速，简单选择，2-路归并顺序存储：（数组）折半，希尔，堆，基数

比较次数与初始状态无关：简单选择，基数T(n)与初始序列无关：折半，堆，多路归并，基数

过程特征：（每一趟确定一个elem最终位置）

第k趟确定第k小/大值：冒泡，堆，简单选择第k趟确定第i小/大值：快速

应用

考虑因素：

n待排序数目elem本身信息量大小key的结构稳定性要求语言工具条件存储结构辅助空间大小

情况：

n≤50?100：n2

链式存储/n≤50：直接插入顺序存储：折半插入elem本身信息量大：简单选择（移动少）

1000≥n＞50?100：希尔n＞1000：nlog2n

key随机分布：快速排序key位数少且可分解：基数T(n)与初始序列无关：

辅助空间小：堆稳定：归并

key基本有序：（比较：直接插入<冒泡，移动：直接插入>冒泡）

基本逆序：直接插入基本顺序：冒泡

elem本身信息量大：链式存储；避免耗费大量移动记录总体信息量大：归并排序；内存一次放不下，需要外部介质

平均查找长度ASL

顺序/线性查找

ASL无序线性表有序表succ(n1)/2failn1

折半/二分查找

判定树：描述折半查找过程ASLsucc≈log2(n1)-1

分块/索引顺序查找

优点：动态结构，快速查找基本思想：

块间：第i块maxkey<第i1块allkey块内：无序索引表：含各块的maxkey和各块第一个元素地址

ASLSucc=LILS

LI：ASL索引查找LS：ASL块内查找

分b块，每块s个记录：(b1)/2(s1)/2=

（索引表，顺序表，均顺序查找）当s=时ASLmin=1

若对索引表折半查找：┌log2(b1)┐(s1)/2

散列(Hash)表

散列表：根据关键字直接访问的数据结构对比：散列表中key和存储地址有直接映射关系，而线性表，树表等无确定映射关系散列函数：Hash(key)=Addr（数组下标，索引，内存地址）冲突：不同关键字映射到同一地址同义词：映射到同一地址的不同关键字T(n)：无冲突时，O(1)

散列函数构造要求

定义域：全部关键字值域：依赖于散列表大小/地址范围地址：计算出来的地址应等概率，均匀分布整个地址空间计算：简单，以在短时间计算出

方法Hash(key)适用不适/特点直接定址a*keybkey分布连续key分布不连续，空位多，则空间浪费除留取余keyMODp质数p左接近表长m；简单，常用平方取中key2的中间几位每一位取值都不够均匀/均＜Addr所需位数Addr与key的每一位都有关系，使Addr分布均匀数字分析数码分布均匀的几位已知Key的集合（r进制，r个数码）某些位分布不均匀，只有某几种数码经常出现折叠分割成位数相同的几部分，取这几部分的叠加和key位数多，且每一位数字上分布大致均匀key分成位数相同的几部分(最后一部分，可以短些)处理冲突

定义：同义词找下一个“空”Hash地址方法：

*Hi表示冲突后的第i次探测的散列地址，m散列表表长，di增量序列，i∈[1，m-1]

开放地址：Hi=(Hash(key)di)%m空闲地址还对同义词表项开放线性探测：di=1...di..di=m-1顺序查看下一单元，直到找到空闲单元/查遍全表

（检测到表尾地址m-1时，下一地址为表首地址0）可能大量元素在相邻散列地址堆积，大大降低了查找效率

平方/二次探测：di=（k≤m/2，m为4k3的质数）；较好，可避免堆积；

不能检测所有单元，但至少能检测一半单元

再/双散列：di=Hash2(key)；最多m-1次探测遍历全表，回到H0位置伪随机序列：di=伪随机序列

拉链/链式地址：同义词链由散列地址唯一标识；适用于经常增删

ps：∵查找时，碰到空指针就认为查找失败∴开放地址不能物理删除元素，否则会截断其他具有相同散列地址的查找地址；∴只能做删除标记∴多次删除后，散列表看起来很满，其实许多位置没用∴要定期维护散列表，把删除标记的元素物理删除性能分析

决定因素：散列函数；处理冲突的方法；装满因子α=n/m=记录数/表长ASL：与α有关

递归

代码简单，容易理解缺点：通常包含很多重复计算，效率不高精髓：将原始问题转换为属性相似的小规模问题递归工作栈：容量与递归调用最大深度一致

递归和递推的区别

• 递归：

1. 设置递归边界
2. 判断已经计算过，直接返回结果
3. 返回关系式

• 递推：

1. 初始化边界
2. 根据初始化边界开始递推
3. 循环递推

十进制转换为二进制

余数入栈

迷宫求解

已走过的0改2，且入栈，坐标周围无0时，出栈直到遇到周围有0

算法（编程题）

场景题千千万，但都是由经典算法变换而来。

优化一般靠牺牲空间换时间

经验

一般过了3道编程，过了1.5就差不多，2就稳了。但是不绝对，有的一道题也会让你面试，有的a了2，也不一定有面试机会
有没有面试机会更多看的是卷的程度，名额多少，简历（例如学历高低）

• 运用示例，摸清规律，弄懂整个逻辑后，再动手
• 10min没有完整思路的先跳过，有时候局限了，回过头可能想得出来
• 随手保存
• 不要追求AC率，后面有空再返回完善，
• 注意题目中说明输入的上限，如下

read_line()//将读取至多1024个字符，一定注意看题目字符上限

gets(n)//将读取至多n个字符，当还未达到n个时如果遇到回车或结束符

常用输出

leta=[1,2,3];

console.log(a.toString());//1,2,3arr->str

console.log(a.join(''));//123arr->str

console.log(...a);//123展开运算符...

考核方式

ACM模式

自己构造输入格式，控制返回格式，OJ不会给任何代码，不同的语言有不同的输入输出规范。

JavaScript(V8)

ACMcoderOJ

readline()获取单行字符串

key：

read_line()//将读取至多1024个字符，一定注意看题目字符上限

gets(n)//将读取至多n个字符，当还未达到n个时如果遇到回车或结束符

printsth(sth,...)//多个参数时，空格分隔；最后不加回车。

console.log(sth,...)、print(sth,...)//多个参数时，空格分隔；最后加回车

line.split('').map(e=>Number(e));//str->arr

arr.push([]);//arr[]->arr[][]

//单行输入

while(line=readline()){

//字符数组

varlines=line.split('');

//.map(Number)可以直接将字符数组变为数字数组

varlines=line.split('').map(Number);

vara=parseInt(lines[0]);//效果等同下面

varb=lines[1];//能将str转换为num

print(ab);

}

//矩阵的输入

while(line=readline()){

letnums=line.split('');//读取第一行

varrow=nums[0];//第一行的第一个数为行数

varcol=nums[1];//第一行的第二个数为列数

varmap=[];//用于存放矩阵

for(leti=0;i<row;i){

map.push([]);

letmapline=readline().split('');

for(letj=0;j<col;j){

map[i][j]=mapline[j];

}

}

}

JavaScript(Node)

华为只可以采用Javascript(Node)

牛客JavaScriptNode练习

模板1

varreadline=require('readline')

//创建读取行接口对象

constrl=readline.createInterface({

input:process.stdin,

output:process.stdout

})

单行

//监听换行，接受数据

rl.on('line',function(line){

//line为输入的单行字符串，split函数--通过空格将该行数据转换为数组。

vararr=line.split('')

//数组arr的每一项都是字符串格式，如果我们需要整型，则需要parseInt将其转换为数字

console.log(parseInt(arr[0])parseInt(arr[1]));

})

多行

constinputArr=[];//存放输入的数据

rl.on('line',function(line){

//line是输入的每一行，为字符串格式

inputArr.push(line.split(''));//将输入流保存到inputArr中（注意为字符串数组）

}).on('close',function(){

console.log(fun(inputArr))//调用函数并输出

})

//解决函数

functionfun(){

xxxxxxxx

returnxx

}

模板2

constrl=require("readline").createInterface({input:process.stdin});

variter=rl[Symbol.asyncIterator]();

constreadline=async()=>(awaititer.next()).value;

voidasyncfunction(){

//Writeyourcodehere

while(line=awaitreadline()){

lettokens=line.split('');

leta=parseInt(tokens[0]);

letb=parseInt(tokens[1]);

console.log(ab);

}

}()

核心代码模式

只需要实现函数核心功能并返回结果，无须处理输入输出

例如力扣上是核心代码模式，就是把要处理的数据都已经放入容器里，可以直接写逻辑

链表

判断链表是否有环

key：遍历链表，判断相邻结点是否相等，若结点为空，则false，若相等，则true

functionListNode(x){

this.val=x;

this.next=null;

}

/**

*

*@paramheadListNode类

*@returnbool布尔型

*/

functionhasCycle(head){

//writecodehere

if(!head||!head.next){returnfalse}

letfast=head.next

letslow=head

while(slow!==fast){

if(!fast||!fast.next){

returnfalse

}

fast=fast.next.next

slow=slow.next

}

returntrue

}

module.exports={

hasCycle:hasCycle

};

二叉树

(反)序列化二叉树

序列化二叉树，key：

• letarr=Array.isArray(s)?s:s.split("");
• leta=arr.shift();
• letnode=null;
• if(typeofa==="number")

functionTreeNode(x){

this.val=x;

this.left=null;

this.right=null;

}

//反序列化二叉树：tree->str把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串

functionSerialize(pRoot,arr=[]){

if(!pRoot){

arr.push("#");

returnarr;

}else{

arr.push(pRoot.val);//注意是val。而不是root

Serialize(pRoot.left,arr);

Serialize(pRoot.right,arr);

}

returnarr;

}

//序列化二叉树：str->tree根据字符串结果str，重构二叉树

functionDeserialize(s){

//转换为数组

letarr=Array.isArray(s)?s:s.split("");

//取出val

leta=arr.shift();

//构建二叉树结点

letnode=null;

if(typeofa==="number"){

//还有可能等于#

node=newTreeNode(a);

node.left=Deserialize(arr);

node.right=Deserialize(arr);

}

returnnode;

}

module.exports={

Serialize:Serialize,

Deserialize:Deserialize,

};

前序遍历（迭代）

入栈：中右左

出栈：中左右

/**

*Definitionforabinarytreenode.

*functionTreeNode(val,left,right){

*this.val=(val===undefined?0:val)

*this.left=(left===undefined?null:left)

*this.right=(right===undefined?null:right)

*}

*/

/**

*@param{TreeNode}root

*@return{number[]}

*/

varpreorderTraversal=function(root){

letstack=[]

letres=[]

letcur=null;

if(!root)returnres;

root&&stack.push(root)

while(stack.length){

cur=stack.pop()

res.push(cur.val)

cur.right&&stack.push(cur.right)

cur.left&&stack.push(cur.left)

}

returnres

};

中序遍历（迭代）

指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

/**

*Definitionforabinarytreenode.

*functionTreeNode(val,left,right){

*this.val=(val===undefined?0:val)

*this.left=(left===undefined?null:left)

*this.right=(right===undefined?null:right)

*}

*/

/**

*@param{TreeNode}root

*@return{number[]}

*/

varinorderTraversal=function(root){

letstack=[]

letres=[]

letcur=root

while(cur||stack.length){

if(cur){

stack.push(cur)

cur=cur.left

}else{

cur=stack.pop()

res.push(cur.val)

cur=cur.right

}

}

returnres

};

后序遍历（迭代）

和前序遍历不同：

入栈：中左右

出栈：中右左

rever出栈：左右中

/**

*Definitionforabinarytreenode.

*functionTreeNode(val,left,right){

*this.val=(val===undefined?0:val)

*this.left=(left===undefined?null:left)

*this.right=(right===undefined?null:right)

*}

*/

/**

*@param{TreeNode}root

*@return{number[]}

*/

varpostorderTraversal=function(root){

letstack=[]

letres=[]

letcur=root

if(!root)returnres

stack.push(root)

while(stack.length){

cur=stack.pop()

res.push(cur.val)

cur.left&&stack.push(cur.left)

cur.right&&stack.push(cur.right)

}

returnres.reverse()

};

层序遍历

树的层序遍历，相似图的广度优先搜索

初始设置一个空队，根结点入队队首结点出队，其左右孩子依次入队若队空，说明所有结点已处理完，结束遍历；否则（2)

/*

*functionTreeNode(x){

*this.val=x;

*this.left=null;

*this.right=null;

*}

*/

/**

*

*@paramrootTreeNode类

*@returnint整型二维数组

*/

functionlevelOrder(root){

//writecodehere

if(root==null){

return[];

}

constarr=[];

constqueue=[];

queue.push(root);

while(queue.length){

constpreSize=queue.length;

constfloor=[];//当前层

for(leti=0;i<preSize;i){

constv=queue.shift();

floor.push(v.val);

v.left&&queue.push(v.left);

v.right&&queue.push(v.right);

}

arr.push(floor);

}

returnarr;//[[1],[2,3]]

}

module.exports={

levelOrder:levelOrder,

};

判断对称二叉树

/*functionTreeNode(x){

this.val=x;

this.left=null;

this.right=null;

}*/

letflag=true;

functiondeep(left,right){

if(!left&&!right)returntrue;//可以两个都为空

if(!right||!left||left.val!==right.val){//只有一个为空或者节点值不同，必定不对称

returnfalse;

}

returndeep(left.left,right.right)&&deep(left.right,right.left);//每层对应的节点进入递归比较

}

functionisSymmetrical(pRoot){

returndeep(pRoot,pRoot);

}

module.exports={

isSymmetrical:isSymmetrical,

};

判断完全二叉树

完全二叉树：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。

/*

*functionTreeNode(x){

*this.val=x;

*this.left=null;

*this.right=null;

*}

*/

/**

*代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

*

*@paramrootTreeNode类

*@returnbool布尔型

*/

functionisCompleteTree(root){

//writecodehere

if(root==null)returntrue;

constqueue=[];

queue.push(root);

letflag=false;//是否遇到空节点

while(queue.length){

constnode=queue.shift();

if(node==null){

//如果遇到某个节点为空，进行标记，代表到了完全二叉树的最下层

flag=true;

continue;

}

if(flag==true){

//若是后续还有访问，则说明提前出现了叶子节点，不符合完全二叉树的性质。

returnfalse;

}

queue.push(node.left);

queue.push(node.right);

}

returntrue;

}

module.exports={

isCompleteTree:isCompleteTree,

};

判断平衡二叉树

平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1，同样左子树是平衡二叉树，右子树为平衡二叉树。

/*functionTreeNode(x){

this.val=x;

this.left=null;

this.right=null;

}*/

functionIsBalanced_Solution(pRoot)

{

if(!pRoot)returntrue;

//writecodehere

return(Math.abs(getMaxDepth(pRoot.left)-getMaxDepth(pRoot.right))<=1)&&IsBalanced_Solution(pRoot.left)&&IsBalanced_Solution(pRoot.right)

}

functiongetMaxDepth(root){

if(!root)return0;

returnMath.max(getMaxDepth(root.left)1,getMaxDepth(root.right)1)

}

module.exports={

IsBalanced_Solution:IsBalanced_Solution

};

二叉树的镜像

先序遍历

/*

*functionTreeNode(x){

*this.val=x;

*this.left=null;

*this.right=null;

*}

*/

/**

*代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

*

*@parampRootTreeNode类

*@returnTreeNode类

*/

functionMirror(pRoot){

functiontraversal(root){

if(root===null)return;

//交换左右孩子

lettemp=root.left;

root.left=root.right;

root.right=temp;

traversal(root.left);

traversal(root.right);

returnroot;

}

returntraversal(pRoot);

//writecodehere

}

module.exports={

Mirror:Mirror

};

最近公共祖先

如果从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，

如果从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。

/*

*functionTreeNode(x){

*this.val=x;

*this.left=null;

*this.right=null;

*}

*/

/**

*

*@paramrootTreeNode类

*@paramo1int整型

*@paramo2int整型

*@returnint整型

*/

functiondfs(root,o1,o2){

if(root==null||root.val==o1||root.val==o2){

returnroot;

}

//递归遍历左子树

letleft=dfs(root.left,o1,o2);

//递归遍历右子树

letright=dfs(root.right,o1,o2);

//如果left、right都不为空，那么代表o1、o2在root的两侧，所以root为他们的公共祖先

if(left&&right)returnroot;

//如果left、right有一个为空，那么就返回不为空的那一个

returnleft!=null?left:right;

}

数组和树

扁平结构(一维数组)转树

key：

1. pid：parentid
2. obj[item.id]={...item,children:[]}
3. pid===0
4. !obj[pid]
5. obj[pid].children.push(treeitem)

//pid：parentid

letarr=[

{id:1,name:'部门1',pid:0},

{id:2,name:'部门2',pid:1},

{id:3,name:'部门3',pid:1},

{id:4,name:'部门4',pid:3},

{id:5,name:'部门5',pid:4},

]

////上面的数据转换为下面的tree数据

//[

//{

//"id":1,

//"name":"部门1",

//"pid":0,

//"children":[

//{

//"id":2,

//"name":"部门2",

//"pid":1,

//"children":[]

//},

//{

//"id":3,

//"name":"部门3",

//"pid":1,

//"children":[

//{

//id:4,

//name:'部门4',

//pid:3,

//"children":[

//{

//id:5,

//name:'部门5',

//pid:4,

//"children":[]

//},

//]

//},

//]

//}

//]

//}

//]

functiontree(items){

//1、声明一个数组和一个对象用来存储数据

letarr=[]

letobj={}

//2、给每条item添加children，并连带一起放在obj对象里

for(letitemofitems){

obj[item.id]={...item,children:[]}

}

//3、forof逻辑处理

for(letitemofitems){

//4、把数据里面的id取出来赋值方便下一步的操作

letid=item.id

letpid=item.pid

//5、根据id将obj里面的每一项数据取出来

lettreeitem=obj[id]

//6、如果是第一项的话吧treeitem放到arr数组当中

if(pid===0){

//把数据放到arr数组里面

arr.push(treeitem)

}else{

//如果没有pid找不到就开一个obj{}

if(!obj[pid]){

obj={

children:[]

}

}

//否则给它的obj根基pid（自己定义的下标）进行查找它里面的children属性然后push

obj[pid].children.push(treeitem)

}

}

//返回处理好的数据

returnarr

}

console.log(tree(arr))

数组扁平化

要求将数组参数中的多维数组扩展为一维数组并返回该数组。
数组参数中仅包含数组类型和数字类型

functionflatten(arr){

//toString()split()实现

returnarr.toString().split(',').map(item=>Number(item));

//join()split()实现

returnarr.join(',').split(',').map(item=>Number(item));

//reduce实现

returnarr.reduce((target,item)=>{

returntarget.concat(Array.isArray(item)?flatten(item):item);

},[])

//递归实现

letres=[];

arr.forEach(item=>{

if(Array.isArray(item)){

res=res.concat(flatten(item))

}else{

res.push(item);

}

});

returnres;

//扩展运算符实现

while(arr.some(item=>Array.isArray(item))){

arr=[].concat(...arr);

}

returnarr;

//flat()实现（这里不支持使用）

returnarr.flat(Infinity);

}

排序

快速排序

快速排序的基本思想是通过分治来使一部分均比另一部分小（大）再使两部分重复该步骤而实现有序的排列。核心步骤有：

1. 选择一个基准值（pivot）
2. 以基准值将数组分割为两部分
3. 递归分割之后的数组直到数组为空或只有一个元素为止

key：

1. pivot=array.splice(pivotIndex,1)[0]
2. _quickSort(left).concat([pivot],_quickSort(right))

const_quickSort=array=>{

if(array.length<=1)returnarray

varpivotIndex=Math.floor(array.length/2)

varpivot=array.splice(pivotIndex,1)[0]

varleft=[]

varright=[]

for(vari=0;i<array.length;i){

if(array[i]<pivot){

left.push(array[i])

}else{

right.push(array[i])

}

}

return_quickSort(left).concat([pivot],_quickSort(right))

}

*归并排序

思想：两个/两个以上有序表合并成新有序表

• 2路-归并排序：两两归并
• key：

1. left=arr.slice(0,mid)
2. mergeLeft=mergeSort(left)
3. res.push(leftArr.shift())
4. res=res.concat(leftArr)

functionmergesort(arr){

if(arr.length<2)returnarr

letlen=arr.length

letmid=parseInt(len/2)

letl1=arr.slice(0,mid)

letr1=arr.slice(mid,len)

letmergeleft=mergesort(l1)

letmergeright=mergesort(r1)

returnmerge(mergeleft,mergeright)

functionmerge(left,right){

letres=[]

while(left.length!=0&&right.length!=0){

if(left[0]<=right[0]){

res.push(left.shift())

}else{

res.push((right.shift()))

}

}

if(left.length){

res=res.concat(left)

}

if(right.length){

res=res.concat(right)

}

returnres

}

}

*堆排序

1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1

3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

注意:升序用大根堆，降序就用小根堆(默认为升序)

key：

headAdjust：

1. for(vari=2*start1;i<=end;i=i*21)
2. if(i<end&&arr[i]<arr[i-1])

buildHeap：//从最后一棵子树开始,从后往前调整

1. //最大元素保存于尾部，并且不参与后面的调整
2. //进行调整，将最大元素调整至堆顶
3. headAdjust(arr,0,i);

//每次调整,从上往下调整

//调整为大根堆

functionheadAdjust(arr,start,end){

//将当前节点值进行保存

vartmp=arr[start];

//遍历孩子结点

for(vari=2*start1;i<=end;i=i*21)

{

if(i<end&&arr[i]<arr[i-1])//有右孩子并且左孩子小于右孩子

{

i--;//i一定是左右孩子的最大值

}

if(arr[i]>tmp)

{

arr[start]=arr[i];

start=i;

}

else

{

break;

}

}

arr[start]=tmp;

}

}

//构建堆

functionbuildHeap(arr){

//从最后一棵子树开始,从后往前调整

for(vari=Math.floor(arr.length/2);i>=0;i--){

headAdjust(arr,i,arr.length);

}

}

functionheapSort(arr){

//构建堆

buildHeap(arr);

for(vari=arr.length-1;i>0;i--){

//最大元素保存于尾部，并且不参与后面的调整

varswap=arr[i];

arr[i]=arr[0];

arr[0]=swap;

//进行调整，将最大元素调整至堆顶

headAdjust(arr,0,i);

}

}

回溯

如果不能成功，那么返回的时候我们就还要把这个位置还原。这就是回溯算法，也是试探算法。

全排列

通过回溯剪枝。修剪掉有当前元素的path，最后保留与原字符串长度相等的所有元素。

key：

1. path.length==string.length
2. path.includes(item)

const_permute=string=>{

constres=[];

constbacktrace=path=>{

if(path.length==string.length){

res.push(path);

return;

}

for(constitemofstring){

if(path.includes(item))continue;

backtrace(pathitem);

}

};

backtrace('');

returnres;

}

N皇后

N皇后问题是指在n*n的棋盘上要摆n个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数n，返回n皇后的摆法数。

要求：空间复杂度O(1)，时间复杂度O(n!)

1. 要确定皇后的位置，其实就是确定列的位置，因为行已经固定了
2. 进一步讲，也就是如何摆放数组arr[0,1,2,3,...,n-1]
3. 如果没有【不在同一条斜线上】要求，这题其实只是单纯的全排列问题
4. 在全排列的基础上，根据N皇后的问题，去除一些结果

• arrn个皇后的列位置

• resn皇后排列结果

• ruler记录对应的列位置是否已经占用（也是是否有皇后），如果有，那么设为1，没有设为0

• setPos哈希集合，标记正斜线（从左上到右下）位置，如果在相同正斜线上，坐标(x,y)满足y-x都相同

• setCon哈希集合，标记反正斜线（从y右上到左下）位置，如果在相同反斜线上，坐标(x,y)满足xy都相同

• 是否在同一斜线上，其实就是这两个点的所形成的斜线的斜率是否为±1。点P(a,b)，点Q(c,d)

  （1）斜率为1(d-b)/(c-a)=1，横纵坐标之差相等

  （2）斜率为-1(d-b)/(c-a)=-1，等式两边恒等变形ab=cd，横纵坐标之和相等

/**

*

*@paramnint整型then

*@returnint整型

*/

functionNqueen(n){

letres=[];//二维数组，存放每行Q的列坐标

letisQ=newArray(n).fill(0);//记录该列是否有Q

letsetPos=newSet();//标记正对角线

letsetCon=newSet();//标记反对角线

//给当前row找一个col

constbackTrace=(row,path)=>{

if(path.length===n){

res.push(path);

return;

}

for(letcol=0;col<n;col){

if(

isQ[col]==0&&

!setPos.has(row-col)&&

!setCon.has(rowcol)

){

path.push(col);

isQ[col]=1;

setPos.add(row-col);

setCon.add(rowcol);

backTrace(row1,path);

path.pop();

isQ[col]=0;

setPos.delete(row-col);

setCon.delete(rowcol);

}

}

};

backTrace(0,[]);

returnres.length;

}

module.exports={

Nqueen:Nqueen,

};

动态规划(DynamicProgramming，DP)

用来解决一类最优化问题的算法思想。考虑最简单的情况，以及下一级情况和它的关系
简单来说，动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。需要注意的是，动态规划会将每个求解过的子问题的解记录下来，这样
一般可以使用递归或者递推的写法来实现动态规划，其中递归写法在此处又称作记忆化搜索。

斐波那契(Fibonacci）数列（递归）

functionF(n){

if(n=0||n==1)return1;

elsereturnF(n-1)F(n-2);

}

dp[n]=-1表示F(n)当前还没有被计算过

functionF(n){

if(n==0lIn-1)return1;//递归边界

if(dp[n]!=-1)returndp[n];//已经计算过，直接返回结果，不再重复计算else{

elsedp[n]=F(n-1)F(n-2);1/计算F(n)，并保存至dp[n]

returndp[n];//返回F(n)的结果

}

数塔（递推）

第i层有i个数字。现在要从第一层走到第n层，最后将路径上所有数字相加后得到的和最大是多少?

dp[i][j]表示从第i行第j个数字出发到达最底层的所有路径中能得到的最大和

dp[i][i]=max(dp[i-1][j],dp[i-1][j1])f[i][j]

最长公共子序列(LCS)

LongestCommonSubsequence：子序列可以不连续
“sadstory”与“adminsorry”最长公共子序列为“adsory”

dp[i][j]表示字符串A的i号位和字符串B的j号位之前的LCS长度下标从1开始)

最长回文子串

dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为1，不是为0

最小路径和

mxn矩阵a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

dp[i][j]代表i到j的最短路径

求解子问题时的状态转移方程：从「上一状态」到「下一状态」的递推式。

dp[i,j]=min(dp[i-1][j],dp[i][j-1])matrix[i][j]

JavaScript中没有二维数组的概念，但是可以设置数组元素的值等于数组

key：

1. dp[0][i]=dp[0][i-1]matrix[0][i];
2. dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])matrix[i][j];

functionminPathSum(matrix){

varrow=matrix.length,

col=matrix[0].length;

vardp=newArray(row).fill(null).map(()=>newArray(col).fill(0));

dp[0][0]=matrix[0][0];//初始化左上角元素

//初始化第一行

for(vari=1;i<col;i)dp[0][i]=dp[0][i-1]matrix[0][i];

//初始化第一列

for(varj=1;j<row;j)dp[j][0]=dp[j-1][0]matrix[j][0];

//动态规划

for(vari=1;i<row;i){

for(varj=1;j<col;j){

dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])matrix[i][j];

}

}

returndp[row-1][col-1];//右下角元素结果即为答案

}

背包

01背包

有n件物品,每件物品的重量为w[i],价值为c[j]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都只有1件。
dp[i][v]表示前i件物品(1≤i≤n,0≤v≤V)恰好装入容量为v的背包中所能获得的最大价值。

这样修改对应到图中可以这样理解:v的枚举顺序变为从右往左，dp[i][v]右边的部分为刚计算过的需要保存给下一行使用的数据，而dp[i][v]左上角的阴影部分为当前需要使用的部分。将这两者结合一下，即把dp[i][v]左上角和右边的部分放在一个数组里，每计算出一个dp[i][v]，就相当于把dp[i-1][v]抹消，因为在后面的运算中dp[i-1][v]再也用不到了。我们把这种技巧称为滚动数组。

特别说明:

如果是用二维数组存放，v的枚举是顺序还是逆序都无所谓;

如果使用一维数组存放,则v的枚举必须是逆序!

完全背包

与01背包问题不同的是其中每种物品都有无数件。

写成一维形式之后和01背包完全相同，唯一的区别在于这里v的枚举顺序是正向枚举，而01背包的一维形式中v必须是逆向枚举。

散列/哈希Hash

空间换时间,即当读入的数为x时，就令hashTable[x]=true(说明:hashTable数组需要初始化为false，表示初始状态下所有数都未出现过)。

数字千位分割

constformat=(n)=>{

letnum=n.toString()//拿到传进来的number数字进行toString

letlen=num.length//在拿到字符串的长度

//当传进来的结果小于3也就是千位还把结果返回出去小于3不足以分割

if(len<3){

returnnum

}else{

letrender=len%3//传入number的长度是否能被3整除

console.log(render)

if(render>0){//说明不是3的整数倍

returnnum.slice(0,render)','num.slice(render,len).match(/\d{3}/g).join(',')

}else{

returnnum.slice(0,len).match(/\d{3}/g).join(',')

}

}

}

letstr=format(298000)

console.log(str)

图

DFS深度优先搜索
BFS广度优先搜索

常用方法

异或运算^

按位异或，相同为0，不同为1

运算法则：

1.交换律（随便换像乘一样）：a^b^c===a^c^b

2.任何数于0异或为任何数0^n===n

3.相同的数异或为0:n^n===0

Math

//e=2.718281828459045

Math.E;

//绝对值

Math.abs()

//基数（base）的指数（exponent）次幂，即base^exponent。

Math.pow(base,exponent)

//max,min不支持传递数组

Math.max(value0,value1,/*…,*/valueN)

Math.max.apply(null,array)

apply会将一个数组装换为一个参数接一个参数

null是因为没有对象去调用这个方法,只需要用这个方法运算

//取整

Math.floor()向下取一个整数（floor地板）

Math.ceil(x)向上取一个整数（ceil天花板）

Math.round()返回一个四舍五入的值

Math.trunc()直接去除小数点后面的值

Number

0B，0O为ES6新增

• 二进制：有前缀0b（或0B）的数值，出现0,1以外的数字会报错（b：binary）
• 八进制：有前缀0o（或0O）的数值，或者是以0后面再跟一个数字（0-7）。如果超出了前面所述的数值范围，则会忽略第一个数字0，视为十进制数（o：octonary）
• 注意：八进制字面量在严格模式下是无效的，会导致支持该模式的JavaScript引擎抛出错误
• 十六进制：有前缀0x，后跟任何十六进制数字（0~9及A~F），字母大小写都可以，超出范围会报错

特殊值：

• Number.MIN_VALUE：5e-324
• Number.MAX_VALUE：1.7976931348623157e308
• Infinity，代表无穷大，如果数字超过最大值，js会返回Infinity，这称为正向溢出(overflow)；
• -Infinity，代表无穷小，小于任何数值，如果等于或超过最小负值-1023（即非常接近0），js会直接把这个数转为0，这称为负向溢出(underflow)
• NaN，Notanumber，代表一个非数值
• isNaN()：用来判断一个变量是否为非数字的类型，如果是数字返回false;如果不是数字返回true。
• isFinite()：数值是不是有穷的

varresult=Number.MAX_VALUENumber.MAX_VALUE;

console.log(isFinite(result));//false

• typeofNaN//'number'---NaN不是独立的数据类型，而是一个特殊数值，它的数据类型依然属于Number
• NaN===NaN//false　　---NaN不等于任何值，包括它本身
• (1/0)===(1/-0)//false　　---除以正零得到Infinity，除以负零得到-Infinity，这两者是不相等的

科学计数法：

对于那些极大极小的数值，可以用e表示法（即科学计数法）表示的浮点数值表示。

等于e前面的数值乘以10的指数次幂

numObj.toFixed(digits)//用定点表示法来格式化一个数值

functionfinancial(x){

returnNumber.parseFloat(x).toFixed(2);

}

console.log(financial(123.456));

//Expectedoutput:"123.46"

console.log(financial(0.004));

//Expectedoutput:"0.00"

console.log(financial('1.23e5'));

//Expectedoutput:"123000.00"

取余是数学中的概念，

取模是计算机中的概念，

两者都是求两数相除的余数

1.当两数符号相同时，结果相同，比如：7%4与7Mod4结果都是3

2.当两数符号不同时，结果不同，比如(-7)%4=-3和(-7)Mod4=1

取余运算，求商采用fix函数，向0方向舍入，取-1。因此(-7)%4商-1余数为-3
取模运算，求商采用floor函数，向无穷小方向舍入，取-2。因此(-7)Mod4商-2余数为1

key：((n%m)m)%m;

Number.prototype.mod=function(n){

return((this%n)n)%n;

}

//或

functionmod(n,m){

return((n%m)m)%m;

}

Map

保存键值对，任何值（对象或者基本类型）都可以作为一个键或一个值。

Map的键可以是任意值，包括函数、对象或任意基本类型。
object的键必须是一个String或是Symbol。

constcontacts=newMap()

contacts.set('Jessie',{phone:"213-555-1234",address:"123N1stAve"})

contacts.has('Jessie')//true

contacts.get('Hilary')//undefined

contacts.delete('Jessie')//true

console.log(contacts.size)//1

functionlogMapElements(value,key,map){

console.log(`m[${key}]=${value}`);

}

newMap([['foo',3],['bar',{}],['baz',undefined]])

.forEach(logMapElements);

//Expectedoutput:"m[foo]=3"

//Expectedoutput:"m[bar]=[objectObject]"

//Expectedoutput:"m[baz]=undefined"

Set

值的集合，且值唯一

letsetPos=newSet();

setPos.add(value);//Boolean

setPos.has(value);

setPos.delete(value);

functionlogSetElements(value1,value2,set){

console.log(`s[${value1}]=${value2}`);

}

newSet(['foo','bar',undefined]).forEach(logSetElements);

//Expectedoutput:"s[foo]=foo"

//Expectedoutput:"s[bar]=bar"

//Expectedoutput:"s[undefined]=undefined"

set判断值相等的机制

//Set用===判断是否相等

constset=newSet();

constobj1={x:10,y:20},obj2={x:10,y:20}

set.add(obj1).add(obj2);

console.log(obj1===obj2);//false

console.log(set.size);//2

set.add(obj1);

console.log(obj1===obj1);//true

console.log(set.size);//2

数组去重（⭐手写）

//Usetoremoveduplicateelementsfromthearray

constnumbers=[2,3,4,4,2,3,3,4,4,5,5,6,6,7,5,32,3,4,5]

console.log([...newSet(numbers)])

//[2,3,4,5,6,7,32]

Array

//创建字符串

//join()方法将一个数组（或一个类数组对象）的所有元素连接成一个字符串并返回这个字符串，用逗号

或指定的分隔符字符串分隔。如果数组只有一个元素，那么将返回该元素而不使用分隔符。

Array.join()

Array.join(separator)

//################创建数组：

//伪数组转成数组

Array.from(arrayLike,mapFn)

console.log(Array.from('foo'));

//Expectedoutput:Array["f","o","o"]

console.log(Array.from([1,2,3],x=>xx));

//Expectedoutput:Array[2,4,6]

console.log(Array.from({length:3},(item,index)=>index));//列的位置

//Expectedoutput:Array[0,1,2]

//################原数组会改变：

arr.reverse()//返回翻转后的数组

//无函数

arr.sort()//默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16

//比较函数

arr.sort(compareFn)

functioncompareFn(a,b){

if(在某些排序规则中，a小于b){

return-1;

}

if(在这一排序规则下，a大于b){

return1;

}

//a一定等于b

return0;

}

//升序

functioncompareNumbers(a,b){

returna-b;

}

//固定值填充

arr.fill(value)

arr.fill(value,start)

arr.fill(value,start,end)

//去除

array.shift()//从数组中删除第一个元素，并返回该元素的值。

array.pop()//从数组中删除最后一个元素，并返回该元素的值。此方法会更改数组的长度。

array.push()//将一个或多个元素添加到数组的末尾，并返回该数组的新长度

//unshift()方法将一个或多个元素添加到数组的开头，并返回该数组的新长度

array.unshift(element0,element1,/*…,*/elementN)

//粘接，通过删除或替换现有元素或者原地添加新的元素来修改数组，并以数组形式返回被修改的内容。

array.splice(start)

array.splice(start,deleteCount)

array.splice(start,deleteCount,item1)

array.splice(start,deleteCount,item1,item2...itemN)

//################原数组不会改变：

//切片，浅拷贝（包括begin，不包括end）。

array.slice()

array.slice(start)

array.slice(start,end)

//展平，按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回。

array.flat()//不写参数默认一维

array.flat(depth)

//过滤器，函数体为条件语句

//箭头函数

filter((element)=>{/*…*/})

filter((element,index)=>{/*…*/})

filter((element,index,array)=>{/*…*/})

array.filter(str=>str.length>6)

//遍历数组处理

//箭头函数

map((element)=>{/*…*/})

map((element,index)=>{/*…*/})

map((element,index,array)=>{/*…*/})

array.map(el=>Math.pow(el,2))

//map和filter同参

//接收一个函数作为累加器，数组中的每个值（从左到右）开始缩减，最终计算为一个值。

//箭头函数

reduce((previousValue,currentValue)=>{/*…*/})

reduce((previousValue,currentValue,currentIndex)=>{/*…*/})

reduce((previousValue,currentValue,currentIndex,array)=>{/*…*/})

reduce((previousValue,currentValue)=>{/*…*/},initialValue)

reduce((previousValue,currentValue,currentIndex)=>{/*…*/},initialValue)

array.reduce((previousValue,currentValue,currentIndex,array)=>{/*…*/},initialValue)

//一个“reducer”函数，包含四个参数：

//previousValue：上一次调用callbackFn时的返回值。

//在第一次调用时，若指定了初始值initialValue，其值则为initialValue，

//否则为数组索引为0的元素array[0]。

//currentValue：数组中正在处理的元素。

//在第一次调用时，若指定了初始值initialValue，其值则为数组索引为0的元素array[0]，

//否则为array[1]。

//currentIndex：数组中正在处理的元素的索引。

//若指定了初始值initialValue，则起始索引号为0，否则从索引1起始。

//array：用于遍历的数组。

//initialValue可选

//作为第一次调用callback函数时参数previousValue的值。

//若指定了初始值initialValue，则currentValue则将使用数组第一个元素；

//否则previousValue将使用数组第一个元素，而currentValue将使用数组第二个元素。

constarray1=[1,2,3,4];

//01234

constinitialValue=0;

constsumWithInitial=array1.reduce(

(accumulator,currentValue)=>accumulatorcurrentValue,

initialValue

);

console.log(sumWithInitial);

//Expectedoutput:10

String

str.charAt(index)//获取第n位字符

str.charCodeAt(n)//获取第n位UTF-16字符编码（Unicode）A是65，a是97

String.fromCharCode(num1[,...[,numN]])//根据UTF编码创建字符串

String.fromCharCode('a'.charCodeAt(0))='a'

str.trim()//返回去掉首尾的空白字符后的新字符串

str.split(separator)//返回一个以指定分隔符出现位置分隔而成的一个数组，数组元素不包含分隔符

conststr='Thequickbrownfoxjumpsoverthelazydog.';

constwords=str.split('');

console.log(words[3]);

//Expectedoutput:"fox"

str.toLowerCase()//字符串转小写；

str.toUpperCase()//字符串转大写；

str.concat(str2,[,...strN])

str.substring(indexStart[,indexEnd])//提取从indexStart到indexEnd（不包括）之间的字符。

str.substr(start[,length])//没有严格被废弃(asin"removedfromtheWebstandards"),但它被认作是遗留的函数并且可以的话应该避免使用。它并非JavaScript核心语言的一部分，未来将可能会被移除掉。

str.indexOf(searchString[,position])//在大于或等于position索引处的第一次出现。

str.match(regexp)//找到一个或多个正则表达式的匹配。

constparagraph='Thequickbrownfoxjumpsoverthelazydog.Itbarked.';

letregex=/[A-Z]/g;

letfound=paragraph.match(regex);

console.log(found);

//Expectedoutput:Array["T","I"]

regex=/[A-Z]/;

found=paragraph.match(regex);

console.log(found);

//Expectedoutput:Array["T"]

//match类似indexOf()和lastIndexOf()，但是它返回指定的值，而不是字符串的位置。

varstr='123123000'

str.match(/\w{3}/g).join(',')//123,123,000

str.search(regexp)//如果匹配成功，则search()返回正则表达式在字符串中首次匹配项的索引;否则，返回-1

constparagraph='?Thequick';

//Anycharacterthatisnotawordcharacterorwhitespace

constregex=/[^\w\s]/g;

console.log(paragraph.search(regex));

//Expectedoutput:0

str.repeat(count)//返回副本

str.replace(regexp|substr,newSubStr|function)//返回一个由替换值（replacement）替换部分或所有的模式（pattern）匹配项后的新字符串。

constp='lazydog.Doglazy';//如果pattern是字符串，则仅替换第一个匹配项。

console.log(p.replace('dog','monkey'));

//"lazymonkey.Doglazy"

letregex=/dog/i;//如果非全局匹配，则仅替换第一个匹配项

console.log(p.replace(regex,'ferret'));

//"lazyferret.Doglazy"

regex=/d|Dog/g;

console.log(p.replace(regex,'ferret'));

//"lazyferretog.ferretlazy"

//当使用一个regex时，您必须设置全局（“g”）标志，否则，它将引发TypeError：“必须使用全局RegExp调用replaceAll”。

constp='lazydog.doglazy';//如果pattern是字符串，则仅替换第一个匹配项。

console.log(p.replaceAll('dog','monkey'));

//"lazymonkey.monkeylazy"

letregex=/dog/g;//如果非全局匹配，则仅替换第一个匹配项

console.log(p.replaceAll(regex,'ferret'));

//"lazyferret.ferretlazy"

正则表达式RegularExpression(RegExp)

RegExp对象是一个预定义了属性和方法的正则表达式对象

字面量和字符串

//以下三种表达式都会创建相同的正则表达式：

/abc/i;//字面量形式/正则表达式主体/修饰符(可选)

newRegExp('abc','i');//首个参数为字符串模式的构造函数

newRegExp(/abc/,'i');//首个参数为常规字面量的构造函数

//防止在字符串中被解译成一个转义字符

varre=newRegExp("\\w");//需要常规的字符转义规则（在前面加反斜杠\）

varre=/\w/;

当表达式被赋值时，字面量形式提供正则表达式的编译（compilation）状态，

当正则表达式保持为常量时使用字面量。

例如在循环中使用字面量构造一个正则表达式时，正则表达式不会在每一次迭代中都被重新编译（recompiled）。

正则表达式对象的构造函数，如newRegExp('abc')提供了正则表达式运行时编译（runtimecompilation）。

如果你知道正则表达式模式为变量，如用户输入，这些情况都可以使用构造函数。

regexp.test和regexp.exec

regexp.test(str)返回Bool

regexp.exec(str)返回匹配的子串或者null

常用修饰符

• iignoreCase执行对大小写不敏感的匹配。
• gglobal执行全局匹配（查找所有匹配而非在找到第一个匹配后停止）。
• ysticky粘性匹配从源字符串的RegExp.prototype.lastIndex位置开始匹配，

lastIndex

只有"g"或"y"标志时，lastIndex才会起作用。

y：下一次匹配一定在lastIndex位置开始；

g：下一次匹配可能在lastIndex位置开始，也可能在这个位置的后面开始。

lastIndex>str.length，则匹配失败，

匹配失败，则lastIndex被设置为0。

letstr='#foo#'

letregex=/foo/y

regex.lastIndex=1

regex.test(str)//true

regex.lastIndex=5

regex.test(str)//false(lastIndexistakenintoaccountwithstickyflag)

regex.lastIndex//0(resetaftermatchfailure)

分组

‘(正则表达式)’每一个分组都是一个子表达式

回溯引用

（backreference）指的是模式的后面部分引用前面已经匹配到的子字符串。

回溯引用的语法像\1,\2,....,其中\1表示引用的第一个子表达式，\2表示引用的第二个子表达式，以此类推。而\0则表示整个表达式。

匹配两个连续相同的单词:\b(\w)\s\1
Hellowhatwhatisthefirstthing,andIamamscq000.

回溯引用在替换字符串中十分常用，语法上有些许区别，用$1,$2...来引用要被替换的字符

varstr='abcabc123';

str.replace(/(ab)c/g,'$1g');

//得到结果'abgabg123'

匹配

选择匹配：(子模式)|(子模式)

多重选择模式：在多个子模式之间加入选择操作符。

为了避免歧义：(子模式)。

varr=/(abc)|(efg)|(123)|(456)/;

惰性匹配：最小化匹配

重复类量词都具有贪婪性，在条件允许的前提下，会匹配尽可能多的字符。

• ?、{n}和{n,m}重复类具有弱贪婪性，表现为贪婪的有限性。
• *、和{n,}重复类具有强贪婪性，表现为贪婪的无限性。

越左的重复类量词优先级越高，会在保证右侧重复类量词最低匹配次数基础上，使最左侧的重复类量词尽可能占有所有字符。

vars="<html><head><title></title></head><body></body></html>";

varr=/(<.*>)(<.*>)/

vara=s.match(r);

console.log(a[0])//整个表达式匹配'<html><head><title></title></head><body></body></html>'

console.log(a[1]);//左侧表达式匹配"<html><head><title></title></head><body></body></html>"

console.log(a[2]);//右侧表达式匹配“</html>”

定义：在满足条件的前提下，尽可能少的匹配字符。

方法：在重复类量词后面添加问号?限制词。

贪婪匹配体现了最大化匹配原则，惰性匹配则体现最小化匹配原则。

vars="<html><p><title></title></head><body></body></html>";

varr=/<.*?>/

vara=s.match(r);//返回单个元素数组["<html>"]而不是最短的<p>

针对6种重复类惰性匹配的简单描述如下：

• {n,m}?：尽量匹配n次，但是为了满足限定条件也可能最多重复m次。
• {n}?：尽量匹配n次。
• {n,}?：尽量匹配n次，但是为了满足限定条件也可能匹配任意次。
• ??：尽量匹配，但是为了满足限定条件也可能最多匹配1次，相当于{0,1}?。
• ?：尽量匹配1次，但是为了满足限定条件也可能匹配任意次，相当于{1,}?。
• *?：尽量不匹配，但是为了满足限定条件也可能匹配任意次，相当于{0,}?。

前/后向查找：匹配括号中的内容（不包含括号）

包括括号：\[\S?\]

不包括括号：(?<=\[)\S?(?=\])

后向查找：(?<=exp)是以exp开头的字符串,但不包含本身.

负后向查找：(?<!exp)，被指定的子表达式不能被匹配到。

前向查找：(?=exp)就匹配为exp结尾的字符串,但不包含本身.

负前向查找:：(?!exp),被指定的子表达式不能被匹配到。

\S匹配任何非空白字符。等价于[^\f\n\r\t\v]。

如果不支持后向查找：将字符串进行翻转，然后再使用前向查找，作完处理后再翻转回来

技巧

反义字符

可以匹配很多无法直接描述的字符，达到以少应多的目的。

varr=/[^0123456789]/g;

边界量词

边界就是确定匹配模式的位置，如字符串的头部或尾部，具体说明如表所示。

JavaScript正则表达式支持的边界量词

量词	说明
^	匹配开头，在多行检测中，会匹配一行的开头
$	匹配结尾，在多行检测中，会匹配一行的结尾

1. vars="howareyou"

1)匹配最后一个单词

varr=/\w$/;

vara=s.match(r);//返回数组["you"]

2)匹配第一个单词

varr=/^\w/;

vara=s.match(r);//返回数组["how"]

3)匹配每一个单词

varr=/\w/g;

vara=s.match(r);//返回数组["how","are","you"]

应用

str.split()

使用正则来划分带有多种行结束符和换行符的文本

//对于不同的平台（Unix，Windows等等），其默认的行结束符是不一样的。而下面的划分方式适用于所有平台。

lettext='Sometext\nAndsomemore\r\nAndyet\rThisistheend'

letlines=text.split(/\r\n|\r|\n/)

console.log(lines)//logs['Sometext','Andsomemore','Andyet','Thisistheend']

str.match()

在字符范围内可以混用各种字符模式。

vars="abcdez";//字符串直接量

varr=/[abce-z]/g;//字符a、b、c，以及从e~z之间的任意字符

vara=s.match(r);//返回数组["a","b","c","e","z"]

str.match(regexp)//找到一个或多个正则表达式的匹配。

constparagraph='Thequickbrownfoxjumpsoverthelazydog.Itbarked.';

letregex=/[A-Z]/g;

letfound=paragraph.match(regex);

console.log(found);

//Expectedoutput:Array["T","I"]

regex=/[A-Z]/;

found=paragraph.match(regex);

console.log(found);

//Expectedoutput:Array["T"]

//match类似indexOf()和lastIndexOf()，但是它返回指定的值，而不是字符串的位置。

varstr='123123000'

str.match(/\w{3}/g).join(',')//123,123,000

str.replace()

使用正则改变数据结构

letre=/(\w)\s(\w)/;//匹配姓名firstlast输出新的格式last,first。

letstr="JohnSmith";

letnewstr=str.replace(re,"$2,$1");//$1和$2指明括号里先前的匹配

console.log(newstr);//"Smith,John".

str.replace(regexp|substr,newSubStr|function)//返回一个由替换值（replacement）替换部分或所有的模式（pattern）匹配项后的新字符串。

constp='lazydog.Doglazy';//如果pattern是字符串，则仅替换第一个匹配项。

console.log(p.replace('dog','monkey'));

//"lazymonkey.Doglazy"

letregex=/dog/i;//如果非全局匹配，则仅替换第一个匹配项

console.log(p.replace(regex,'ferret'));

//"lazyferret.Doglazy"

regex=/d|Dog/g;

console.log(p.replace(regex,'ferret'));

//"lazyferretog.ferretlazy"

//当使用一个regex时，您必须设置全局（“g”）标志，否则，它将引发TypeError：“必须使用全局RegExp调用replaceAll”。

constp='lazydog.doglazy';//如果pattern是字符串，则仅替换第一个匹配项。

console.log(p.replaceAll('dog','monkey'));

//"lazymonkey.monkeylazy"

letregex=/dog/g;//如果非全局匹配，则仅替换第一个匹配项

console.log(p.replaceAll(regex,'ferret'));

//"lazyferret.ferretlazy"

设计对提交的表单字符串进行敏感词过滤。先设计一个敏感词列表，然后使用竖线把它们连接在一起，定义选择匹配模式，最后使用字符串的replace()方法把所有敏感字符替换为可以显示的编码格式。

vars='<metacharset="utf-8">';//待过滤的表单提交信息

varr=/\'|\"|\<|\>/gi;//过滤敏感字符的正则表达式

functionf(){//替换函数

把敏感字符替换为对应的网页显示的编码格式

return"&#"arguments[0].charCodeAt(0)";";

}

vara=s.replace(r,f);//执行过滤替换

document.write(a);//在网页中显示正常的字符信息

console.log(a);

str.serach()

str.search(regexp)//如果匹配成功，则search()返回正则表达式在字符串中首次匹配项的索引;否则，返回-1

constparagraph='?Thequick';

//Anycharacterthatisnotawordcharacterorwhitespace

constregex=/[^\w\s]/g;

console.log(paragraph.search(regex));

//Expectedoutput:0

合法的URL

URL结构一般包括协议、主机名、主机端口、路径、请求信息、哈希

1. 首先必须是以http(s)开头并且可以不包含协议头部信息
2. 主机名可以使用"-"符号，所以两种情况都要判断，包含"-"或不包含"-"
3. 顶级域名很多，直接判断"."之后是否为字母即可
4. 最后判断端口、路径和哈希，这些参数可有可无

 域名中只能包含以下字符
  1.26个英文字母
  2."0，1，2，3，4，5，6，7，8，9"十个数字
  3."-"(英文中的连词号，但不能是第一个字符)

https://www.bilibili.com/video/BV1F54y1N74E/?spm_id_from=333.337.search-card.all.click&vd_source=6fd32175adc98c97cd87300d3aed81ea

//开始:^

//协议:http(s)?:\/\/

//域名:[A-z0-9]-[A-z0-9]|[A-z0-9]

//顶级域名如comcn,2-6位:[a-zA-Z]{2,6}

//端口数字:(\d)?

//路径任意字符如/login:(\/.)?

//哈希?和#，如?age=1:(\?.)?(#.)?

//结束:$

//https://www.bilibilicom/video/BV1F54y1N74E?spm..

/^(http(s)?:\/\/)?(([a-zA-Z0-9]-[a-zA-Z0-9]|[a-zA-Z0-9])\.)([a-zA-Z]{2,6})(:\d)?(\/.)?(\?.)?(#.)?$/.test(url)

常用字符

\标记下一个字符是特殊字符或文字。例如，"n”和字符"n”匹配。"\n"则和换行字符匹配。

^匹配输入的开头.
$匹配输入的末尾

·匹配除换行字符外的任何单个字符
*匹配前一个字符零或多次。例如，"zo*”与"z”或"zoo”匹配。
匹配前一个字符一次或多次。例如，"zo"与"zoo”匹配，但和"z”不匹配。
?匹配前一个字符零或一次。例如，"a?ve?”和"never"中的“"ve”匹配。
x|y匹配x或y
{n}匹配n次。n是非负整数
{n,}n是一个非负整数。至少匹配n次。例如，"o{2,)"和"Bob”中的"o”不匹配，但和"foooood"中的所有o匹配。"o{1}”与"o”等效。"o{0,}”和"o*”等效。
{n,m}m和n是非负整数。至少匹配n次而至多匹配m次。例如，"o{1,3]"和"fooooood”中的前三个o匹配。"o{0,1}”和“o?”等效。
[xyz]匹配括号内的任一字符。例如，"[abc]"和"plain”中的"a”匹配。

[^xyz]匹配非括号内的任何字符。例如，"[^abc]"和“plain”中的"p”匹配。
[a-z]字符范围。和指定范围内的任一字符匹配。例如，"[a-z]”匹配"a"到"z"范围内的任一小写的字母表字符。

[^m-z]否定字符范围。匹配不在指定范围内的任何字符。例如，"[m-z]”匹配不在"m"到"z"范围内的任何字符。

助记：digital

\d匹配数字字符。等价于[0-9]。
\D匹配非数字字符。等价于[^0-9]。

助记：space

\s匹配任何空白，包括空格、制表、换页等。与"[\fn\rlt\v]”等效。
\S匹配任何非空白字符。与"[^\fn\rlt\v]”等效。

\w匹配包括下划线在内的任何字字符。与"[A-Za-z0-9_]”等效。

\W匹配任何非字字符。与"[^A-Za-z0-9_]”等效。

元字符表

元字符	描述
.	查找单个字符，除了换行和行结束符
\w	查找单词字符
\W	查找非单词字符
\d	查找数字
\D	查找非数字字符
\s	查找空白字符
\S	查找非空白字符
\b	匹配单词边界
\B	匹配非单词边界
\0	查找NUL字符
\n	查找换行符
\f	查找换页符
\r	查找回车符
\t	查找制表符
\v	查找垂直制表符
\xxx	查找以八进制数xxxx规定的字符
\xdd	查找以十六进制数dd规定的字符
\uxxxx	查找以十六进制xxxx规定的Unicode字符

[A-z]和[a-zA-Z]

[A-z]将在范围匹配的ASCII字符从A到z，

[a-zA-Z]将在范围中的范围匹配的ASCII字符从A到Z和从a到z。

查看ASCII字符的thistable，则会看到A-z包含[,\,],^,_，```

leetcode刷题攻略

基础笔试套路