持续创作,加速成长!这是我参加「日新计划 10 月更文挑战」的第6天,点击检查活动概况
前言
又到了金九银十季,最近我也是奔波于各种面试。我自己总结整理了许多方向的前端面试题。借着国庆这个假期,也把这些标题总结分享给咱们,也祝正在面试的朋友们能够拿到满意的offer。
往期文章
(1) 2022年我的面试万字总结(浏览器网络篇)
(2) 2022年我的面试万字总结(CSS篇)
(3) 2022年我的面试万字总结(HTML篇)
(4) 2022年我的面试万字总结(JS篇上)
(5) 2022年我的面试万字总结(JS篇下)
(7) 2022年我的面试万字总结(Vue上)
(8) 2022年我的面试万字总结(Vue下)
(9) 2022年我的面试万字总结(Vue3+TS)
(10) 2022年我的面试万字总结(Node、webpack、性能优化)
(11) 2022年我的面试万字总结(小程序、git)
一、手写代码题
1. 手写Object.create
思路:将传入的目标作为原型
function create(obj) {
function F() {}
F.prototype = obj
return new F()
}
2. 手写instanceof
instanceof 运算符用于判别结构函数的 prototype 特点是否出现在目标的原型链中的任何位置。
完结过程:
- 首要获取类型的原型
- 然后取得目标的原型
- 然后一向循环判别目标的原型是否等于类型的原型,直到目标原型为
null
,由于原型链最终为null
function myInstanceof(left, right) {
let proto = Object.getPrototypeOf(left), // 获取目标的原型
prototype = right.prototype; // 获取结构函数的 prototype 目标
// 判别结构函数的 prototype 目标是否在目标的原型链上
while (true) {
if (!proto) return false;
if (proto === prototype) return true;
proto = Object.getPrototypeOf(proto);
}
}
3. 手写 new
(1)首要创立了一个新的空目标
(2)设置原型,将目标的原型设置为函数的 prototype 目标。
(3)让函数的 this 指向这个目标,履行结构函数的代码(为这个新目标增加特点)
(4)判别函数的回来值类型,假如是值类型,回来创立的目标。假如是引证类型,就回来这个引证类型的目标。
function myNew(fn, ...args) {
// 判别参数是否是一个函数
if (typeof fn !== "function") {
return console.error("type error");
}
// 创立一个目标,并将目标的原型绑定到结构函数的原型上
const obj = Object.create(fn.prototype);
const value = fn.apply(obj, args); // 调用结构函数,而且this绑定到obj上
// 假如结构函数有回来值,而且回来的是目标,就回来value ;不然回来obj
return value instanceof Object ? value : obj;
}
4. 手写promise(简易版)
class MyPromise {
constructor(fn){
// 存储 reslove 回调函数列表
this.callbacks = []
const resolve = (value) => {
this.data = value // 回来值给后边的 .then
while(this.callbacks.length) {
let cb = this.callbacks.shift()
cb(value)
}
}
fn(resolve)
}
then(onResolvedCallback) {
return new MyPromise((resolve) => {
this.callbacks.push(() => {
const res = onResolvedCallback(this.data)
if (res instanceof MyPromise) {
res.then(resolve)
} else {
resolve(res)
}
})
})
}
}
// 这是测验事例
new MyPromise((resolve) => {
setTimeout(() => {
resolve(1)
}, 1000)
}).then((res) => {
console.log(res)
return new MyPromise((resolve) => {
setTimeout(() => {
resolve(2)
}, 1000)
})
}).then(res =>{console.log(res)})
4.2 Promise.all
MyPromise.all = function (promisesList) {
return new MyPromise((resolve, reject) => {
if (!Array.isArray(promiselList) return reject(new Error('有必要是数组'))
if (!promisesList.length) return resolve([])
let arr = [], count = 0
// 直接循环一起履行传进来的promise
for (let i = 0, len = promisesList.length; i < len; i++) {
// 由于有或许是 promise 有或许不是,所以用resolve()不论是不是都会主动转成promise
Promise.resolve(promise).then(result => {
// 由到promise在初始化的时分就履行了,.then只是拿成果而已,所以履行完结的次序有或许和传进来的数组不一样
// 也便是说直接push到arr的话,次序有或许会犯错
count++
arr[i] = result
// 不能用arr.length===len,是由于数组的特性
// arr=[]; arr[3]='xx'; console.log(arr.length) 这打印出来会是4 而不是1
if(count === len) resolve(arr)
}).catch(err => reject(err))
}
})
}
4.3 Promise.race
传参和上面的 all 一模一样,传入一个 Promise 实例调集的数组,然后悉数一起履行,谁先快先履行完就回来谁,只回来一个成果
MyPromise.race = function(promisesList) {
return new MyPromise((resolve, reject) => {
// 直接循环一起履行传进来的promise
for (const promise of promisesList) {
// 直接回来出去了,所以只要一个,就看哪个快
promise.then(resolve, reject)
}
})
}
5. 防抖和节省
函数防抖是指在事情被触发 n 秒后再履行回调,假如在这 n 秒内事情又被触发,则重新计时。这能够运用在一些点击恳求的事情上,防止由于用户的屡次点击向后端发送屡次恳求。
函数节省是指规则一个单位时刻,在这个单位时刻内,只能有一次触发事情的回调函数履行,假如在同一个单位时刻内某事情被触发屡次,只要一次能收效。节省能够运用在 scroll 函数的事情监听上,经过事情节省来降低事情调用的频率。
// //防抖
function debounce(fn, date) {
let timer //声明接纳定时器的变量
return function (...arg) { // 获取参数
timer && clearTimeout(timer) // 清空定时器
timer = setTimeout(() => { // 生成新的定时器
//由于箭头函数里的this指向上层效果域的this,所以这儿能够直接用this,不需求声明其他的变量来接纳
fn.apply(this, arg) // fn()
}, date)
}
}
//--------------------------------
// 节省
function debounce(fn, data) {
let timer = +new Date() // 声明初始时刻
return function (...arg) { // 获取参数
let newTimer = +new Date() // 获取触发事情的时刻
if (newTimer - timer >= data) { // 时刻判别,是否满意条件
fn.apply(this, arg) // 调用需求履行的函数,修正this值,而且传入参数
timer = +new Date() // 重置初始时刻
}
}
}
6. 手写 call 函数
call 函数的完结过程:
- 判别调用目标是否为函数,即便咱们是界说在函数的原型上的,可是或许出现运用 call 等办法调用的状况。
- 判别传入上下文目标是否存在,假如不存在,则设置为 window 。
- 处理传入的参数,截取第一个参数后的一切参数。
- 将函数作为上下文目标的一个特点。
- 运用上下文目标来调用这个办法,并保存回来成果。
- 删去方才新增的特点。
- 回来成果。
// call函数完结
Function.prototype.myCall = function(context) {
// 判别调用目标
if (typeof this !== "function") {
console.error("type error");
}
// 获取参数
let args = [...arguments].slice(1),
result = null;
// 判别 context 是否传入,假如未传入则设置为 window
context = context || window;
// 将调用函数设为目标的办法
context.fn = this;
// 调用函数
result = context.fn(...args);
// 将特点删去
delete context.fn;
return result;
};
7. 手写 apply 函数
apply 函数的完结过程:
- 判别调用目标是否为函数,即便咱们是界说在函数的原型上的,可是或许出现运用 call 等办法调用的状况。
- 判别传入上下文目标是否存在,假如不存在,则设置为 window 。
- 将函数作为上下文目标的一个特点。
- 判别参数值是否传入
- 运用上下文目标来调用这个办法,并保存回来成果。
- 删去方才新增的特点
- 回来成果
// apply 函数完结
Function.prototype.myApply = function(context) {
// 判别调用目标是否为函数
if (typeof this !== "function") {
throw new TypeError("Error");
}
let result = null;
// 判别 context 是否存在,假如未传入则为 window
context = context || window;
// 将函数设为目标的办法
context.fn = this;
// 调用办法
if (arguments[1]) {
result = context.fn(...arguments[1]);
} else {
result = context.fn();
}
// 将特点删去
delete context.fn;
return result;
};
8. 手写 bind 函数
bind 函数的完结过程:
- 判别调用目标是否为函数,即便咱们是界说在函数的原型上的,可是或许出现运用 call 等办法调用的状况。
- 保存当时函数的引证,获取其他传入参数值。
- 创立一个函数回来
- 函数内部运用 apply 来绑定函数调用,需求判别函数作为结构函数的状况,这个时分需求传入当时函数的 this 给 apply 调用,其他状况都传入指定的上下文目标。
// bind 函数完结
Function.prototype.myBind = function(context) {
// 判别调用目标是否为函数
if (typeof this !== "function") {
throw new TypeError("Error");
}
// 获取参数
var args = [...arguments].slice(1),
fn = this;
return function Fn() {
// 依据调用办法,传入不同绑定值
return fn.apply(
this instanceof Fn ? this : context,
args.concat(...arguments)
);
};
};
9. 函数柯里化的完结
函数柯里化指的是一种将运用多个参数的一个函数转化成一系列运用一个参数的函数的技术。
function curry(fn, ...args) {
return fn.length <= args.length ? fn(...args) : curry.bind(null, fn, ...args);
}
10. 手写AJAX恳求
创立AJAX恳求的过程:
- 创立一个 XMLHttpRequest 目标。
- 在这个目标上运用 open 办法创立一个 HTTP 恳求,open 办法所需求的参数是恳求的办法、恳求的地址、是否异步和用户的认证信息。
- 在建议恳求前,能够为这个目标增加一些信息和监听函数。比方说能够经过 setRequestHeader 办法来为恳求增加头信息。还能够为这个目标增加一个状况监听函数。一个 XMLHttpRequest 目标一共有 5 个状况,当它的状况改动时会触发onreadystatechange 事情,能够经过设置监听函数,来处理恳求成功后的成果。当目标的 readyState 变为 4 的时分,代表服务器回来的数据接纳完结,这个时分能够经过判别恳求的状况,假如状况是 2xx 或许 304 的话则代表回来正常。这个时分就能够经过 response 中的数据来对页面进行更新了。
- 当目标的特点和监听函数设置完结后,最终调用 sent 办法来向服务器建议恳求,能够传入参数作为发送的数据体。
const SERVER_URL = "/server";
let xhr = new XMLHttpRequest();
// 创立 Http 恳求
xhr.open("GET", SERVER_URL, true);
// 设置状况监听函数
xhr.onreadystatechange = function() {
if (this.readyState !== 4) return;
// 当恳求成功时
if (this.status === 200) {
handle(this.response);
} else {
console.error(this.statusText);
}
};
// 设置恳求失利时的监听函数
xhr.onerror = function() {
console.error(this.statusText);
};
// 设置恳求头信息
xhr.responseType = "json";
xhr.setRequestHeader("Accept", "application/json");
// 发送 Http 恳求
xhr.send(null);
11. 运用Promise封装AJAX恳求
// promise 封装完结:
function getJSON(url) {
// 创立一个 promise 目标
let promise = new Promise(function(resolve, reject) {
let xhr = new XMLHttpRequest();
// 新建一个 http 恳求
xhr.open("GET", url, true);
// 设置状况的监听函数
xhr.onreadystatechange = function() {
if (this.readyState !== 4) return;
// 当恳求成功或失利时,改动 promise 的状况
if (this.status === 200) {
resolve(this.response);
} else {
reject(new Error(this.statusText));
}
};
// 设置过错监听函数
xhr.onerror = function() {
reject(new Error(this.statusText));
};
// 设置呼应的数据类型
xhr.responseType = "json";
// 设置恳求头信息
xhr.setRequestHeader("Accept", "application/json");
// 发送 http 恳求
xhr.send(null);
});
return promise;
}
12. 手写深仿制
function fn(obj) {
// 判别数据是否是复杂类型
if (obj instanceof Object) {
//判别数据是否是数组
if (Array.isArray(obj)) {
//声明一个空数组来接纳仿制后的数据
let result = []
obj.forEach(item => {
// 需求递归深层遍历,不然仿制的是地址
result.push(fn(item))
})
// 回来输出这个数组,数组仿制完结
return result
} else {
//假如是目标,就声明一个空目标来接纳仿制后的数据
let result = {}
for (let k in obj) {
// 运用递归深层遍历
result[k] = fn(obj[k])
}
// 回来输出这个目标,目标仿制完结
return result
}
}
// 简略数据类型则直接回来输出
return obj
}
13. 手写打乱数组次序的办法
首要的完结思路便是:
- 取出数组的第一个元素,随机发生一个索引值,将该第一个元素和这个索引对应的元素进行交流。
- 第2次取出数据数组第二个元素,随机发生一个除了索引为1的之外的索引值,并将第二个元素与该索引值对应的元素进行交流
- 依照上面的规则履行,直到遍历完结
let arr = [1,2,3,4,5,6,7,8,9,10];
for (let i = 0; i < arr.length; i++) {
const randomIndex = Math.round(Math.random() * (arr.length - 1 - i)) + i;
[arr[i], arr[randomIndex]] = [arr[randomIndex], arr[i]];
}
console.log(arr)
14. 完结数组扁平化
经过循环递归的办法,一项一项地去遍历,假如每一项仍是一个数组,那么就持续往下遍历,运用递归程序的办法,来完结数组的每一项的衔接:
let arr = [1, [2, [3, 4, 5]]];
function flatten(arr) {
let result = [];
for(let i = 0; i < arr.length; i++) {
if(Array.isArray(arr[i])) {
result = result.concat(flatten(arr[i]));
} else {
result.push(arr[i]);
}
}
return result;
}
flatten(arr); // [1, 2, 3, 4,5]
15. 完结数组的flat办法
function _flat(arr, depth) {
if(!Array.isArray(arr) || depth <= 0) {
return arr;
}
return arr.reduce((prev, cur) => {
if (Array.isArray(cur)) {
return prev.concat(_flat(cur, depth - 1))
} else {
return prev.concat(cur);
}
}, []);
}
16. 完结数组的push办法
let arr = [];
Array.prototype.push = function() {
for( let i = 0 ; i < arguments.length ; i++){
this[this.length] = arguments[i] ;
}
return this.length;
}
17. 完结数组的filter办法
Array.prototype._filter = function(fn) {
if (typeof fn !== "function") {
throw Error('参数有必要是一个函数');
}
const res = [];
for (let i = 0, len = this.length; i < len; i++) {
fn(this[i]) && res.push(this[i]);
}
return res;
}
18. 完结数组的map办法
Array.prototype._map = function(fn) {
if (typeof fn !== "function") {
throw Error('参数有必要是一个函数');
}
const res = [];
for (let i = 0, len = this.length; i < len; i++) {
res.push(fn(this[i]));
}
return res;
}
19. 完结 add(1)(2)(3)(4)
能够完结恣意数量数字相加,可是需求用+号隐式转化
function fn() {
let result = [];
function add(...args) {
// ...args剩下参数,能够获取到传进来的参数
result = [...result, ...args]
return add;
};
// 创立一个取代 valueOf 办法的函数,掩盖自界说目标的 valueOf 办法
add.toString = () => result.reduce((sum, k) => sum + k, 0);
return add;
};
let add = fn()
console.log(+add(1)(2)(3)(4)) // --->10
// let add2 = fn();
console.log(+add2(1, 2, 3)(4)) // --->10
参数固定的状况下,不需求用+号,能够依据参数长度来判别回来值
function currying(fn, length) {
length = length || fn.length; // 第一次调用,给length赋值fn的长度,后边每次重复调用,length的长度都会减去参数的长度
return function (...args) {
return args.length >= length // 当时传递进来的参数的长度与length长度进行比较
? fn.apply(this, args) // 把最终一组实参传给为赋值的形参,此刻一切形参都已赋值,并调用fn函数
: currying(fn.bind(this, ...args), length - args.length)
// 每一次调用fn.bind,都会把当时的args里的实参顺次传给fn的形参,length的长度减去参数的长度
// 相当于fn.bind(this, 1).bind(this, 2, 3),bind的接连调用,来填充fn的参数
// 直到某一次调用,fn的形参行将悉数都被赋值时,条件建立,会履行fn.apply,把最终的参数传递曩昔,而且调用fn
}
}
function fn(a, b, c, d) {
return a + b + c + d
}
const add = currying(fn)
add(4)(3)(1)(2) //10
add(1, 3)(4)(2) //10
add(1)(3, 4, 2) //10
20. 用Promise完结图片的异步加载
let imageAsync=(url)=>{
return new Promise((resolve,reject)=>{
let img = new Image();
img.src = url;
img.nlad=()=>{
console.log(`图片恳求成功,此处进行通用操作`);
resolve(image);
}
img.nerrr=(err)=>{
console.log(`失利,此处进行失利的通用操作`);
reject(err);
}
})
}
imageAsync("url").then(()=>{
console.log("加载成功");
}).catch((error)=>{
console.log("加载失利");
})
21. 手写发布-订阅形式
class EventCenter{
// 1. 界说事情容器,用来装事情数组
let handlers = {}
// 2. 增加事情办法,参数:事情名 事情办法
addEventListener(type, handler) {
// 创立新数组容器
if (!this.handlers[type]) {
this.handlers[type] = []
}
// 存入事情
this.handlers[type].push(handler)
}
// 3. 触发事情,参数:事情名 事情参数
dispatchEvent(type, params) {
// 若没有注册该事情则抛犯过错
if (!this.handlers[type]) {
return new Error('该事情未注册')
}
// 触发事情
this.handlers[type].forEach(handler => {
handler(...params)
})
}
// 4. 事情移除,参数:事情名 要删去事情,若无第二个参数则删去该事情的订阅和发布
removeEventListener(type, handler) {
if (!this.handlers[type]) {
return new Error('事情无效')
}
if (!handler) {
// 移除事情
delete this.handlers[type]
} else {
const index = this.handlers[type].findIndex(el => el === handler)
if (index === -1) {
return new Error('无该绑定事情')
}
// 移除事情
this.handlers[type].splice(index, 1)
if (this.handlers[type].length === 0) {
delete this.handlers[type]
}
}
}
}
22. Object.defineProperty(简易版)
// Vue2的呼应式原理,结合了Object.defineProperty的数据绑架,以及发布订阅者形式
// Vue2的数据绑架,便是经过递归遍历data里的数据,用Object.defineProperty给每一个特点增加getter和setter,
// 而且把data里的特点挂载到vue实例中,修正vue实例上的特点时,就会触发对应的setter函数,向Dep订阅器发布更新消息,
// 对应的Watcher订阅者会收到告诉,调用自身的回调函数,让编译器去更新视图。
const obj = {
name: '刘逍',
age: 20
}
const p = {}
for (let key in obj) {
Object.defineProperty(p, key, {
get() {
console.log(`有人读取p里的${key}特点`);
return obj[key]
},
set(val) {
console.log(`有人修正了p里的${key}特点,值为${val},需求去更新视图`);
obj[key] = val
}
})
}
23. Proxy数据绑架(简易版)
// Vue3的数据绑架经过Proxy函数对署理目标的特点进行绑架,经过Reflect目标里的办法对署理目标的特点进行修正,
// Proxy署理目标不需求遍历,装备项里的回调函数能够经过参数拿到修正特点的键和值
// 这儿用到了Reflect目标里的三个办法,get,set和deleteProperty,办法需求的参数与装备项中回调函数的参数相同。
// Reflect里的办法与Proxy里的办法是一一对应的,只要是Proxy目标的办法,就能在Reflect目标上找到对应的办法。
const obj = {
name: '刘逍',
age: 20
}
const p = new Proxy(obj, {
// 读取特点的时分会调用getter
get(target, propName) { //第一个参数为署理的源目标,等同于上面的Obj参数。第二个参数为读取的那个特点值
console.log(`有人读取p目标里的${propName}特点`);
return Reflect.get(target, propName)
},
// 增加和修正特点的时分会调用setter
set(target, propName, value) { //参数等同于get,第三个参数为修正后的特点值
console.log(`有人修正了p目标里的${propName}特点,值为${value},需求去修正视图`);
Reflect.set(target, propName, value)
},
// 删去特点时,调用deleteProperty
deleteProperty(target, propName) { // 参数等同于get
console.log(`有人删去了p目标里的${propName}特点,需求去修正视图`);
return Reflect.deleteProperty(target, propName)
}
})
24. 完结路由(简易版)
// hash路由
class Route{
constructor(){
// 路由存储目标
this.routes = {}
// 当时hash
this.currentHash = ''
// 绑定this,防止监听时this指向改动
this.freshRoute = this.freshRoute.bind(this)
// 监听
window.addEventListener('load', this.freshRoute, false)
window.addEventListener('hashchange', this.freshRoute, false)
}
// 存储
storeRoute (path, cb) {
this.routes[path] = cb || function () {}
}
// 更新
freshRoute () {
this.currentHash = location.hash.slice(1) || '/'
this.routes[this.currentHash]()
}
}
25. 运用 setTimeout 完结 setInterval
完结思路是运用递归函数,不断地去履行 setTimeout 从而到达 setInterval 的效果
function mySetInterval(fn, timeout) {
// 控制器,控制定时器是否持续履行
var timer = {
flag: true
};
// 设置递归函数,模仿定时器履行。
function interval() {
if (timer.flag) {
fn();
setTimeout(interval, timeout);
}
}
// 发动定时器
setTimeout(interval, timeout);
// 回来控制器
return timer;
}
26. 运用setInterval完结setTimeout
function mySetInterval(fn, t) {
const timer = setInterval(() => {
clearInterval(timer)
fn()
}, t)
}
mySetInterval(() => {
console.log('hoho');
}, 1000)
27. 完结 jsonp
// 动态的加载js文件
function addScript(src) {
const script = document.createElement('script');
script.src = src;
script.type = "text/javascript";
document.body.appendChild(script);
}
addScript("http://xxx.xxx.com/xxx.js?callback=handleRes");
// 设置一个全局的callback函数来接纳回调成果
function handleRes(res) {
console.log(res);
}
// 接口回来的数据格式
handleRes({a: 1, b: 2});
28. 提取出url 里的参数并转成目标
function getUrlParams(url){
let reg = /([^?&=]+)=([^?&=]+)/g
let obj = { }
url.replace(reg, function(){
obj[arguments[1]] = arguments[2]
})
// 或许
const search = window.location.search
search.replace(/([^&=?]+)=([^&]+)/g, (m, $1, $2)=>{obj[$1] = decodeURIComponent($2)})
return obj
}
let url = 'https://www.junjin.cn?a=1&b=2'
console.log(getUrlParams(url)) // { a: 1, b: 2 }
29. 请写至少三种数组去重的办法?(原生js)
//运用filter
function unique(arr) {
return arr.filter(function(item, index, arr) {
//当时元素,在原始数组中的第一个索引==当时索引值,不然回来当时元素
return arr.indexOf(item, 0) === index;
});
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//运用ES6 Set去重(ES6中最常用)
function unique (arr) {
return Array.from(new Set(arr))
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "true", true, 15, false, undefined, null, NaN, "NaN", 0, "a", {}, {}]
//运用for嵌套for,然后splice去重(ES5中最常用)
function unique (arr) {
for(var i=0; i<arr.length; i++){
for(var j=i+1; j<arr.length; j++){
if(arr[i]==arr[j]){ //第一个等同于第二个,splice办法删去第二个
arr.splice(j,1);
j--;
}
}
}
return arr;
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "true", 15, false, undefined, NaN, NaN, "NaN", "a", {…}, {…}]
//NaN和{}没有去重,两个null直接消失了
二、算法根底
1. 时刻&空间复杂度
- 复杂度是数量级(方便回忆、推行),不是具体数字。
- 常见复杂度巨细比较:O(n^2) > O(nlogn) > O(n) > O(logn) > O(1)
1.1 时刻复杂度
常见时刻复杂度对应关系:
- O(n^2):2层循环(嵌套循环)
- O(nlogn):快速排序(循环 + 二分)
- O(n):1层循环
- O(logn):二分
1.2 空间复杂度
常见空间复杂度对应关系:
- O(n):传入一个数组,处理过程生成一个新的数组巨细与传入数组共同
2. 八大数据结构
1. 栈
栈
是一个后进先出
的数据结构。JavaScript
中没有栈
,可是能够用Array
完结栈
的一切功用。
// 数组完结栈数据结构
const stack = []
// 入栈
stack.push(0)
stack.push(1)
stack.push(2)
// 出栈
const popVal = stack.pop() // popVal 为 2
运用场景
- 场景一:十进制转二进制
- 场景二:有效括号
- 场景三:函数调用仓库
2. 行列
行列
是一个先进先出
的数据结构。JavaScript
中没有行列
,可是能够用Array
完结行列
的一切功用。
// 数组完结行列数据结构
const queue = []
// 入队
stack.push(0)
stack.push(1)
stack.push(2)
// 出队
const shiftVal = stack.shift() // shiftVal 为 0
运用场景
- 场景一:日常测核酸排队
- 场景二:JS异步中的使命行列
- 场景三:核算最近恳求次数
3. 链表
链表
是多个元素组成的列表,元素存储不接连,用next
指针连在一起。JavaScript
中没有链表
,可是能够用Object
模仿链表
。
运用场景
- 场景一:JS中的原型链
- 场景二:运用链表指针获取 JSON 的节点值
4. 调集
调集
是一个无序且仅有
的数据结构。ES6
中有调集:Set
,调集常用操作:去重、判别某元素是否在调集中、求交集。
// 去重
const arr = [1, 1, 2, 2]
const arr2 = [...new Set(arr)]
// 判别元素是否在调集中
const set = new Set(arr)
const has = set.has(3) // false
// 求交集
const set2 = new Set([2, 3])
const set3 = new Set([...set].filter(item => set2.has(item)))
运用场景
- 场景一:求交集、差集
5. 字典(哈希)
字典
也是一种存储仅有值
的数据结构,但它以键值对
的形式存储。ES6
中的字典名为Map
,
// 字典
const map = new Map()
// 增
map.set('key1', 'value1')
map.set('key2', 'value2')
map.set('key3', 'value3')
// 删
map.delete('key3')
// map.clear()
// 改
map.set('key2', 'value222')
// 查
map.get('key2')
运用场景
- 场景:leetcode刷题
6. 树
树
是一种分层
的数据模型。前端常见的树包含:DOM、树、级联挑选、树形控件……。JavaScript
中没有树
,可是能够经过Object
和Array
构建树
。树的常用操作:深度/广度优先遍历、先中后序遍历。
运用场景
- 场景一:DOM树
- 场景二:级联挑选器
7. 图
图
是网络结构的笼统模型,是一组由边衔接的节点。图能够表明任何二元关系,比方路途、航班。JS中没有图,可是能够用Object
和Array
构建图
。图的表明法:邻接矩阵、邻接表、相关矩阵。
运用场景
- 场景一:路途
- 场景二:航班
8. 堆
堆
是一种特殊的彻底二叉树。一切的节点都大于等于(最大堆)或小于等于(最小堆)它的子节点。由于堆
的特殊结构,咱们能够用数组
表明堆
。
运用场景
- 场景:leetcode刷题
3. 排序办法
3.1 冒泡排序
比较两个记载键值的巨细,假如这两个记载键值的巨细出现逆序,则交流这两个记载
每遍历一个元素,都会把之前的一切相邻的元素都两两比较一遍,即便是现已排序好的元素
//[1,3,4,2]->[1,3,2,4]->[1,2,3,4]->[1,2,3,4]
let n = 0
function bubbleSort(arr){
for(let i = 1;i < arr.length;i++){
for(let j = i;j > 0;j--){
n++ // 1+2+3+...+arr.length-1
if(arr[j] < arr[j-1]){
[arr[j],arr[j-1]] = [arr[j-1],arr[j]];
}
}
}
return arr;
}
3.2 刺进排序
第i(i大于等于1)个记载进行刺进操作时,R1、 R2,…,是排好序的有序数列,取出第i个元素,在序列中找到一个适宜的位置并将她刺进到该位置上即可。
相当于把当时遍历的元素取出,在序列中找到一个适宜的位置将它刺进。它的第二层循环不必遍历当时元素之前的一切元素,由于当时元素之前的序列是排序好的,碰到第一个小于当时元素的值,就能够停止持续向前查找了,然后把当时元素刺进当时位置即可
function insertSort(arr){
for(let i = 1;i < arr.length;i++){
let j = i-1;
if(arr[i]<arr[j]){
let temp = arr[i];
while(j >= 0 && temp < arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
return arr;
}
//[1,3,4,2] ->[1,3,4,4]->[1,3,3,4]->[1,2,3,4]
//i=3 temp=2 j=2 arr[j]=4 arr[3]=4 [1,3,4,4]; j=1 arr[2]=3 [1,3,3,4]; j=0 [1,2,3,4]
3.3 希尔排序
算法先即将排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记载的下标相差d.对每组中悉数元素进行直接刺进排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接刺进排序。当增量减到1时,进行直接刺进排序后,排序完结。
function hillSort(arr){
let len = arr.length;
for(let gap = parseInt(len / 2);gap >= 1;gap = parseInt(gap / 2)){
for(let i = gap;i < len;i++){
if(arr[i] < arr[i-gap]){
let temp = arr[i];
let j = i - gap;
while(j >= 0 && arr[j] > temp){
arr[j+gap] = arr[j];
j -= gap;
}
arr[j+gap] = temp;
}
}
}
return arr;
}
3.4 挑选排序
在第i次挑选操作中,经过n-i次键值间比较,从n-i+1个记载中选出键值最小的记载,并和第i(1小于等于1小于等于n-1)个记载交流
每一次遍历,都把当时元素与剩下元素里的最小值交流位置
//[4,1,3,2]->[1,4,3,2]->[1,2,4,3]->[1,2,3,4]
function selectSort(arr){
for(let i = 0;i < arr.length;i++){
let min = Math.min(...arr.slice(i));
let index
for (let j = i; j < arr.length; j++) {
if (arr[j] === min) {
index = j
break
}
}
[arr[i],arr[index]] = [arr[index],arr[i]];
}
return arr;
}
3.5 快排
在n个记载中取某一个记载的键值为规范,一般取第一个记载键值为基准,经过一趟排序将待排的记载分为小于或等于这个键值的两个独立的部分,这是一部分的记载键值均比另一部分记载的键值小,然后,对这两部分记载持续分别进行快速排序,以到达整个序列有序
取当时排序数组的第一个值作为基准值keys,经过一次遍历把数组分为right大于基准值和left小于等于基准值的两部分,然后对两个部分重复以上过程排序,最终return的时分依照[left,keys,right]的次序回来
function quickSort(arr){
if(arr.length <= 1) return arr;
let right = [],left = [],keys = arr.shift();
for(let value of arr){
if(value > keys){
right.push(value)
}else{
left.push(value);
}
}
return quickSort(left).concat(keys,quickSort(right));
}
//[4,1,3,2]-->quickSort([1,3,2]).concat(4,quickSort([]))
// -->quickSort([]).concant(1,quickSort([3,2])).concat(4,quickSort([]))
// -->quickSort([]).concant(1,quickSort([2]).concant(3)).concat(4,quickSort([]))
// -->[1,2,3,4]
//keys=4 R[] L[1,3,2]
-------quickSort(left)
//keys=1 R[3,2] L[]
//keys=3 R[] L[2]
//quickSort(left)=[1,2,3]
3.6各排序算法的稳定性,时刻复杂度,空间复杂度
每个言语的排序内部完结都是不同的。
对于 JS 来说,数组长度大于 10 会采用快排,不然运用刺进排序。挑选刺进排序是由于尽管时刻复杂度很差,可是在数据 量很小的状况下和 O(N * logN) 相差无几,然而刺进排序需求的常数时刻很小,所以相对其他排序来说更快。
4. JS尾递归优化斐波拉契数列
正常的斐波拉契数列js完结办法
const Fibonacci = (n) => {
if (n <= 1) return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(40) // 165580141 核算缓慢有延迟了
Fibonacci(100) // 栈溢出,无法得到成果仿制代码
运用尾递归优化该办法
const Fibonacci = (n, sum1 = 1, sum2 = 1) => {
if (n <= 1) return sum2;
return Fibonacci(n - 1, sum2, sum1 + sum2)
}
Fibonacci(10) // 89
Fibonacci(100) // 573147844013817200000 速度依旧很快
Fibonacci(1000) // 7.0330367711422765e+208 仍是没有压力仿制代码
尾递归优化能够在数量较大的核算中,能够起到很好的效果