前端笔试常考设计模式，操作系统，数据结构，ACM模板，经典算法，正则表达式，常用方法

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

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()优点：

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

//请假审批，需要组长审批、经理审批、总监审批classAction{constructor(name){this.name=namethis.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()优点：

constp1=newPromise((resolve,reject)=>{setTimeout(()=>{resolve('result')},1000);})p1.then(res=>console.log(res),err=>console.log(err))分析Promise的调用流程：

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

在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)}}//实现同resolvelet_reject=(val)=>{while(this._rejectQueue.length){constcallback=this._rejectQueue.shift()callback(val)}}//newPromise()时立即执行executor,并传入resolve和rejectexecutor(_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的资源必须由Pi+1满足（当各类资源＝1，则循环等待＝死锁）

处理

预防

避免

检测

分配

严格，

宁愿闲置资源

折中，

运行时判断是否可能死锁

宽松，并发性最强

只要允许就分配

操作

破坏必要条件之一：

一次请求all；剥夺；按资源序分配

算法通过是否安全状态，找可能的安全序列

定期检查是否死锁

优点

适用突发处理，不必剥夺

不必剥夺，限制条件弱，系统性能较好

允许对死锁现场处理

缺点

剥夺次数过多；不便灵活申请资源

需知将来需求资源；

可能长时阻塞进程

剥夺解除死锁，造成损失

破坏必要条件：

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

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

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

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

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

（含作业/进程）

FCFS

短作业优先

高响应比

RR

多级反馈队列

抢占

x

√

对内算法

非抢占

√（默认）

适用

无

批处理OS

分时

通用

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

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

分配策略算法

首次适应FF

最佳适应BF

最坏适应WF

邻近适用NF

空闲分区链接

地址递增

容量递增

容量递减

循环首次适应

性能

最简单、快、好

最多外部碎片

很快没大内存块

内存末尾碎片

比较

（∵留下了高地址的大空闲区，∴更可能满足进程）

优于顺序：FF可能>BF>WF，FF通常>NF

使用位：每一帧关联一个附加位/访问位

使用位置1：首次装入/再被访问

候选帧集合：看做循环缓冲区，有一个指针与之关联

替换：按装入顺序扫描/上次扫描位置，扫描查找到0的帧，之前的1帧置0

替换第一个帧（u＝0，m＝0）

重新扫描，替换第一个帧（u＝0，m＝1），跳过的帧u置0

指针回到最初位置，所有帧u置0，重复①

a

-->

b

c

^

下标

data

next

0

2

1

4

3

-1

（以入栈12345为例）

（1）出栈p首时，p前的序列A，只能逆序出栈，且插在A中每个元素后面

eg：4****；4_3_2_1_

（2）p出栈序列的前一个元素p1，可能为p的前面的或后一个结点

eg：出栈p1,3则p1可能=1,2;4

卡特兰数Catalan

初始S.top=-1，即top指向栈顶

S.top=0

共享栈，top指向栈顶

栈顶元素

S.data[S.top]

S.data[S.top-1]

进栈

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在两操作数中的位置

后缀表达式

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

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

否则，依次弹出当前处理符≤栈内优先级的运算符，

