转载学习文档来源 面试之道
前端
js
- 七种内置类型：null undifined boolean number string symbol Object
- typeof 对于基本类型，除了 null(显示’object’) 都可以显示正确的类型; 想获得一个变量的正确类型，可以通过 Object.prototype.toString.call(xx)。这样我们就可以获得类似 [object Type] 的字符串
- 对象在转换基本类型时，首先会调用 valueOf 然后调用 toString。并且这两个方法你是可以重写的。当然你也可以重写 Symbol.toPrimitive ，该方法在转基本类型时调用优先级最高。
let a = { value() { return 0; }, toString() { return '1'; }, [Symbol.toPrimitive]() { return 2; } } -
每个函数都有 prototype 属性，除了 Function.prototype.bind()，该属性指向原型。
每个对象都有 proto 属性，指向了创建该对象的构造函数的原型。其实这个属性指向了 [[prototype]]，但是 [[prototype]] 是内部属性，我们并不能访问到，所以使用 proto 来访问。
对象可以通过 proto 来寻找不属于该对象的属性，proto 将对象连接起来组成了原型链。
如果你想更进一步的了解原型，可以仔细阅读 深度解析原型中的各个难点。 - new: 1)新生成一个对象 2）链接到原型 3）绑定this 4）返回新对象
function create() { // 创建一个空的对象 let obj = new Object(); // 获得构造函数 let Con = [].shift.call(arguments); // 链接到原型 obj.__proto__ = Con.prototype; // 绑定 this，执行构造函数 let result = Con.apply(obj, arguments) // 确保 new 出来的是个对象 return typeof result === 'object' ? result : obj; } - 对于 new 来说，还需要注意下运算符优先级。
function Foo() { return this; } Foo.getName = function () { console.log('1'); }; Foo.prototype.getName = function () { console.log('2'); }; // new Foo() 的优先级大于 new Foo, 所以 new (Foo.getName()); (new Foo()).getName(); new Foo.getName(); // -> 1 new Foo().getName(); // -> 2 - instanceof 可以正确的判断对象的类型，因为内部机制是通过判断对象的原型链中是不是能找到类型的 prototype。
function instanceof(left, right) { // 获得类型的原型 let prototype = right.prototype // 获得对象的原型 left = left.__proto__ // 判断对象的类型是否等于类型的原型 while (true) { if (left === null) return false if (prototype === left) return true left = left.__proto__ } } - 闭包的定义很简单：函数 A 返回了一个函数 B，并且函数 B 中使用了函数 A 的变量，函数 B 就被称为闭包。
// 经典面试题，循环中使用闭包解决 var 定义函数的问题 for ( var i=1; i<=5; i++) { setTimeout( function timer() { console.log( i ); }, i*1000 ); } // 首先因为 setTimeout 是个异步函数，所有会先把循环全部执行完毕，这时候 i 就是 6 了，所以会输出一堆 6;解决办法: 第一种使用闭包; 第二种就是使用 setTimeout 的第三个参数; 第三种就是使用 let 定义 i for (var i = 1; i <= 5; i++) { // 第一种使用闭包 (function(j) { setTimeout(function timer() { console.log(j); }, j * 1000); })(i); } for ( var i=1; i<=5; i++) { // 第二种就是使用 setTimeout 的第三个参数 setTimeout( function timer(j) { console.log( j ); }, i*1000, i); } for ( let i=1; i<=5; i++) { // 使用 let 定义 i setTimeout( function timer() { console.log( i ); }, i*1000 ); } - 深浅拷贝：
1）浅拷贝：Object.assign；
2）深拷贝：JSON.parse(JSON.stringify(object))；不过会 a）忽略 undefined b）会忽略 symbol c) 不能序列化函数 d) 不能解决循环引用的对象
3) 深拷贝：MessageChannelfunction structuralClone(obj) { return new Promise(resolve => { const {port1, port2} = new MessageChannel(); port2.onmessage = ev => resolve(ev.data); port1.postMessage(obj); }); } var obj = {a: 1, b: { c: b }} // 注意MessageChannel 方法是异步的 // 可以处理 undefined 和循环引用对象 (async () => { const clone = await structuralClone(obj) })() -
防抖和节流：防抖动和节流本质是不一样的。防抖动是将多次执行变为最后一次执行，节流是将多次执行变成每隔一段时间执行。
// 防抖1 function debounce(func, wait=50, immediate=true) { let timer, context, args; const later = () => setTimeout(() => { timer = null; if(!immediate) { func.apply(context, args); context = args = null; } }, wait); return function(...params) { if (!timer) { timer = later(); if (immediate) { func.apply(this, params); }else { context = this; args = params; } }else { clearTimeout(timer) timer = later(); } } } // 防抖2 function debounce2(func, wait) { let last = 0; return function() { let now = new Date(); if (now - last < wait) { return; } last = now; return func(this, arguments); } } // 节流 function throttle(func, wait) { let timer, context, args, result; let previous = 0; const later = () => { previous = new Date(); timer = null; result = func.apply(context, args); context = args = null; } return function() { let now = new Date(); const remain = wait - (now - previous); context = this; args = arguments; if (remain <=0 || remain > wait) { if (timer) { clearTimeout(timer); timer = null; } previous = now; result = func.apply(context, args); context = args = null; }else { timer = setTimeout(later, remain); } return result; //?? } } -
模拟实现 call 和 apply 和 bind
Function.prototype.myCall = function(context) { var context = context || window; context.fn = this; var args = [...arguments].slice(1); var result = context.fn(...args); delete context.fn; return result; } Function.prototype.myApply = function(context) { var context = context || window; context.fn = this; var result; if (arguments[1]) { result = context.fn(...argument[1]); }else { result = context.fn(); } delete context.fn; return result; } Function.prototype.myBind() = function(context) { if (typeof this !== 'function') { throw new TypeError('Error'); } var _this = this; var args = [...arguments].slice(1); return function F() { // 因为返回了一个函数，我们可以 new F()，所以需要判断 if (this instanceof F) { return new _this(...args, ...arguments); } return _this.apply(context, args.concat(...arguments)) } } -
promise实现
class MyPromise { constructor(fn) { this.fulfilledQueue = []; this.rejectedQueue = []; this._status = PENDING; this._value = null; const handleFulfilledQueue = () => { while(this.fulfilledQueue.length) { let fulfiledFn = this.fulfilledQueue.shift(); fulfiledFn(this._value); }; }; const handleRejectedQueue = () => { console.log(this.rejectedQueue); while(this.rejectedQueue.length) { let rejectedFn = this.rejectedQueue.shift(); rejectedFn(this._value); }; }; // 完成状态转变，执行回调队列中的回调函数 const _resolve = (val) => { const fn = () => { if(this._status !== PENDING) { return; } if(val instanceof MyPromise) { val.then((res) => { this._status = FULFILLED; this._value = res; handleFulfilledQueue(); }, (err) => { this._status = REJECTED; this._value = err; handleRejectedQueue(); }); } else { this._status = FULFILLED; this._value = val; handleFulfilledQueue(); } } setTimeout(fn, 0); } // 完成状态Pending到REJECTED的转变，执行rejected队列中的回调函数 const _reject = (val) => { const fn = () => { if(this._status !== PENDING) { return; } this._status = REJECTED; this._value = val; handleRejectedQueue(); } setTimeout(fn, 0); } try { // 处理外部传入函数执行异常 fn(_resolve, _reject); // resolve 和 reject是捆绑promise对象的 } catch(e) { return _reject(e); } } then(successFn, failFn) { return new MyPromise((resolve, reject) => { // 每个then都会返回一个新的primise // 执行成功时的回调函数 const handleSucess = (fn) => { try { if(typeof fn === 'function') { const res = fn(this._value); if(res instanceof MyPromise) { res.then(resolve, reject); } else { resolve(res); } } else { // this --> 从自己的作用域链的上一层继承this resolve(this._value) } } catch(e){ reject(e); } } // 执行失败时的回调函数 const handleFail = (fn) => { try { if(typeof fn === 'function') { const res = fn(this._value); if(res instanceof MyPromise) { res.then(resolve, reject); } else { resolve(res); } } else { reject(this._value); } } catch(e) { reject(e); } } switch(this._status){ case PENDING: // 异步任务尚未完成，将回调函数推入相应队列 this.fulfilledQueue.push(() => { handleSucess(successFn); }); this.rejectedQueue.push(() => { handleFail(failFn); }); break; case FULFILLED: // 异步任务成功完成，执行成功回调函数 handleSucess(successFn); break; case REJECTED: // 异步任务已失败，执行失败回调函数 handleFail(failFn); break; default: console.log('Promise error status:', this._status); break; }; }); } catch(failFn) { return this.then(null, failFn); } finally(finalFn){ return this.then(finalFn, finalFn); } static resolve(val) { if(val instanceof MyPromise) { return val; } else { return new MyPromise((resolve, reject) =>{ resolve(val); }); } } static reject(val) { return new MyPromise((resolve, reject) => { reject(val); }); } static all(promiseArr) { return new Promise((resolve, reject) =>{ const len = promiseArr.length; let count = 0; let result = []; for(let i = 0; i < len; i++) { promiseArr[i].then((val) => { count++; result.push[val]; if(count === len){ resolve(result); } }, (err) => { reject(err); }); } }); } static race(promiseArr) { return new Promise((resolve, reject) =>{ const len = promiseArr.length; for(let i = 0; i < len; i++) { promiseArr[i].then((val) => { resolve(val); }, (err) => { reject(err); }); } }); } }// es5 实现，可以比较清楚看到this的绑定问题 // 三种状态 const PENDING = "pending"; const RESOLVED = "resolved"; const REJECTED = "rejected"; // promise 接收一个函数参数，该函数会立即执行 function MyPromise(fn) { let _this = this; _this.currentState = PENDING; _this.value = undefined; // 用于保存 then 中的回调，只有当 promise // 状态为 pending 时才会缓存，并且每个实例至多缓存一个 _this.resolvedCallbacks = []; _this.rejectedCallbacks = []; _this.resolve = function (value) { if (value instanceof MyPromise) { // 如果 value 是个 Promise，递归执行 return value.then(_this.resolve, _this.reject) } setTimeout(() => { // 异步执行，保证执行顺序 if (_this.currentState === PENDING) { _this.currentState = RESOLVED; _this.value = value; _this.resolvedCallbacks.forEach(cb => cb()); } }) }; _this.reject = function (reason) { setTimeout(() => { // 异步执行，保证执行顺序 if (_this.currentState === PENDING) { _this.currentState = REJECTED; _this.value = reason; _this.rejectedCallbacks.forEach(cb => cb()); } }) } // 用于解决以下问题 // new Promise(() => throw Error('error)) try { fn(_this.resolve, _this.reject); } catch (e) { _this.reject(e); } } MyPromise.prototype.then = function (onResolved, onRejected) { var self = this; // 绑定调用的this // 规范 2.2.7，then 必须返回一个新的 promise var promise2; // 规范 2.2.onResolved 和 onRejected 都为可选参数 // 如果类型不是函数需要忽略，同时也实现了透传 // Promise.resolve(4).then().then((value) => console.log(value)) onResolved = typeof onResolved === 'function' ? onResolved : v => v; onRejected = typeof onRejected === 'function' ? onRejected : r => throw r; if (self.currentState === RESOLVED) { return (promise2 = new MyPromise(function (resolve, reject) { // 规范 2.2.4，保证 onFulfilled，onRjected 异步执行 // 所以用了 setTimeout 包裹下 setTimeout(function () { try { var x = onResolved(self.value); resolutionProcedure(promise2, x, resolve, reject); } catch (reason) { reject(reason); } }); })); } if (self.currentState === REJECTED) { return (promise2 = new MyPromise(function (resolve, reject) { setTimeout(function () { // 异步执行onRejected try { var x = onRejected(self.value); resolutionProcedure(promise2, x, resolve, reject); } catch (reason) { reject(reason); } }); })); } if (self.currentState === PENDING) { return (promise2 = new MyPromise(function (resolve, reject) { self.resolvedCallbacks.push(function () { // 考虑到可能会有报错，所以使用 try/catch 包裹 try { var x = onResolved(self.value); resolutionProcedure(promise2, x, resolve, reject); } catch (r) { reject(r); } }); self.rejectedCallbacks.push(function () { try { var x = onRejected(self.value); resolutionProcedure(promise2, x, resolve, reject); } catch (r) { reject(r); } }); })); } }; // 规范 2.3 function resolutionProcedure(promise2, x, resolve, reject) { // 规范 2.3.1，x 不能和 promise2 相同，避免循环引用 if (promise2 === x) { return reject(new TypeError("Error")); } // 规范 2.3.2 // 如果 x 为 Promise，状态为 pending 需要继续等待否则执行 if (x instanceof MyPromise) { if (x.currentState === PENDING) { x.then(function (value) { // 再次调用该函数是为了确认 x resolve 的 // 参数是什么类型，如果是基本类型就再次 resolve // 把值传给下个 then resolutionProcedure(promise2, value, resolve, reject); }, reject); } else { x.then(resolve, reject); } return; } // 规范 2.3.3.3.3 // reject 或者 resolve 其中一个执行过得话，忽略其他的 let called = false; // 规范 2.3.3，判断 x 是否为对象或者函数 if (x !== null && (typeof x === "object" || typeof x === "function")) { // 规范 2.3.3.2，如果不能取出 then，就 reject try { // 规范 2.3.3.1 let then = x.then; // 如果 then 是函数，调用 x.then if (typeof then === "function") { // 规范 2.3.3.3 then.call( x, y => { if (called) return; called = true; // 规范 2.3.3.3.1 resolutionProcedure(promise2, y, resolve, reject); }, e => { if (called) return; called = true; reject(e); } ); } else { // 规范 2.3.3.4 resolve(x); } } catch (e) { if (called) return; called = true; reject(e); } } else { // 规范 2.3.4，x 为基本类型 resolve(x); } } -
generate实现
- async 和 await
var a = 0 var b = async () => { a = a + await 10 console.log('2', a) // -> '2' 10 a = (await 10) + a console.log('3', a) // -> '3' 20 } b() a++ console.log('1', a) // -> '1' 1 /* 1 1 2 10 3 20 首先函数 b 先执行，在执行到 await 10 之前变量 a 还是 0，因为在 await 内部实现了 generators ，generators 会保留堆栈中东西，所以这时候 a = 0 被保存了下来 因为 await 是异步操作，遇到await就会立即返回一个pending状态的Promise对象，暂时返回执行代码的控制权，使得函数外的代码得以继续执行，所以会先执行 console.log('1', a) 这时候同步代码执行完毕，开始执行异步代码，将保存下来的值拿出来使用，这时候 a = 10 然后后面就是常规执行代码了 # */
浏览器
-
事件机制：
a) 事件触发有三个阶段：1）window 往事件触发处传播，遇到注册的捕获事件会触发 2）传播到事件触发处时触发注册的事件 3）从事件触发处往 window 传播，遇到注册的冒泡事件会触发
b) 如果给一个目标节点同时注册冒泡和捕获事件，事件触发会按照注册的顺序执行。
c）addEventListener 该函数的第三个参数可以是布尔值，也可以是对象，对象的话有3属性： capture，布尔值，和 useCapture 作用一样 ；once，布尔值，值为 true 表示该回调只会调用一次，调用后会移除监听；passive，布尔值，表示永远不会调用 preventDefault
d) stopPropagation 是用来阻止事件冒泡的，其实该函数也可以阻止捕获事件。stopImmediatePropagation 同样也能实现阻止事件，但是还能阻止该事件目标执行别的注册事件. - 跨域：如果协议、域名或者端口有一个不同就是跨域
a) JSONP 的原理很简单，就是利用 script 标签没有跨域限制的漏洞。通过 script 标签指向一个需要访问的地址并提供一个回调函数来接收数据当需要通讯时。
b）CORS 需要浏览器和后端同时支持。IE 8 和 9 需要通过 XDomainRequest 来实现。浏览器会自动进行 CORS 通信，实现 CORS 通信的关键是后端。只要后端实现了 CORS，就实现了跨域。服务端设置 Access-Control-Allow-Origin 就可以开启 CORS。 该属性表示哪些域名可以访问资源，如果设置通配符则表示所有网站都可以访问资源。
c) document.domain: 只能用于二级域名相同的情况下，比如 a.test.com 和 b.test.com 适用于该方式。只需要给页面添加 document.domain = ‘test.com’ 表示二级域名都相同就可以实现跨域
d）postMessage: 通常用于获取嵌入页面中的第三方页面数据。一个页面发送消息，另一个页面判断来源并接收消息var channel = new MessageChannel(); var para = document.querySelector('p'); var ifr = document.querySelector('iframe'); var otherWindow = ifr.contentWindow; ifr.addEventListener("load", iframeLoaded, false); function iframeLoaded() { otherWindow.postMessage('Hello from the main page!', '*', [channel.port2]); } channel.port1.onmessage = handleMessage; function handleMessage(e) { para.innerHTML = e.data; } -
Event loop: Node 中的 Event loop 和浏览器中的不相同(待研究)
-
Service Worker
- 渲染机制:
a) 浏览器的渲染机制一般分为以下几个步骤: 处理 HTML 并构建 DOM 树。处理 CSS 构建 CSSOM 树。将 DOM 与 CSSOM 合并成一个渲染树。根据渲染树来布局，计算每个节点的位置。调用 GPU 绘制，合成图层，显示在屏幕上。
b) 重绘（Repaint）和回流（Reflow）: 重绘是当节点需要更改外观而不会影响布局的，比如改变 color 就叫称为重绘; 回流是布局或者几何属性需要改变就称为回流。1. 使用 translate 替代 top 2. 使用 visibility 替换 display: none ，因为前者只会引起重绘，后者会引发回流（改变了布局) 3. 把 DOM 离线后修改，比如：先把 DOM 给 display:none (有一次 Reflow)，然后你修改 100 次，然后再把它显示出来 4. 不要把 DOM 结点的属性值放在一个循环里当成循环里的变量 5. 不要使用 table 布局，可能很小的一个小改动会造成整个 table 的重新布局 6. 动画实现的速度的选择，动画速度越快，回流次数越多，也可以选择使用 requestAnimationFrame 7. CSS 选择符从右往左匹配查找，避免 DOM 深度过深 8. 将频繁运行的动画变为图层，图层能够阻止该节点回流影响别的元素。比如对于 video 标签，浏览器会自动将该节点变为图层。
性能
- DNS 预解析
<link rel="dns-prefetch" href="//yuchengkai.cn" /> - 缓存：强缓存和协商缓存
a) 强缓存可以通过两种响应头实现：Expires 和 Cache-Control 。强缓存表示在缓存期间不需要请求，state code 为 200// Expires 是 HTTP / 1.0 的产物，表示资源会在 Wed, 22 Oct 2018 08:41:00 GMT 后过期，需要再次请求。并且 Expires 受限于本地时间，如果修改了本地时间，可能会造成缓存失效。 Expires: Wed, 22 Oct 2018 08:41:00 GMT // Cache-Control 出现于 HTTP / 1.1，优先级高于 Expires 。该属性表示资源会在 30 秒后过期，需要再次请求 Cache-control: max-age=30b) 如果缓存过期了，我们就可以使用协商缓存来解决问题。协商缓存需要请求，如果缓存有效会返回 304。协商缓存需要客户端和服务端共同实现，和强缓存一样，也有两种实现方式。
// Last-Modified 表示本地文件最后修改日期，If-Modified-Since 会将 Last-Modified 的值发送给服务器，询问服务器在该日期后资源是否有更新，有更新的话就会将新的资源发送回来。但是如果在本地打开缓存文件，就会造成 Last-Modified 被修改，所以在 HTTP / 1.1 出现了 ETag # Last-Modified 和 If-Modified-Since // ETag 类似于文件指纹，If-None-Match 会将当前 ETag 发送给服务器，询问该资源 ETag 是否变动，有变动的话就将新的资源发送回来。并且 ETag 优先级比 Last-Modified 高 ETag 和 If-None-Matchc) 对于某些不需要缓存的资源，可以使用 Cache-control: no-store ，表示该资源不需要缓存;
对于频繁变动的资源，可以使用 Cache-Control: no-cache 并配合 ETag 使用，表示该资源已被缓存，但是每次都会发送请求询问资源是否更新。
对于代码文件来说，通常使用 Cache-Control: max-age=31536000 并配合策略缓存使用，然后对文件进行指纹处理，一旦文件名变动就会立刻下载新的文件 -
使用 HTTP / 2.0
因为浏览器会有并发请求限制，在 HTTP / 1.1 时代，每个请求都需要建立和断开，消耗了好几个 RTT 时间（往返时间），并且由于 TCP 慢启动的原因，加载体积大的文件会需要更多的时间。
在 HTTP / 2.0 中引入了多路复用，能够让多个请求使用同一个 TCP 链接，极大的加快了网页的加载速度。并且还支持 Header 压缩，进一步的减少了请求的数据大小。 - 预加载
预加载其实是声明式的 fetch ，强制浏览器请求资源，并且不会阻塞 onload 事件，可以使用以下代码开启预加载<link rel="preload" href="http://example.com" /> -
懒执行 和 懒加载
-
图片加载优化 和 其他文件优化
-
CDN
静态资源尽量使用 CDN 加载，由于浏览器对于单个域名有并发请求上限，可以考虑使用多个 CDN 域名。对于 CDN 加载静态资源需要注意 CDN 域名要与主站不同，否则每次请求都会带上主站的 Cookie -
使用 Webpack 优化项目：
a) 对于 Webpack4，打包项目使用 production 模式，这样会自动开启代码压缩
b) 使用 ES6 模块来开启 tree shaking，这个技术可以移除没有使用的代码
c) 优化图片，对于小图可以使用 base64 的方式写入文件中
d) 按照路由拆分代码，实现按需加载
e) 给打包出来的文件名添加哈希，实现浏览器缓存文件 - 监控
a) 使用 window.onerror 拦截报错
b) 对于异步代码来说，可以使用 catch 的方式捕获错误。比如 Promise 可以直接使用 catch 函数，async await 可以使用 try catch
安全
-
xss 与 csrf：
a) XSS 通过修改 HTML 节点或者执行 JS 代码来攻击网站。
b) CSRF， 是一种挟制用户在当前已登录的 Web 应用程序上执行非本意的操作的攻击方法。简单点说，CSRF 就是利用用户的登录态发起恶意请求
c) XSS 利用的是用户对指定网站的信任，CSRF 利用的是网站对用户网页浏览器的信任。 -
CSP：内容安全策略 (CSP) 是一个额外的安全层，用于检测并削弱某些特定类型的攻击，包括跨站脚本 (XSS) 和数据注入攻击等
通过 HTTP Header 中的 Content-Security-Policy 来开启 CSP -
密码安全
框架通识
-
MVVM:
Model-View-ViewModel的简写。即模型-视图-视图模型。【模型】指的是后端传递的数据。【视图】指的是所看到的页面。【视图模型】mvvm模式的核心，它是连接view和model的桥梁。它有两个方向：一是将【模型】转化成【视图】，即将后端传递的数据转化成所看到的页面。实现的方式是：数据绑定。二是将【视图】转化成【模型】，即将所看到的页面转化成后端的数据。实现的方式是：DOM 事件监听。这两个方向都实现的，我们称之为数据的双向绑定。 - Proxy 与 Object.defineProperty 对比
问题： 只能对属性进行数据劫持，所以需要深度遍历整个对象， 对于数组不能监听到数据的变化
反观 Proxy 就没以上的问题，原生支持监听数组变化，并且可以直接对整个对象进行拦截，所以 Vue 也将在下个大版本中使用 Proxy 替换 Object.definePropertylet onWatch = (obj, setBind, getLogger) => { let handler = { get(target, property, receiver) { getLogger(target, property) return Reflect.get(target, property, receiver) }, set(target, property, value, receiver) { setBind(value) return Reflect.set(target, property, value) } } return new Proxy(obj, handler) } let obj = { a: 1 } let value let p = onWatch( obj, v => { value = v }, (target, property) => { console.log(`Get '${property}' = ${target[property]}`) } ) p.a = 2 // bind `value` to `2` p.a // -> Get 'a' = 2 -
路由原理: hash 模式 和 history 模式
a) hash: location.hash 与 hashchange 事件
b) history.pushState() 与 history.replaceState() –参数为state对象、可选的标题、可选的url； window.onpopstate事件(event对象存在state对象，为pushState传入的) - Virtual Dom
计算机通识
网络
-
UDP
a) UDP 是一个面向报文（报文可以理解为一段段的数据）的协议。意思就是 UDP 只是报文的搬运工，不会对报文进行任何拆分和拼接操作b) 不可靠性:
1) UDP 是无连接的，也就是说通信不需要建立和断开连接。 2) UDP 也是不可靠的。协议收到什么数据就传递什么数据，并且也不会备份数据，对方能不能收到是不关心的。 3）UDP 没有拥塞控制，一直会以恒定的速度发送数据。即使网络条件不好，也不会对发送速率进行调整。这样实现的弊端就是在网络条件不好的情况下可能会导致丢包，但是优点也很明显，在某些实时性要求高的场景（比如电话会议）就需要使用 UDP 而不是 TCPc) 高效: 因为 UDP 没有 TCP 那么复杂，需要保证数据不丢失且有序到达。所以 UDP 的头部开销小，只有八字节(源端口（可选字段）和目标端口,整个数据报文的长度,整个数据报文的检验和)，相比 TCP 的至少二十字节要少得多，在传输数据报文时是很高效的
d) 传输方式: UDP 不止支持一对一的传输方式，同样支持一对多，多对多，多对一的方式，也就是说 UDP 提供了单播，多播，广播的功能 -
TCP
a) TCP 头部:1) Sequence number，这个序号保证了 TCP 传输的报文都是有序的，对端可以通过序号顺序的拼接报文; 2) Acknowledgement Number，这个序号表示数据接收端期望接收的下一个字节的编号是多少，同时也表示上一个序号的数据已经收到 3) Window Size，窗口大小，表示还能接收多少字节的数据，用于流量控制 4) 标识符: URG=1：该字段为一表示本数据报的数据部分包含紧急信息，是一个高优先级数据报文，此时紧急指针有效。紧急数据一定位于当前数据包数据部分的最前面，紧急指针标明了紧急数据的尾部。 5) 标识符: ACK=1：该字段为一表示确认号字段有效。此外，TCP 还规定在连接建立后传送的所有报文段都必须把 ACK 置为一。 6) 标识符: PSH=1：该字段为一表示接收端应该立即将数据 push 给应用层，而不是等到缓冲区满后再提交。 7) 标识符: RST=1：该字段为一表示当前 TCP 连接出现严重问题，可能需要重新建立 TCP 连接，也可以用于拒绝非法的报文段和拒绝连接请求。 8) 标识符: SYN=1：当SYN=1，ACK=0时，表示当前报文段是一个连接请求报文。当SYN=1，ACK=1时，表示当前报文段是一个同意建立连接的应答报文。 9) 标识符: FIN=1：该字段为一表示此报文段是一个释放连接的请求报文b) 性能指标 RTT: 该指标表示发送端发送数据到接收到对端数据所需的往返时间
c) 建立连接三次握手:1) SYN --> 客户端向服务端发送连接请求报文段。该报文段中包含自身的数据通讯初始序号。请求发送后，客户端便进入 SYN-SENT 状态，x 表示客户端的数据通信初始序号。 2) SYN + ACK --> 服务端收到连接请求报文段后，如果同意连接，则会发送一个应答，该应答中也会包含自身的数据通讯初始序号，发送完成后便进入 SYN-RECEIVED 状态。 3) ACK --> 当客户端收到连接同意的应答后，还要向服务端发送一个确认报文。客户端发完这个报文段后便进入ESTABLISHED 状态，服务端收到这个应答后也进入 ESTABLISHED 状态，此时连接建立成功 >PS：第三次握手可以包含数据，通过 TCP 快速打开（TFO）技术。其实只要涉及到握手的协议，都可以使用类似 TFO 的方式，客户端和服务端存储相同 cookie，下次握手时发出 cookie 达到减少 RTT 的目的d) 断开链接四次握手:
1) 若客户端 A 认为数据发送完成，则它需要向服务端 B 发送连接释放请求 2) B 收到连接释放请求后，会告诉应用层要释放 TCP 链接。然后会发送 ACK 包，并进入 CLOSE_WAIT 状态，表示 A 到 B 的连接已经释放，不接收 A 发的数据了。但是因为 TCP 连接时双向的，所以 B 仍旧可以发送数据给 A。 3) B 如果此时还有没发完的数据会继续发送，完毕后会向 A 发送连接释放请求，然后 B 便进入 LAST-ACK 状态。 4) A 收到释放请求后，向 B 发送确认应答，此时 A 进入 TIME-WAIT 状态。该状态会持续 2MSL（最大段生存期，指报文段在网络中生存的时间，超时会被抛弃） 时间，若该时间段内没有 B 的重发请求的话，就进入 CLOSED 状态。当 B 收到确认应答后，也便进入 CLOSED 状态。e) 滑动窗口
f) 拥塞处理 -
HTTP
a) 常见状态码1) 200 OK，表示从客户端发来的请求在服务器端被正确处理 2) 204 No content，表示请求成功，但响应报文不含实体的主体部分 3) 205 Reset Content，表示请求成功，但响应报文不含实体的主体部分，但是与 204 响应不同在于要求请求方重置内容 4) 206 Partial Content，进行范围请求 5) 301 moved permanently，永久性重定向，表示资源已被分配了新的 URL 6) 302 found，临时性重定向，表示资源临时被分配了新的 URL 7）303 see other，表示资源存在着另一个 URL，应使用 GET 方法获取资源 8）304 not modified，表示服务器允许访问资源，但因发生请求未满足条件的情况 9）307 temporary redirect，临时重定向，和302含义类似，但是期望客户端保持请求方法不变向新的地址发出请求 10）400 bad request，请求报文存在语法错误 11）401 unauthorized，表示发送的请求需要有通过 HTTP 认证的认证信息 12）403 forbidden，表示对请求资源的访问被服务器拒绝 13）404 not found，表示在服务器上没有找到请求的资源 14）500 internal sever error，表示服务器端在执行请求时发生了错误 15）501 Not Implemented，表示服务器不支持当前请求所需要的某个功能 16）503 service unavailable，表明服务器暂时处于超负载或正在停机维护，无法处理请求b) HTTP 首部: https://yuchengkai.cn/docs/cs/#http-%E9%A6%96%E9%83%A8
-
HTTPS:
a) HTTPS 还是通过了 HTTP 来传输信息，但是信息通过 TLS 协议进行了加密
b) TLS 握手过程:1) 客户端发送一个随机值，需要的协议和加密方式 2) 服务端收到客户端的随机值，自己也产生一个随机值，并根据客户端需求的协议和加密方式来使用对应的方式，发送自己的证书（如果需要验证客户端证书需要说明） 3) 客户端收到服务端的证书并验证是否有效，验证通过会再生成一个随机值，通过服务端证书的公钥去加密这个随机值并发送给服务端，如果服务端需要验证客户端证书的话会附带证书 4) 服务端收到加密过的随机值并使用私钥解密获得第三个随机值，这时候两端都拥有了三个随机值，可以通过这三个随机值按照之前约定的加密方式生成密钥，接下来的通信就可以通过该密钥来加密解密 -
HTTP 2.0
a) 二进制传输: HTTP 2.0 中所有加强性能的核心点在于此。在之前的 HTTP 版本中，我们是通过文本的方式传输数据。在 HTTP 2.0 中引入了新的编码机制，所有传输的数据都会被分割，并采用二进制格式编码
b) 多路复用: 在 HTTP 2.0 中，有两个非常重要的概念，分别是帧（frame）和流（stream）。帧代表着最小的数据单位，每个帧会标识出该帧属于哪个流，流也就是多个帧组成的数据流。多路复用，就是在一个 TCP 连接中可以存在多条流。换句话说，也就是可以发送多个请求，对端可以通过帧中的标识知道属于哪个请求。通过这个技术，可以避免 HTTP 旧版本中的队头阻塞问题，极大的提高传输性能。
c) Header 压缩: 使用了 HPACK 压缩格式对传输的 header 进行编码，减少了 header 的大小。并在两端维护了索引表，用于记录出现过的 header ，后面在传输过程中就可以传输已经记录过的 header 的键名，对端收到数据后就可以通过键名找到对应的值
d) 服务端 Push: 在 HTTP 2.0 中，服务端可以在客户端某个请求后，主动推送其他资源 - QUIC
- DNS
数据结构
-
栈
栈是一个线性结构，特点是只能在某一端添加或删除数据，遵循先进后出的原则 - 队列
队列一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。class Queue { constructor() { this.queue = []; } enQueue(item) { this.queue.push(item); } deQueue(item) { this.queue.shift(); } getLength() { return this.queue.length } isEmpty() { return this.getLength() === 0 } } - 链表
1）链表是一个线性结构，同时也是一个天然的递归结构。链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
2）单向链表class Node { constructor(v, next) { this.value = v; this.next = next; } } class LinkList { constructor() { // 链表长度 this.size = 0; // 虚拟头部 this.dummyHead = new Node(null, null); } find(index) { let size = this.getSize(); if (index > size || !/^\d$/.test(index)) { return null; } let resNode = this.dummyHead; while(index--) { resNode = this.resNode.next; } return resNode; } addNode(v, index) { let preNode = find(index-1); preNode.next = new Node(v, preNode.next); this.size++; return preNode.next; }, removeNode(index) { let prev = find(index-1); let node = prev.next; prev.next = node.next; node.next = null; this.size--; return node; } getSize() { return this.size; } } -
树
1）二叉树：树拥有很多种结构，二叉树是树中最常用的结构，同时也是一个天然的递归结构。
二叉树拥有一个根节点，每个节点至多拥有两个子节点，分别为：左节点和右节点。树的最底部节点称之为叶节点，当一颗树的叶数量数量为满时，该树可以称之为满二叉树。
2）二分搜索树也是二叉树，拥有二叉树的特性。但是区别在于二分搜索树每个节点的值都比他的左子树的值大，比右子树的值小。这种存储方式很适合于数据搜索。class Node { constructor(value) { this.value = value; this.left = null; this.rught = null; // 表示该节点下有多少子节点（包含自身） this.size = 1 } } class BST { constructor() { this.root = null; this.size = 0; } getSize() { return this.size } isEmpty() { return this.size === 0 } addNode(v) { this.root = this._addChild(this.root, v); } _addChild(node, v) { if (!node) { this.size++; return new Node(v); } if (node.value > v) { node.size++; // 每加入一个节点，树的所有节点的size都+1 node.left = this._addChild(node.left, v); }else if (node.value < v) { node.size++; node.right = this._addChild(node.right, v); } return node; } // 先序遍历可用于打印树的结构 // 先序遍历先访问根节点，然后访问左节点，最后访问右节点。 preTraversal() { this._prev(this.root); } _prev(node) { if (node) { console.log(node.value); this._prev(node.left); this._prev(node.right); } } // 中序遍历可用于排序 // 对于 BST 来说，中序遍历可以实现一次遍历就 // 得到有序的值 // 中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。 midTraversal() { this._mid(this.root) } _mid(node) { if (node) { this._mid(node.left) console.log(node.value) this._mid(node.right) } } // 后序遍历可用于先操作子节点 // 再操作父节点的场景 // 后序遍历表示先访问左节点，然后访问右节点，最后访问根节点。 backTraversal() { this._back(this.root) } _back(node) { if (node) { this._back(node.left) this._back(node.right) console.log(node.value) } } // 广度遍历,利用队列结构的先进先出 breadthTraversal() { if (!this.root) return null; let q = new Queue(); q.enQueue(this.root); while(!q.isEmpty()){ let n = q.deQueue(); console.log(n.value); if (n.left) { q.enQueue(n.left) } if (n.right) { q.enQueue(n.right) } } } // 寻找最小值 getMin(root) { let _root = root || this.root; if (_root) return null; let node = this.root; while(node.left) { node = node.left; } return node.value; } // 向下取整 floor(v) { let node = this._floor(this.root, v); return node ? node.value : null; } // 既然是向下取整，那么根据二分搜索树的特性，值一定在根节点的左侧。只需要一直遍历左子树直到当前节点的值不再大于等于需要的值，然后判断节点是否还拥有右子树。如果有的话，继续上面的递归判断 _floor(node, v) { if (!node) return null; if (node.value === v) { return node } // 如果当前节点值还比需要的值大，就继续递归 if (node.value > v) { return this._floor(node.left, v); } // 判断当前节点是否拥有右子树 let right = this._floor(node.right, v); if (right) return right; return node; } // 表示该节点下有多少子节点（包含自身） _getSize(node) { return node ? node.size : 0 } // 排名，获取给定值的排名或者排名第几的节点的值 select(k) { let node = this._select(this.root, k); return node ? node.value : null; } _select(node, k) { if (!node) return null; // 先获取左子树下有几个节点 let size = node.left ? node.left.size : 0; // 判断 size 是否大于 k // 如果大于 k，代表所需要的节点在左节点 if (size > k) return this._select(node.left, k); // 如果小于 k，代表所需要的节点在右节点 // 注意这里需要重新计算 k，减去根节点除了右子树的节点数量 if (size < k) return this._select(node.right, size-k-1); return node; } // 删除节点: 存在以下几种情况: // 需要删除的节点没有子树 // 需要删除的节点只有一条子树 // 需要删除的节点有左右两条树 // 删除最小节点 delectMin() { this.root = this._deleteMin(this.root); console.log(this.root); } _deleteMin(node) { // 一直递归左子树 // 如果左子树为空，就判断节点是否拥有右子树 // 有右子树的话就把需要删除的节点替换为右子树 if (node != null & !node.left) return node.right; node.left = this._deleteMin(node.left); // 最后需要重新维护下节点的 `size` node.size = this._getSize(node.left) + this._getSize(node.right) + 1; return node; } // 如何删除任意节点了。对于这个操作，T.Hibbard 在 1962 年提出了解决这个难题的办法，也就是如何解决第三种情况。 // 当遇到这种情况时，需要取出当前节点的后继节点（也就是当前节点右子树的最小节点）来替换需要删除的节点。然后将需要删除节点的左子树赋值给后继结点，右子树删除后继结点后赋值给他。 // 你如果对于这个解决办法有疑问的话，可以这样考虑。因为二分搜索树的特性，父节点一定比所有左子节点大，比所有右子节点小。那么当需要删除父节点时，势必需要拿出一个比父节点大的节点来替换父节点。这个节点肯定不存在于左子树，必然存在于右子树。然后又需要保持父节点都是比右子节点小的，那么就可以取出右子树中最小的那个节点来替换父节点。 delete(v) { this.root = this._delect(this.root, v) } _delete(node, v) { if (!node) return null; if (node.value > v) { // 寻找的节点比当前节点小，去左子树找 node.left = this._delete(node.left, v); }else if (node.value < v) { // 寻找的节点比当前节点大，去右子树找 node.right = this._delete(node.right, v); }else { // 进入这个条件说明已经找到节点 // 先判断节点是否只拥有左右子树中的一个 // 是的话，将子树返回出去，这里和 `_delectMin` 的操作一样 if (!node.left) return node.right; if (!node.right) return node.left; // 进入这里，代表节点拥有左右子树 // 先取出当前节点的后继结点，也就是取当前节点右子树的最小值 let min = this.getMin(node.right); // 取出最小值后，删除最小值 // 然后把删除节点后的子树赋值给最小值节点 min.right = this._deleteMin(node.right); // 左子树不动 min.left = node.left; node = min; } // 维护 size node.size = this._getSize(node.left) + this._getSize(node.right) + 1 return node } } - AVL 树
1）二分搜索树实际在业务中是受到限制的，因为并不是严格的 O(logN)，在极端情况下会退化成链表，比如加入一组升序的数字就会造成这种情况。
AVL 树改进了二分搜索树，在 AVL 树中任意节点的左右子树的高度差都不大于 1，这样保证了时间复杂度是严格的 O(logN)。基于此，对 AVL 树增加或删除节点时可能需要旋转树来达到高度的平衡。
2) 实现class Node { constructor(v) { this.value = v; this.left = left; this.right = right; this.height = 1; } } class AVL { constructor() { this.root = null; } _getHeight(node) { if (!node) return 0 return node.height } _getBalanceFactor(node) { return this._getHeight(node.left) - this._getHeight(node.right) } addNode(v) { this.root = this._addChild(this.root, v); } _addChild(node, v) { if (!node) { return new Node(v); } if (node.value > v) { node.left = this._addChild(node.left, v); }else if (node.value < v) { node.right = this._addChild(node.right, v); }else { node.value = v; } node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.left)); let factor = this._getBalanceFactor(node); if (factor > 1 && this._getBalanceFactor(node.left)>=0) { return this._rightRotate(node); } if (factor < -1 && this._getBalanceFactor(node.right)<=0) { return this._leftRotate(node); } if (factor > 1 && this._getBalanceFactor(node.left)<0) { node.left = this._leftRotate(node.left) return this._rightRotate(node) } // 右左情况 // 节点的左树比右树矮，且节点的右树的右树比节点的右树的左树矮 if (factor < -1 && this._getBalanceFactor(node.right) > 0) { node.right = this._rightRotate(node.right) return this._leftRotate(node) } return node; } // 节点右旋 // 5 2 // / \ / \ // 2 6 ==> 1 5 // / \ / / \ // 1 3 new 3 6 // / // new _rightRotate(node) { // 旋转后新根节点 let newRoot = node.left // 需要移动的节点 let moveNode = newRoot.right // 节点 2 的右节点改为节点 5 newRoot.right = node // 节点 5 左节点改为节点 3 node.left = moveNode // 更新树的高度 node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right)) newRoot.height = 1 + Math.max(this._getHeight(newRoot.left), this._getHeight(newRoot.right)) return newRoot } // 节点左旋 // 4 6 // / \ / \ // 2 6 ==> 4 7 // / \ / \ \ // 5 7 2 5 new // \ // new _leftRotate(node) { // 旋转后新根节点 let newRoot = node.right // 需要移动的节点 let moveNode = newRoot.left // 节点 6 的左节点改为节点 4 newRoot.left = node // 节点 4 右节点改为节点 5 node.right = moveNode // 更新树的高度 node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right)) newRoot.height = 1 + Math.max(this._getHeight(newRoot.left), this._getHeight(newRoot.right)) return newRoot } } - Trie
1）trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。该树有以下几个特点：
根节点代表空字符串，每个节点都有 N（假如搜索英文字符，就有 26 条） 条链接，每条链接代表一个字符；
节点不存储字符，只有路径才存储，这点和其他的树结构不同
从根节点开始到任意一个节点，将沿途经过的字符连接起来就是该节点对应的字符串class TrieNode { constructor() { this.path = 0; this.end = 0; this.next = new Array(26).fill(null); } } class Trie { constructor() { this.root = new TrieNode(); } insert(str) { if (!str) return; let node = this.root; for(let i=0; i<str.length; i++) { // 获得字符先对应的索引 let index = str[i].charCodeAt() - 'a'.charCodeAt(); // 如果索引对应没有值，就创建 if (!node.next[index]) { node.next[index] = new TrieNode(); } node.path += 1; node = node.next[index]; } node.end += 1; } // 搜索字符串出现的次数 search(str) { if (!str) return let node = this.root; for(let i=0; i<str.length; i++){ let index = str[i].charCodeAt() - 'a'.charCodeAt() // 如果索引对应没有值，代表没有需要搜素的字符串 if (!node.next[index]) { return 0 } node = node.next[index]; } return node.end; } // 删除字符串 delete() { if (!str) return let node = this.root; for(let i=0; i<str.length; i++){ let index = str[i].charCodeAt() - 'a'.charCodeAt() // 如果索引对应没有值，代表没有需要搜素的字符串 if (--node.next[index].path == 0) { node.next[index] = null; return; } node = node.next[index]; } node.end -= 1; } } - 并查集:
1) 学习指导 转 并查集 - 堆
1) 堆通常是一个可以被看做一棵树的数组对象。堆的实现通过构造二叉堆，实为二叉树的一种。这种数据结构具有以下性质。任意节点小于（或大于）它的所有子节点; 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层从左到右填入。
2）堆的每个节点的左边子节点索引是 i * 2 + 1，右边是 i * 2 + 2，父节点是 (i - 1) /2。
堆有两个核心的操作，分别是 shiftUp 和 shiftDown 。前者用于添加元素，后者用于删除根节点。shiftUp 的核心思路是一路将节点与父节点对比大小，如果比父节点大，就和父节点交换位置。shiftDown 的核心思路是先将根节点和末尾交换位置，然后移除末尾元素。接下来循环判断父节点和两个子节点的大小，如果子节点大，就把最大的子节点和父节点交换。class MaxHeap { constructor() { this.heap = []; } size() { return this.heap.length } empty() { return this.size() == 0 } _swap(left, right) { let rightValue = this.heap[right] this.heap[right] = this.heap[left] this.heap[left] = rightValue } getParentIndex(k) { return parseInt((k - 1)/2); } getLeftIndex(k) { return k * 2 + 1 } add(item) { this.heap.push(item); this._shiftUp(this.heap.size() -1); } removeMax() { this._shiftDown(0) } _shiftUp(k) { // 如果当前节点比父节点大，就交换 while(this.heap[k] > this.heap[this.getParentIndex(k)]) { this._swap(k, this.getParentIndex(k)); // 将索引变成父节点 k = this.getParentIndex(k); } } _shiftDown(k) { // 交换首位并删除末尾 this._swap(0, k); this.heap.splice(this.heap.size()-1, 1); // 判断节点是否有左孩子，因为二叉堆的特性，有右必有左 while(this.getLeftIndex(k) < this.size()) { let j = this.getLeftIndex(k); // 判断是否有右孩子，并且右孩子是否大于左孩子 if (j+1 < this.size() && this.heap[j] < this.heap[j+1]) { j++; } // 判断父节点是否已经比子节点都大 if (this.heap[k] > this.heap[j] ) { break; } // 否则继续查找 this._swap(k, j); k = j; } } }
算法
-
时间复杂度
1) 通常使用最差的时间复杂度来衡量一个算法的好坏。
2) 对于一个算法来说，可能会计算出如下操作次数 aN + 1，N 代表数据量。那么该算法的时间复杂度就是 O(N) - 位运算
1) 进制转换:// 二进制（或者其他进制） 转 十进制 parseInt(10001,2) //17 parseInt(77, 8) // 63 // 十进制 转 二进制（或者其他进制） Number(17).toString(2) //"10001" Number(63).toString(8) // "77"2) 左移
<<
左移就是将二进制全部往左移动，10 在二进制中表示为 1010 ，左移一位后变成 10100 ，转换为十进制也就是 20，所以基本可以把左移看成以下公式 a * (2 ^ b)
3) 算数右移>>
算数右移就是将二进制全部往右移动并去除多余的右边，10 在二进制中表示为 1010 ，右移一位后变成 101 ，转换为十进制也就是 5，所以基本可以把右移看成以下公式 int v = a / (2 ^ b)
4) 按位与 按位或 按位异或 -
排序
可以参考文章动图转 JS家的排序算法1) 通用函数
function checkArray(array) { if (!array || array.length <= 2) return } function swap(array, left, right) { let rightValue = array[right] array[right] = array[left] array[left] = rightValue }2）冒泡排序：思路：遍历数组，每次遍历就将最大（或最小）值推至最前，越往后遍历查询次数越少。时间复杂度是 O(n * n)
function bubble(array) { checkArray(array); for(let i= array.length -1; i>0; i--) { for(j=0; j<i; j++) { if (array[j] > array[j+1]) { swap(array, j, j+1); } } } return array; }3) 插入排序: 第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。
function insertion(array) { checkArray(array); for (let i=1; i<array.length; i++) { for(let j=i-1; j>=0 && array[j]>array[j+1]; j--) { swap(array, j, j+1); } } return array; }4) 选择排序: 遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作
function selection(array) { checkArray(array); for(let i=0; i< array.length-1; i++) { let minIndex = i; for(let j=i+1; j<array.length; j++) { minIndex = array[j] < array[minIndex] ? j : minIndex; } swap(array, minIndex, i); } return array; }5) 归并排序: 递归的将数组两两分开直到最多包含两个元素，然后将数组排序合并，最终合并为排序好的数组
function sort(array) { checkArray(array); mergeSort(array, 0, array.length - 1) return array } function mergeSort(array, left, right) { if (left === right) return; let mid = parseInt(left + ((right - left) >> 1)); mergeSort(array, left, mid); mergeSort(array, mid + 1, right); let help = []; let i = 0; let p1 = left; let p2 = mid+1; while(p1<=mid && p2<=right) { help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++]; } while(p1 <= mid) { help[i++] = array[p1++]; } while(p2 <= right){ help[i++] = array[p2++]; } for (let i = 0; i < help.length; i++) { array[left + i] = help[i] } return array }// 非递归实现，自底向上方式 function mergeSort(arr) { if (arr.length < 2) { return; } var step = 1; var left, right; while (step < arr.length) { left = 0; right = step; while (right + step <= arr.length) { mergeArrays(arr, left, left+step, right, right+step); left = right + step; right = left + step; } if (right < arr.length) { mergeArrays(arr, left, left+step, right, arr.length); } step *= 2; } } function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) { var rightArr = new Array(stopRight - startRight + 1); var leftArr = new Array(stopLeft - startLeft + 1); k = startRight; for (var i = 0; i < (rightArr.length-1); ++i) { rightArr[i] = arr[k]; ++k; } k = startLeft; for (var i = 0; i < (leftArr.length-1); ++i) { leftArr[i] = arr[k]; ++k; } rightArr[rightArr.length-1] = Infinity; // 哨兵值 leftArr[leftArr.length-1] = Infinity; // 哨兵值 var m = 0; var n = 0; for (var k = startLeft; k < stopRight; ++k) { if (leftArr[m] <= rightArr[n]) { arr[k] = leftArr[m]; m++; }else { arr[k] = rightArr[n]; n++; } } print("left array - ", leftArr); print("right array - ", rightArr); }6）快排：在数据集之中，选择一个元素作为”基准”（pivot），所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
function quickSort(array){ if (array.length == 0) { return []; } let left = []; let right = []; let privot = array[0]; for(let i=1; i<array.length; i++) { if (array[i] < privot) { left.push(array[i]); }else if (array[i] > privot) { right.push(array[i]); } } return quickSort(left).concat(privot, quickSort(right)); }// 另外一种实现 function sort(array) { checkArray(array); quickSort(array, 0, array.length - 1); return array; } function quickSort(array, left, right) { if (left < right) { swap(array, , right) // 随机取值，然后和末尾交换，这样做比固定取一个位置的复杂度略低 let indexs = part(array, parseInt(Math.random() * (right - left + 1)) + left, right); quickSort(array, left, indexs[0]); quickSort(array, indexs[1] + 1, right); } } function part(array, left, right) { let less = left - 1; let more = right; while (left < more) { if (array[left] < array[right]) { // 当前值比基准值小，`less` 和 `left` 都加一 ++less; ++left; } else if (array[left] > array[right]) { // 当前值比基准值大，将当前值和右边的值交换 // 并且不改变 `left`，因为当前换过来的值还没有判断过大小 swap(array, --more, left); } else { // 和基准值相同，只移动下标 left++; } } // 将基准值和比基准值大的第一个值交换位置 // 这样数组就变成 `[比基准值小, 基准值, 比基准值大]` swap(array, right, more); return [less, more]; }7）堆排序: 堆排序利用了二叉堆的特性来做，二叉堆通常用数组表示，并且二叉堆是一颗完全二叉树（所有叶节点（最底层的节点）都是从左往右顺序排序，并且其他层的节点都是满的）。二叉堆又分为大根堆与小根堆。排序原理即 每次将堆顶元素与数组最后面的且没有被置换的元素互换，然后将互换后的堆重排成大根堆或小根堆
function heapSort() { checkArray(array); // 构造大根堆 for(let i=0; i<array.length; i++) { heapInsert(array, i); } let size = array.length // 交换首位和末尾 swap(array, 0, --size); while(size > 0) { heapify(array, 0, size); swap(array, 0, --size); } } function heapInsert(array, index) { while(array[index] > array[parseInt((index - 1) / 2)]) { swap(array, index, parseInt((index - 1) / 2)); index = parseInt((index - 1) / 2); } } function heapify(array, index, size) { let left = index*2 +1; while(left<size) { // 判断左右节点大小 let largest = left + 1 < size && array[left] < array[left + 1] ? left + 1 : left // 判断子节点和父节点大小 largest = array[index] < array[largest] ? largest : index if (largest === index) break swap(array, index, largest) index = largest left = index * 2 + 1 } }8) 计数排序: 核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数
- 链表
1）反转单向链表function revertList(head) { if (!head || !head.next) return head; let pre = null; let current = head; let next; while(current){ next = current.next; current.next = pre; pre = current; current = next; } return pre; } - 树
1）二叉树的先序，中序，后序遍历// 递归 function traversal(root) { if (root){ // 先序 console.log(root) traversal(root.left) // 中序 // console.log(root); traversal(root.right) // 后序 // console.log(root); } } // 非递归--先序 function pre(root) { if (root) { let stack = [] // 先将根节点 push stack.push(root) while(stack.length) { root = stack.pop(); console.log(root); if (root.right) { stack.push(root.right); } if (root.left) { stack.push(root.left); } } } } // 非递归--中序 function mid(root) { if (root) { let stack = [] while(stack.length || root) { if (root) { stack.push(root); root = root.left; }else { root = stack.pop() console.log(root) root = root.right; } } } } // 非递归--后序 function pos(root) { if (root) { let stack1 = []; let stack2 = []; stack1.push(root); while(stack.length) { root = stack1.pop(); stack2.push(root); if (root.left) { stack1.push(root.left) } if (root.right) { stack1.push(root.right) } } while (stack2.length > 0) { console.log(s2.pop()) } } } - 动态规划: 动态规划背后的基本思想非常简单。就是将一个问题拆分为子问题，一般来说这些子问题都是非常相似的，那么我们可以通过只解决一次每个子问题来达到减少计算量的目的。
动态规划的本质其实就是两点: 自底向上分解子问题; 通过变量存储已经计算过的解
1) 斐波那契数列function fib(n) { let array = new Array(n + 1).fill(null) array[0] = 0 array[1] = 1 for(let i=2; i<=n; i++) { array[i] = array[i - 1] + array[i - 2]； } return array[n]; }2) 0 - 1 背包问题: 给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。每个物品只能放入至多一次
```js /**- @param {*} w 物品重量
- @param {*} v 物品价值
- @param {*} C 总容量
-
@returns */ function knapsack(w, v, C) { let length = w.length; if (length === 0) return 0
let array = new Array(length).fill(new Array(c+1).fill(null)); // 完成底部子问题的解 for (let i = 0; i <= C; i++) { // 对照表格第一行， array[0] 代表物品 1 // i 代表剩余总容量 // 当剩余总容量大于物品 1 的重量时，记录下背包物品总价值，否则价值为 0 array[0][i] = i >= w[0] ? v[0] : 0 } // 自底向上开始解决子问题，从物品 2 开始 for (let i = 1; i < length; i++) { for (let j = 0; j <= C; j++) { // 这里求解子问题，分别为不放当前物品和放当前物品 // 先求不放当前物品的背包总价值，这里的值也就是对应表格中上一行对应的值 array[i][j] = array[i - 1][j] // 判断当前剩余容量是否可以放入当前物品 if (j >= w[i]) { // 可以放入的话，就比大小 // 放入当前物品和不放入当前物品，哪个背包总价值大 array[i][j] = Math.max(array[i][j], v[i] + array[i - 1][j - w[i]]) } } } return array[length - 1][C] }
3) 最长递增子序列 ```js function lis(n) { if (n.length === 0) return 0 // 创建一个和参数相同大小的数组，并填充值为 1 let array = new Array(n.length).fill(1) // 从索引 1 开始遍历，因为数组已经所有都填充为 1 了 for (let i = 1; i < n.length; i++) { // 从索引 0 遍历到 i // 判断索引 i 上的值是否大于之前的值 for (let j = 0; j < i; j++) { if (n[i] > n[j]) { array[i] = Math.max(array[i], 1 + array[j]) } } } let res = 1 for (let i = 0; i < array.length; i++) { res = Math.max(res, array[i]) } return res }