直到遇‘(’or优先级<当前处理符

待处理序列

当前扫描元素

动作

a*b+(-c)

a加入后缀表达式

*b+(-c)

*

*入栈

b+(-c)

b加入后缀表达式

+(-c)

ab

+

+<栈顶*，弹出*

+入栈

(-c)

ab*

(

(入栈

-c)

+(

-

栈顶为(，-入栈

c)

+(-

c加入后缀表达式

)

ab*c

把栈中(之后的符号入后缀，并删(

ab*c-

扫描完毕，运算符依次退栈，入后缀

ab*c-+

完成

操作符

#

（

*,/

+,-

）

isp栈内优先

5

6

icp栈外优先

步骤

扫描项

项类型

栈内

输出

‘#’进栈，读下一符号

操作数

直接输出

isp(‘#’)

#*

isp(‘*’)>icp(‘+’)，退栈并输出

isp(‘#’)

#+

isp(‘-’)

#+（

7

isp(‘（’)

#+（-

8

9

isp(‘-’)>icp(‘）’)，退栈并输出

10

isp(‘（’)==icp(‘）’)，直接退栈

11

isp(‘+’)>icp(‘#’)，退栈并输出

12

isp(‘#’)==icp(‘#’)，退栈，结束

队非空时，

Q.front指向队头元素的上一个元素，Q.rear指向队尾元素

Q.front指向队头元素，Q.rear指向队尾元素的下一个位置

∵假溢出：初始Q.front==Q.rear=0;“队满”Q.front==Q.rear

∴循环队列

x=Q.data[Q.front];

Q.front=(Q.front+1)%MaxSize

链队列

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

N0=1+N2

结点i的

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

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

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

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

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

左子树的关键字＜根结点＜右子树的关键字

判断是否为BST：中序序列递增=>B为BST，即predata

任一结点的左子树和右子树的深度之差≤1

插入：若需调整，则每次调整对象必为最小不平衡二叉树

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

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

普里姆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相当于进了立即出

WPL=∑（weight*路径边数）=(16+21+30)*2+(10+12)*3=200

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

Dijkstra算法

Floyd算法

问题

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

各个顶点之间的最短路径

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

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

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

模式匹配过程：

虽KMP的T(n)=O(m+n)，

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

∴至今采用

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

内部排序

思想

稳定

平均

S(n)

最坏

最好

插

入

直接

查找；elem插入到有序，顺序找位

n2

n2顺序

n逆序

折半

查找；直接插入的优化，折半找位

n2与初始序列无关

希尔

分治；分组直接插入排序d个组L[i,i+d,...,i+kd]

n1.3

依赖f(d)

交换

冒泡

擂台；无序中两两比较，不等则交换，至最值

n2逆序

n顺序

快速

分治；取pivot，调整至L[1...k-1]＜L(k)≤L[k+1...n]

log2n

nlog2n

n2最不平衡

nlog2n最平衡

选择

简单

擂台；第i趟L[i...n]，初始min=i，swap(L(min),L(i))

堆

擂台；完全二叉树，根>子结点（大根堆）

nlog2n逆序

nlog2n顺序

2-路归并

分治；分组排序，两两合并相邻有序序列

n

基数

多key；从优先级min的开始入队分配，收集

r

d(n+r)与初始序列无关

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

过程特征：（每一趟确定一个elem最终位置）第k趟确定第k小/大值：冒泡，堆，简单选择第k趟确定第i小/大值：快速

key基本有序：（比较：直接插入<冒泡，移动：直接插入>冒泡）基本逆序：直接插入基本顺序：冒泡elem本身信息量大：链式存储；避免耗费大量移动记录总体信息量大：归并排序；内存一次放不下，需要外部介质

ASL

无序线性表

有序表

succ

(n+1)/2

fail

n+1

判定树：描述折半查找过程

ASLsucc≈log2(n+1)-1

散列函数构造

要求

方法

Hash(key)

不适/特点

直接定址

a*key+b

key分布连续

key分布不连续，空位多，则空间浪费

除留取余

keyMODp

质数p左接近表长m；简单，常用

平方取中

key2的中间几位

每一位取值都不够均匀

/均＜Addr所需位数

Addr与key的每一位都有关系，

使Addr分布均匀

数字分析

数码分布均匀的几位

已知Key的集合

（r进制，r个数码）

某些位分布不均匀，

只有某几种数码经常出现

折叠

分割成位数相同的几部分，

取这几部分的叠加和

key位数多，且每一位

数字上分布大致均匀

key分成位数相同的几部分

(最后一部分，可以短些)

处理冲突

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

（检测到表尾地址m-1时，下一地址为表首地址0）

可能大量元素在相邻散列地址堆积，大大降低了查找效率

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

ps：

∵查找时，碰到空指针就认为查找失败

∴开放地址不能物理删除元素，否则会截断其他具有相同散列地址的查找地址；

∴只能做删除标记∴多次删除后，散列表看起来很满，其实许多位置没用

∴要定期维护散列表，把删除标记的元素物理删除

性能分析

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

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

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

read_line()//将读取至多1024个字符，一定注意看题目字符上限gets(n)//将读取至多n个字符，当还未达到n个时如果遇到回车或结束符常用输出leta=[1,2,3];console.log(a.toString());//1,2,3arr->strconsole.log(a.join(''));//123arr->strconsole.log(...a);//123展开运算符...考核方式ACM模式自己构造输入格式，控制返回格式，OJ不会给任何代码，不同的语言有不同的输入输出规范。

ACMcoderOJ

readline()获取单行字符串

key：

read_line()//将读取至多1024个字符，一定注意看题目字符上限gets(n)//将读取至多n个字符，当还未达到n个时如果遇到回车或结束符printsth(sth,...)//多个参数时，空格分隔；最后不加回车。console.log(sth,...)、print(sth,...)//多个参数时，空格分隔；最后加回车line.split('').map(e=>Number(e));//str->arrarr.push([]);//arr[]->arr[][]//单行输入while(line=readline()){//字符数组varlines=line.split('');//.map(Number)可以直接将字符数组变为数字数组varlines=line.split('').map(Number);vara=parseInt(lines[0]);//效果等同下面varb=+lines[1];//+能将str转换为numprint(a+b);}//矩阵的输入while(line=readline()){letnums=line.split('');//读取第一行varrow=+nums[0];//第一行的第一个数为行数varcol=+nums[1];//第一行的第二个数为列数varmap=[];//用于存放矩阵for(leti=0;i

牛客JavaScriptNode练习

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

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

functionListNode(x){this.val=x;this.next=null;}/****@paramheadListNode类*@returnbool布尔型*/functionhasCycle(head){//writecodehereif(!head||!head.next){returnfalse}letfast=head.nextletslow=headwhile(slow!==fast){if(!fast||!fast.next){returnfalse}fast=fast.next.nextslow=slow.next}returntrue}module.exports={hasCycle:hasCycle};二叉树(反)序列化二叉树序列化二叉树，key：

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。而不是rootSerialize(pRoot.left,arr);Serialize(pRoot.right,arr);}returnarr;}//序列化二叉树：str->tree根据字符串结果str，重构二叉树functionDeserialize(s){//转换为数组letarr=Array.isArray(s)s:s.split("");//取出valleta=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===undefined0:val)*this.left=(left===undefinednull:left)*this.right=(right===undefinednull: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===undefined0:val)*this.left=(left===undefinednull:left)*this.right=(right===undefinednull:right)*}*//***@param{TreeNode}root*@return{number[]}*/varinorderTraversal=function(root){letstack=[]letres=[]letcur=rootwhile(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===undefined0:val)*this.left=(left===undefinednull:left)*this.right=(right===undefinednull:right)*}*//***@param{TreeNode}root*@return{number[]}*/varpostorderTraversal=function(root){letstack=[]letres=[]letcur=rootif(!root)returnresstack.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()};层序遍历树的层序遍历，相似图的广度优先搜索

/*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){//writecodehereif(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;//writecodeherereturn(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!=nullleft:right;}数组和树扁平结构(一维数组)转树key：

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);}排序快速排序快速排序的基本思想是通过分治来使一部分均比另一部分小（大）再使两部分重复该步骤而实现有序的排列。核心步骤有：

const_quickSort=array=>{if(array.length<=1)returnarrayvarpivotIndex=Math.floor(array.length/2)varpivot=array.splice(pivotIndex,1)[0]varleft=[]varright=[]for(vari=0;i

functionmergesort(arr){if(arr.length<2)returnarrletlen=arr.lengthletmid=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位置的数交换，如此反复执行，便能得到有序数组

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

headAdjust：

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

//每次调整,从上往下调整//调整为大根堆functionheadAdjust(arr,start,end){//将当前节点值进行保存vartmp=arr[start];//遍历孩子结点for(vari=2*start+1;i<=end;i=i*2+1){if(itmp){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，最后保留与原字符串长度相等的所有元素。

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

arrn个皇后的列位置

resn皇后排列结果

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

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

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

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

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

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

/****@paramnint整型then*@returnint整型*/functionNqueen(n){letres=[];//二维数组，存放每行Q的列坐标letisQ=newArray(n).fill(0);//记录该列是否有QletsetPos=newSet();//标记正对角线letsetCon=newSet();//标记反对角线//给当前row找一个colconstbackTrace=(row,path)=>{if(path.length===n){res.push(path);return;}for(letcol=0;col

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][j+1])+f[i][j]

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

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

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

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

这样修改对应到图中可以这样理解: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必须是逆向枚举。

constformat=(n)=>{letnum=n.toString()//拿到传进来的number数字进行toStringletlen=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)常用方法异或运算^按位异或，相同为0，不同为1

运算法则：

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

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

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

//e=2.718281828459045Math.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()直接去除小数点后面的值Number0B，0O为ES6新增

特殊值：

varresult=Number.MAX_VALUE+Number.MAX_VALUE;console.log(isFinite(result));//falsetypeofNaN//'number'---NaN不是独立的数据类型，而是一个特殊数值，它的数据类型依然属于NumberNaN===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.23e+5'));//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')//truecontacts.get('Hilary')//undefinedcontacts.delete('Jessie')//trueconsole.log(contacts.size)//1functionlogMapElements(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值的集合，且值唯一

//以下三种表达式都会创建相同的正则表达式：/ab+c/i;//字面量形式/正则表达式主体/修饰符(可选)newRegExp('ab+c','i');//首个参数为字符串模式的构造函数newRegExp(/ab+c/,'i');//首个参数为常规字面量的构造函数//防止在字符串中被解译成一个转义字符varre=newRegExp("\\w+");//需要常规的字符转义规则（在前面加反斜杠\）varre=/\w+/;当表达式被赋值时，字面量形式提供正则表达式的编译（compilation）状态，

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

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

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

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

regexp.test(str)返回Bool

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

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

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

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

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

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

letstr='#foo#'letregex=/foo/yregex.lastIndex=1regex.test(str)//trueregex.lastIndex=5regex.test(str)//false(lastIndexistakenintoaccountwithstickyflag)regex.lastIndex//0(resetaftermatchfailure)分组‘(正则表达式)’每一个分组都是一个子表达式

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

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

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

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

varstr='abcabc123';str.replace(/(ab)c/g,'$1g');//得到结果'abgabg123'匹配选择匹配：(子模式)|(子模式)多重选择模式：在多个子模式之间加入选择操作符。

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

varr=/(abc)|(efg)|(123)|(456)/;惰性匹配：最小化匹配重复类量词都具有贪婪性，在条件允许的前提下，会匹配尽可能多的字符。

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

vars="";varr=/(<.*>)(<.*>)/vara=s.match(r);console.log(a[0])//整个表达式匹配''console.log(a[1]);//左侧表达式匹配""console.log(a[2]);//右侧表达式匹配“”定义：在满足条件的前提下，尽可能少的匹配字符。

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

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

vars="

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

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

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

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

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

负后向查找：(

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

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

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

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

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

varr=/[^0123456789]/g;边界量词边界就是确定匹配模式的位置，如字符串的头部或尾部，具体说明如表所示。

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,000str.replace()使用正则改变数据结构

str.search(regexp)//如果匹配成功，则search()返回正则表达式在字符串中首次匹配项的索引;否则，返回-1constparagraph='Thequick';//Anycharacterthatisnotawordcharacterorwhitespaceconstregex=/[^\w\s]/g;console.log(paragraph.search(regex));//Expectedoutput:0合法的URLURL结构一般包括协议、主机名、主机端口、路径、请求信息、哈希

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

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

·匹配除换行字符外的任何单个字符*匹配前一个字符零或多次。例如，"zo*”与"z”或"zoo”匹配。+匹配前一个字符一次或多次。例如，"zo+"与"zoo”匹配，但和"z”不匹配。匹配前一个字符零或一次。例如，"ave”和"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_]”等效。

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

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

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

建议养成每句后加;的好习惯

命名方法：名词全部大写命名规范：使用大写字母和下划线来组合命名，下划线用来分割单词

constMAX_COUNT=10;变量，函数命名方法:小驼峰式命名法命名规范：前缀为形容词（变量），前缀为动词（函数）

letmaxCount=10;/****@paramnint整型then*@returnint整型*/functionsetConut(n){this.count=n;returnn}类类&构造函数

命名方法：大驼峰式命名法，首字母大写。

命名规范：前缀为名称。

classPerson{private_name:string;constructor(){}//公共方法getName(){returnthis._name;}//公共方法setName(name){this._name=name;}}constperson=newPerson();person.setName('mervyn');person.getName();//->mervyn*注释HTML

p{color:#ff7000;/*字体颜色设置*/height：30px;/*段落高度设置*/}