高频
一、手写LRU缓存
leetcode 446
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
- LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
- void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例:
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
a. LRU 缓存策略举例:
i. 假设缓存大小为 4,依次打开了 gitlab、力扣、微信、QQ,缓存链表为 QQ -> 微信 -> 力扣 -> gitlab;
ii. 若此时切换到了「微信」,则缓存链表更新为 微信 -> QQ -> 力扣 -> gitlab;
iii. 若此时打开了腾讯会议,因为缓存已经满 4 个 ,所以要进行缓存淘汰机制,删除链表的最后一位 「gitlab」,则缓存链表更新为 腾讯会议 -> 微信 -> QQ -> 力扣;
b. 本题用的是 map 迭代器,map 实现了 iterator,next 模拟链表的下一个指针,为了方便操作,这里将 map 第一个元素作为链表的最后一个元素;
let cache = new Map();
cache.set('a', 1);
cache.set('b', 2);
cache.set('c', 3);
cache.keys(); // MapIterator {'a', 'b', 'c'}
cache.keys().next().value; // a
a. 时间复杂度:对于 put 和 get 都是 O(1);
b. 空间复杂度:O(capacity);
class LRUCache {
capacity:number;
cache:Map<number,number> = new Map();
//缓存的容量
constructor(capacity: number) {
this.capacity = capacity
}
get(key: number): number {
if(this.cache.has(key)){
let value = this.cache.get(key);
//重新set,相当于更新到cache最后----可以保证删除时,最久未使用的在第一位
//先删除
this.cache.delete(key);
this.cache.set(key,value);
return value;
}
return -1;
}
put(key: number, value: number): void {
if(this.cache.has(key)){
this.cache.delete(key);
}
this.cache.set(key,value);
if(this.cache.size>this.capacity){
//利用next指针,反复进行put时,可以删除正确的缓存
this.cache.delete(this.cache.keys().next().value);
}
}
}
二、手写深拷贝
前置知识
前面文章我们讲到,JavaScript
中存在两大数据类型:
- 基本类型
- 引用类型
基本类型数据保存在在栈内存中
引用类型数据保存在堆内存中,引用数据类型的变量是一个指向堆内存中实际对象的引用,存在栈中
深拷贝
深拷贝开辟一个新的栈,两个对象属完成相同,但是对应两个不同的地址,修改一个对象的属性,不会改变另一个对象的属性
常见的深拷贝方式有:
- _.cloneDeep()
- jQuery.extend()
- JSON.stringify()
- 手写循环递归
console.log(obj1.b.f === obj2.b.f); // false
JSON.stringify()
const obj2=JSON.parse(JSON.stringify(obj1));
但是这种方式存在弊端,会忽略
undefined
、symbol
和函数
const obj = { name: 'A', name1: undefined, name3: function() {}, name4: Symbol('A') } const obj2 = JSON.parse(JSON.stringify(obj)); console.log(obj2); // {name: "A"}
function deepCopy(object) {
if (!object || typeof object !== "object") return object;
let newObject = Array.isArray(object) ? [] : {};
for (let key in object) {
if (object.hasOwnProperty(key)) {
newObject[key] = deepCopy(object[key]);
}
}
return newObject;
}
循环递归------考点
function deepClone(obj, hash = new WeakMap()) {
if (!object || typeof object !== "object") return object;
// 是对象的话就要进行深拷贝,遇到循环引用,将引用存储起来,如果存在就不再拷贝
if (hash.get(obj)) return hash.get(obj);
let cloneObj = Array.isArray(object) ? [] : {};
hash.set(obj, cloneObj);
for (let key in obj) {
if (obj.hasOwnProperty(key)) {
// 实现一个递归拷贝
cloneObj[key] = deepClone(obj[key], hash);
}
}
return cloneObj;
}
下面首先借助两张图,可以更加清晰看到浅拷贝与深拷贝的区别
从上图发现,浅拷贝和深拷贝都创建出一个新的对象,但在复制对象属性的时候,行为就不一样
浅拷贝只复制属性指向某个对象的指针,而不复制对象本身,新旧对象还是共享同一块内存,修改对象属性会影响原对象
// 浅拷贝
const obj1 = {
name : 'init',
arr : [1,[2,3],4],
};
const obj3=shallowClone(obj1) // 一个浅拷贝方法
obj3.name = "update";
obj3.arr[1] = [5,6,7] ; // 新旧对象还是共享同一块内存
console.log('obj1',obj1) // obj1 { name: 'init', arr: [ 1, [ 5, 6, 7 ], 4 ] }
console.log('obj3',obj3) // obj3 { name: 'update', arr: [ 1, [ 5, 6, 7 ], 4 ] }
但深拷贝会另外创造一个一模一样的对象,新对象跟原对象不共享内存,修改新对象不会改到原对象
// 深拷贝
const obj1 = {
name : 'init',
arr : [1,[2,3],4],
};
const obj4=deepClone(obj1) // 一个深拷贝方法
obj4.name = "update";
obj4.arr[1] = [5,6,7] ; // 新对象跟原对象不共享内存
console.log('obj1',obj1) // obj1 { name: 'init', arr: [ 1, [ 2, 3 ], 4 ] }
console.log('obj4',obj4) // obj4 { name: 'update', arr: [ 1, [ 5, 6, 7 ], 4 ] }
三、手写Array.filter/map/fill/reduce/forEach
/*
纯函数API :
concat
filter
map
reduce
slice
非纯函数API
splice
shift(unshift同理)
reverse
*/
forEach返回undefined不属于纯函数,同样的由every、some
Array.prototype._forEach = function(fn,_this){
if(typeof fn!='function') throw '需要传入一个函数';
if(!this instanceof Array) throw '需要传入一个数组';
let length = this.length;
for(let i=0;i<length;i++)
{
fn.call(_this,this[i],i,this)
}
}
纯函数API
concat() 方法用于合并两个或多个数组。此方法不会更改现有数组,而是返回一个新数组。
concat方法不会改变this或任何作为参数提供的数组,而是返回一个浅拷贝.也就是说,如果数组里有引用对象的话,拷贝过来的是引用地址
//实现一个简易concat
Array.prototype._concat = function(...args){
let context = this , result = [];
//如果数组为空,直接返回当前数组对象
if(!args.length){
return context
}
//如果没有参数,直接返回this
args.forEach( item => {
if(Object.prototype.toString.call(item) !== '[object Array]'){
result.push(item)
//判断参数里面有没有数组
}else{
item.forEach( it => result.push(it))
}
})
return result
}
console.log( []._concat(1,2,3,3,45))
console.log( []._concat(1,2,3,{name:'dd'},45))
console.log( []._concat([1,[2]],3,3,45))
console.log( []._concat() )
// [ 1, 2, 3, 3, 45 ]
// [ 1, 2, 3, { name: 'dd' }, 45 ]
// [ 1, [ 2 ], 3, 3, 45 ]
// []
filter() 方法创建一个新数组, 其包含通过所提供函数实现的测试的所有元素。
需要注意的点
- filter方法不会改变原数组,它返回过滤后的新数组。
- 这个过程是一次性的,后面数组改变不会影响filter的值
//实现一个简易filter
Array.prototype._filter = function(cb,thisArg){
let context = this
let cbThis = thisArg ? thisArg : null
let result = []
//this默认指向this,提供了thisArg的情况下指向thisArgs
context.forEach( (item,index,arr) => {
if(cb.call(cbThis,item,index,arr)){
result.push(item)
}
})
return result
}
console.log( [1,2,3,43]._filter( item => item&1 == 1 ) )
console.log( []._filter(item => item&1 == 1 , [1,2,3,43]) )
//[ 1, 3, 43 ]
//[]
map() 方法创建一个新数组,其结果是该数组中的每个元素是调用一次提供的函数后的返回值。
需要注意的点
- map方法不会改变原数组,它返回新数组。
- callback 函数会被自动传入三个参数:数组元素,元素索引,原数组本身。
- map函数的第二个参数是可选项,作为callback的this指向
//实现一个简易map
Array.prototype._map = function(cb,thisArg){
let context = this
let cbThis = thisArg ? thisArg : null
let result = []
//this默认指向this,提供了thisArg的情况下指向thisArgs
context.forEach( (item,index,arr) => {
result.push( cb.call(cbThis,item,index,arr) )
})
return result
}
console.log( [1,2,3]._map(Math.sqrt) )
console.log( [1,2,3]._map((index,item)=>{ return index * 2 + item}) )
// [ 1, 1.4142135623730951, 1.7320508075688772 ]
// [ 2, 5, 8 ]
reduce() 方法对数组中的每个元素执行一个由您提供的reducer函数(升序执行),将其结果汇总为单个返回值。
需要注意的点
- reduce方法不会改变原数组,它返回一个值。
- 提供初始值initialValue会更加安全(建议)
//实现一个简易reduce
Array.prototype._reduce = function(reducer,initialValue){
let context = this , startIndex = 1
debugger
//this默认指向this,提供了thisArg的情况下指向thisArgs
if(initialValue !== undefined){
startIndex = 0
}else{
initialValue = context[0]
}
for(let i = startIndex ; i < context.length ; i ++){
initialValue = reducer(initialValue,context[i],i,context)
}
return initialValue
}
console.log([1,2,3,34]._reduce((a,b) => a+b , 12))
console.log([1,2,3,34]._reduce((a,b) => a.concat(b) , []))
// 52
// [ 1, 2, 3, 34 ]
slice() 方法返回一个新的数组对象,这一对象是一个由 begin 和 end 决定的原数组的浅拷贝(包括 begin,不包括end)。原始数组不会被改变。
需要注意的点
- slice方法是对数组项的浅拷贝
- slice方法不会对原始数组进行修改
//实现一个简易slice
Array.prototype._slice = function(...args){
let len = this.length , result = []
let startIndex = args[0] === undefined ? 0 : args[0]
let endIndex = args[1] === undefined ? len : args[1] >= len?len:args[1]
for(let i = startIndex ; i < endIndex ; i ++ ){
result.push(this[i])
}
return result
}
console.log( [1,2,3,34,3,3,3,33,3]._slice() )
//[1, 2, 3, 34, 3,3, 3, 33, 3]
非纯函数API
splice()方法通过删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容。此方法会改变原数组。
需要注意的点
- 指定修改的开始位置(从0计数)。如果超出了数组的长度,则从数组末尾开始添加内容;如果是负值,则表示从数组末位开始的第几位(从-1计数,这意味着-n是倒数第n个元素并且等价于array.length-n);如果负数的绝对值大于数组的长度,则表示开始位置为第0位。
- 如果 deleteCount 大于 start 之后的元素的总数,则从 start 后面的元素都将被删除(含第 start 位)。 如果 deleteCount 被省略了,或者它的值大于等于array.length - start(也就是说,如果它大于或者等于start之后的所有元素的数量),那么start之后数组的所有元素都会被删除。 如果 deleteCount 是 0 或者负数,则不移除元素。这种情况下,至少应添加一个新元素
//实现一个简易splice
Array.prototype._splice = function(startIndex,count,...items){
debugger
let context = this , len = context.length;
let temp = this.slice()
startIndex = startIndex < 0 ? Math.abs(startIndex>=len)?0:len + startIndex : startIndex
//这里是判断startIndex负值相关情况
//这里是判断count值得情况
count = count <=0 ? 0 : count//count可以是负值
if( count >= len - startIndex ){
for(let i = 0 ; i < len - startIndex ; i ++){
context.pop()
}
items.forEach( item => {
context.push(item)
})
}else{//正常情况下得
context.length = len - count + items.length//数组原地操作
for(let j = context.length - 1 ; j >= startIndex + count ; j--){
context[j] = context[ j + count - items.length ]
}
for(let i = 0 ; i < items.length ; i ++){
context[startIndex + i] = items[i]
}
}
console.log(this)
return count === undefined ? temp.slice(startIndex) : temp.slice(startIndex,startIndex + count)
}
console.log( [1,2,3,34]._splice(1,2,3,4,45) )
// [ 1, 3, 4, 45, 34 ]
// [ 2, 3 ]
拓展:手写push、pop、shift、unshift------均为非纯函数
push
向数组末尾添加一个或多个元素,并返回数组新的长度
//通过数组的arguments属性
function push(){
for(let i=0;i<arguments.length;i++){
this[this.length] = arguments[i];
}
return this.length
}
Array.prototype.push = push;
unshift
向数组开头添加一个或多个元素,并且返回数组新的长度
function unshift(){
//创建一个新数组接收添加的元素
let newAry = [];
for(let i=0;i<arguments.length;i++){
newAry[i] = arguments[i];
}
let len = newAry.length;
for(let i=0;i<this.length;i++){
newAry[i+len] = this[i];
}
for(let i=0;i<newAry.length;i++){
this[i] = newAry[i];
}
return this.length;
}
Array.prototype.unshift = unshift;
pop
删除数组最后一项,并返回该删除项目
function pop(){
let returnVal = this[this.length-1];
this.length--;
return returnVal
}
Array.prototype.pop = pop;
shift
删除数组第一项,并且返回该删除项目
function shift(){
let newAry = [];
let reVal = this[0];
for(let i=0;i<this.length-1;i++){
newAry[i] = this[i+1];
}
for(let i=0;i<newAry.length;i++){
this[i] = newAry[i]
}
this.length--;
return reVal;
}
Array.prototype.shift = shift;
四、手写new操作符
前置知识
从上面介绍中,我们可以看到new
关键字主要做了以下的工作:
- 创建一个新的对象
obj
- 将对象与构建函数通过原型链连接起来
- 将构建函数中的
this
绑定到新建的对象obj
上 - 根据构建函数返回类型作判断,如果是原始值则被忽略,如果是返回对象,需要正常处理
举个例子:
function Person(name, age){
this.name = name;
this.age = age;
}
const person1 = new Person('Tom', 20)
console.log(person1) // Person {name: "Tom", age: 20}
t.sayName() // 'Tom'
流程图如下:
![img](https://static.vue-js.com/b429b990-7a39-11eb-85f6-6fac77c0c9b3.png)
手写
现在我们已经清楚地掌握了new
的执行过程
那么我们就动手来实现一下new
function mynew(Func, ...args) {
// 1.创建一个新对象
const obj = {}
// 2.新对象原型指向构造函数原型对象
obj.__proto__ = Func.prototype
// 3.将构建函数的this指向新对象
let result = Func.apply(obj, args)
// 4.根据返回值判断
return result instanceof Object ? result : obj
}
测试一下
function mynew(func, ...args) {
const obj = {}
obj.__proto__ = func.prototype
let result = func.apply(obj, args)
return result instanceof Object ? result : obj
}
function Person(name, age) {
this.name = name;
this.age = age;
}
Person.prototype.say = function () {
console.log(this.name)
}
let p = mynew(Person, "huihui", 123)
console.log(p) // Person {name: "huihui", age: 123}
p.say() // huihui
五、手写bind
从上面可以看到,apply
、call
、bind
三者的区别在于:
- 三者都可以改变函数的
this
对象指向 - 三者第一个参数都是
this
要指向的对象,如果如果没有这个参数或参数为undefined
或null
,则默认指向全局window
- 三者都可以传参,但是
apply
是数组,而call
是参数列表,且apply
和call
是一次性传入参数,而bind
可以分为多次传入 bind
是返回绑定this之后的函数,apply
、call
则是立即执行
实现bind
的步骤,我们可以分解成为三部分:
- 修改
this
指向 - 动态传递参数
// 方式一:只在bind中传递函数参数
fn.bind(obj,1,2)()
// 方式二:在bind中传递函数参数,也在返回函数中传递参数
fn.bind(obj,1)(2)
- 兼容
new
关键字
整体实现代码如下:
Function.prototype.myBind = function (context) {
// 判断调用对象是否为函数
if (typeof this !== "function") {
throw new TypeError("Error");
}
// 获取参数
const args = [...arguments].slice(1),
fn = this;
return function Fn() {
// 根据调用方式,传入不同绑定值
return fn.apply(this instanceof Fn ? new fn(...arguments) : context, args.concat(...arguments));
}
}
六、手写vue v-if/v-show
v-show原理
不管初始条件是什么,元素总是会被渲染
我们看一下在vue
中是如何实现的
代码很好理解,有transition
就执行transition
,没有就直接设置display
属性
// https://github.com/vuejs/vue-next/blob/3cd30c5245da0733f9eb6f29d220f39c46518162/packages/runtime-dom/src/directives/vShow.ts
export const vShow: ObjectDirective<VShowElement> = {
beforeMount(el, { value }, { transition }) {
el._vod = el.style.display === 'none' ? '' : el.style.display
if (transition && value) {
transition.beforeEnter(el)
} else {
setDisplay(el, value)
}
},
mounted(el, { value }, { transition }) {
if (transition && value) {
transition.enter(el)
}
},
updated(el, { value, oldValue }, { transition }) {
// ...
},
beforeUnmount(el, { value }) {
setDisplay(el, value)
}
}
v-if原理
v-if
在实现上比v-show
要复杂的多,因为还有else
else-if
等条件需要处理,这里我们也只摘抄源码中处理 v-if
的一小部分
返回一个node
节点,render
函数通过表达式的值来决定是否生成DOM
// https://github.com/vuejs/vue-next/blob/cdc9f336fd/packages/compiler-core/src/transforms/vIf.ts
export const transformIf = createStructuralDirectiveTransform(
/^(if|else|else-if)$/,
(node, dir, context) => {
return processIf(node, dir, context, (ifNode, branch, isRoot) => {
// ...
return () => {
if (isRoot) {
ifNode.codegenNode = createCodegenNodeForBranch(
branch,
key,
context
) as IfConditionalExpression
} else {
// attach this branch's codegen node to the v-if root.
const parentCondition = getParentCondition(ifNode.codegenNode!)
parentCondition.alternate = createCodegenNodeForBranch(
branch,
key + ifNode.branches.length - 1,
context
)
}
}
})
}
)
七、防抖与节流
//防抖函数
function debounce(func, delay) {
// 这里使用了闭包,所以 timer 不会轻易被销毁
let timer = null
// 生成一个新的函数并返回
return function (...args) {
// 清空定时器
if (timer) {
clearTimeout(timer)
}
// 重新启动定时器
timer = setTimeout(() => {
func.call(this, ...args)
}, delay)
}
}
//节流函数
function throttle(func, delay) {
let timer = null
// 在 delay 时间内,最多执行一次 func
return function (...args) {
if (!timer) {
timer = setTimeout(() => {
func.call(this, ...args)
// 完成一次计时,清空,待下一次触发
timer = null
}, delay)
}
}
}
八、手写 instanceof
// 原理:验证当前类的原型prototype是否会出现在实例的原型链proto上,只要在它的原型链上,则结果都为true
function myinstanceOf_(obj, class_name) {
// let proto = obj.__proto__;
let proto = Object.getPrototypeOf(obj)
let prototype = class_name.prototype
while (true) {
if (proto == null) return false
if (proto == prototype) return true
// proto = proto.__proto__;
proto = Object.getPrototypeOf(proto)
}
}
九、手写 call、apply、bind 函数
// 给函数的原型添加 _call 方法,使得所有函数都能调用 _call
// thisArg 就是要绑定的那个this;...args 扩展操作符传参,适合不定长参数,args是一个数组
Function.prototype._call = function(thisArg,...args){
// 1.获取需要执行的函数
let func = this
// 2.将 thisArg 转成对象类型(防止它传入的是非对象类型,例如123数字)
thisArg = (thisArg !== null && thisArg !== undefined) ? Object(thisArg) : window
// 3.使用 thisArg 调用函数,绑定 this
// 评论区大佬提出的改进方法,用 Symbol 创建一个独一无二的属性,避免属性覆盖或冲突的情况
let fn = Symbol()
thisArg[fn] = this
// thisArg.fn = fn
let result = thisArg[fn](...args)
delete thisArg[fn]
// 4.返回结果
return result
}
Function.prototype._apply = function(thisArg,argArray){
// 1.获取需要执行的函数
let fn = this
// 2.将 thisArg 转成对象类型(防止它传入的是非对象类型,例如123数字)
thisArg = (thisArg !== null && thisArg !== undefined) ? Object(thisArg) : window
// 判断一些边界情况
argArray = argArray || []
// 3.使用 thisArg 调用函数,绑定 this
thisArg.fn = fn
// 将传递过来的数组(可迭代对象)拆分,传给函数
let result = thisArg.fn(...argArray)
delete thisArg.fn
// 4.返回结果
return result
}
Function.prototype._call = function(thisArg,...args){
let fn = this
thisArg = (thisArg !== null && thisArg !== undefined) ? Object(thisArg) : window
thisArg.fn = fn
let result = thisArg.fn(...args)
delete thisArg.fn
return result
}
// 利用 call 模拟 bind
Function.prototype._bind = function(thisArg,...args){
let fn = this // 需要调用的那个函数的引用
// bind 需要返回一个函数
return function(){
return fn._call(thisArg, ...args)
}
}
十、手写AJAX请求
function ajax(url) {
// 创建一个 XHR 对象
return new Promise((resolve,reject) => {
const xhr = new XMLHttpRequest()
// 指定请求类型,请求URL,和是否异步
xhr.open('GET', url, true)
xhr.onreadystatechange = funtion() {
// 表明数据已就绪
if(xhr.readyState === 4) {
if(xhr.status === 200){
// 回调
resolve(JSON.stringify(xhr.responseText))
}
else{
reject('error')
}
}
}
// 发送定义好的请求
xhr.send(null)
})
}
十一、手写数组去重
// 1.Set + 数组复制
fuction unique1(array){
// Array.from(),对一个可迭代对象进行浅拷贝
return Array.from(new Set(array))
}
// 2.Set + 扩展运算符浅拷贝
function unique2(array){
// ... 扩展运算符
return [...new Set(array)]
}
// 3.filter,判断是不是首次出现,如果不是就过滤掉
function unique3(array){
return array.filter((item,index) => {
return array.indexOf(item) === index
})
}
// 4.创建一个新数组,如果之前没加入就加入
function unique4(array){
let res = []
array.forEach(item => {
if(res.indexOf(item) === -1){
res.push(item)
}
})
return res
}
进阶:如果数组内有数组和对象,应该怎么去重(此时对象的地址不同,用Set去不了重)
方法:
十二、手写数组扁平
// 方法1-3:递归
function flat1(array){
// reduce(): 对数组的每一项执行归并函数,这个归并函数的返回值会作为下一次调用时的参数,即 preValue
// concat(): 合并两个数组,并返回一个新数组
return array.reduce((preValue,curItem) => {
return preValue.concat(Array.isArray(curItem) ? flat1(curItem) : curItem)
},[])
}
function flat2(array){
let res = []
array.forEach(item => {
if(Array.isArray(item)){
// res.push(...flat2(item))
// 如果遇到一个数组,递归
res = res.concat(flat2(item))
}
else{
res.push(item)
}
})
return res
}
function flat3(array){
// some(): 对数组的每一项都运行传入的函数,如果有一项返回 TRUE,则这个方法返回 TRUE
while(array.some(item => Array.isArray(item))){
// ES6 增加了扩展运算符,用于取出参数对象的所有可遍历属性,拷贝到当前对象之中:
array = [].concat(...array)
console.log(...array)
}
return array
}
// 方法4、5:先转成字符串,再变回数组
function flat4(array){
//[1,[2,3]].toString() => 1,2,3
return array.toString().split(',').map(item => parseInt(item))
}
function flat5(array){
return array.join(',').split(',').map(item => Number(item))
}
另附:手写对象扁平化
十三、手写数组乱序
// 方法1: sort + Math.random()
function shuffle1(arr){
return arr.sort(() => Math.random() - 0.5);//
}
// 方法2:时间复杂度 O(n^2)
// 随机拿出一个数(并在原数组中删除),放到新数组中
function randomSortArray(arr) {
let backArr = [];
while (arr.length) {
let index = parseInt(Math.random() * arr.length);
backArr.push(arr[index]);
arr.splice(index, 1);
}
return backArr;
}
// 方法3:时间复杂度 O(n)
// 随机选一个放在最后,交换
function randomSortArray2(arr) {
let lenNum = arr.length - 1;
for (let i = 0; i < lenNum; i++) {
let index = parseInt(Math.random() * (lenNum + 1 - i));
[a[index],a[lenNum - i]] = [a[lenNum - i],a[index]]
}
return arr;
}
十四、手写 Promise.all()、Promise.race()、Promise.on() 等其他promise方法
function myAll(promises){
// 问题关键:什么时候要执行resolve,什么时候要执行 reject
return new Promise((resolve,reject) => {
results = []
// 迭代数组中的 Promise,将每个 promise 的结果保存到一个数组里
let counter = 0
for (let i = 0; i < promises.length; i++) {
// 如果不是 Promise 类型要先包装一下
// 调用 then 得到结果
Promise.resolve(promises[i]).then(res => {
// 这里不能用 push(),因为需要保证结果的顺序。感谢评论区大佬的批评指正
results[i] = res
counter++
// 如果全部成功,状态变为 fulfilled
if(counter === promises.length){
resolve(results)
}
},err => { // 如果出现了 rejected 状态,则调用 reject() 返回结果
reject(err)
})
}
}
)
}
// test
let p1 = new Promise(function (resolve, reject) {
setTimeout(function () {
resolve(1)
}, 1000)
})
let p2 = new Promise(function (resolve, reject) {
setTimeout(function () {
resolve(2)
}, 2000)
})
let p3 = new Promise(function (resolve, reject) {
setTimeout(function () {
resolve(3)
}, 3000)
})
myAll([p3, p1, p2]).then(res => {
console.log(res) // [3, 1, 2]
})
// 哪个 promise 状态先确定,就返回它的结果
function myRace(promises) {
return new Promise((resolve, reject) => {
promises.forEach(promise => {
Promise.resolve(promise).then(res => {
resolve(res)
}, err => {
reject(err)
})
})
})
}
//
function myOn(promises){
}
//
function myAllsetter(promises){
}
十五、手撕快排
PS: 常见的排序算法,像冒泡,选择,插入排序这些最好也背一下,堆排序归并排序能写则写。万一考到了呢,要是写不出就直接回去等通知了
const _quickSort = array => {
// 补全代码
quickSort(array, 0, array.length - 1)
// 别忘了返回数组
return array
}
const quickSort = (array, start, end) => {
// 注意递归边界条件
if(end - start < 1) return
// 取第一个数作为基准
const base = array[start]
let left = start
let right = end
while(left < right){
// 从右往左找小于基准元素的数,并赋值给右指针 array[right]
while(left < right && array[right] >= base) right--
array[left] = array[right]
// 从左往右找大于基准元素的数,并赋值给左指针 array[left]
while(left < right && array[left] <= base) left++
array[right] = array[left]
}
// 双指针重合处,将基准元素填到这个位置。基准元素已经事先保存下来了,因此不用担心上面的赋值操作会覆盖掉基准元素的值
// array[left] 位置已经确定,左边的都比它小,右边的都比它大
array[left] = base
quickSort(array, start, left - 1)
quickSort(array, left + 1, end)
return array
}
十六、手写 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);
}
// 接口返回的数据格式,加载完js脚本后会自动执行回调函数
handleRes({a: 1, b: 2});
十七、手写寄生组合继承
function Parent(name) {
this.name = name;
this.say = () => {
console.log(111);
};
}
Parent.prototype.play = () => {
console.log(222);
};
function Children(name,age) {
Parent.call(this,name);
this.age = age
}
Children.prototype = Object.create(Parent.prototype);
Children.prototype.constructor = Children;
十八、手写二分查找
// 迭代版
function search(nums, target) {
// write code here
if(nums.length === 0) return -1
let left = 0,right = nums.length - 1
// 注意这里的边界,有等号
while(left <= right){
let mid = Math.floor((left + right) / 2)
if(nums[mid] < target) left = mid + 1
else if(nums[mid] > target) right = mid - 1
else return mid
}
return -1
}
// 递归版
function binary_search(arr, low, high, key) {
if (low > high) {
return -1;
}
var mid = parseInt((high + low) / 2);
if (arr[mid] == key) {
return mid;
} else if (arr[mid] > key) {
high = mid - 1;
return binary_search(arr, low, high, key);
} else if (arr[mid] < key) {
low = mid + 1;
return binary_search(arr, low, high, key);
}
};
十九、手写函数柯里化
function sum(x,y,z) {
return x + y + z
}
function hyCurrying(fn) {
// 判断当前已经接收的参数的个数,和函数本身需要接收的参数是否一致
function curried(...args) {
// 1.当已经传入的参数 大于等于 需要的参数时,就执行函数
if(args.length >= fn.length){
// 如果调用函数时指定了this,要将其绑定上去
return fn.apply(this, args)
}
else{
// 没有达到个数时,需要返回一个新的函数,继续来接收参数
return function(...args2) {
//return curried.apply(this, [...args, ...args2])
// 接收到参数后,需要递归调用 curried 来检查函数的个数是否达到
return curried.apply(this, args.concat(args2))
}
}
}
return curried
}
var curryAdd = hyCurry(sum)
curryAdd(10,20,30)
curryAdd(10,20)(30)
curryAdd(10)(20)(30)
二十、CSS水平垂直居中
- 不定宽高div,实现子元素垂直、水平居中,三种以上3
二十一、CSS画三角形
二十二、CSS实现两栏和三栏布局
二十三、手写发布-订阅模式 || EventEmitter
on
发布和订阅
发布和订阅。在type上添加订阅者
emit
执行该订阅下的所有函数
执行该订阅下的所有函数。遍历type下的订阅者,执行。
off
取消某个函数的订阅
取消某个函数的订阅。在订阅者中找到fn然后删除
once
只执行一次订阅事件
once方法将handler函数挂载了type这个发布者上,如果执行emit就会执行handler函数中的内容,会先删除type上的所有的函数,然后执行fn。
class EventBus {
constructor() {
this.tasks = {}; // 按事件名称创建任务队列
}
/**
* 注册事件(订阅)
* @param {String} type 事件名称
* @param {Function} fn 回调函数
*/
on(type, fn) {
// 如果还没有注册过该事件,则创建对应事件的队列
if (!this.tasks[type]) {
this.tasks[type] = [];
}
// 将回调函数加入队列
this.tasks[type].push(fn);
}
/**
* 注册一个只能执行一次的事件
* @params type[String] 事件类型
* @params fn[Function] 回调函数
*/
once(type, fn) {
if (!this.tasks[type]) {
this.tasks[type] = [];
}
const that = this;
// 注意该函数必须是具名函数,因为需要删除,但该名称只在函数内部有效
function _once(...args) {
fn(...args);
that.off(type, _once); // 执行一次后注销
}
this.tasks[type].push(_once);
}
/**
* 触发事件(发布)
* @param {String} type 事件名称
* @param {...any} args 传入的参数,不限个数
*/
emit(type, ...args) {
// 如果该事件没有被注册,则返回
if (!this.tasks[type]) {
return;
}
// 遍历执行对应的回调数组,并传入参数
this.tasks[type].forEach((fn) => fn(...args));
}
/**
* 移除指定回调(取消订阅)
* @param {String} type 事件名称
* @param {Function} fn 回调函数
*/
off(type, fn) {
const tasks = this.tasks[type];
// 校验事件队列是否存在
if (!Array.isArray(tasks)) {
return;
}
// 利用 filter 删除队列中的指定函数
this.tasks[type] = tasks.filter((cb) => fn !== cb);
}
}
另附:手写观察者
Subject是构造函数,new Subject() 创建一个主题对象,该对象内部维护订阅当前主题的观察者数组。主题对象上有一些方法,如添加观察者(addObserver)、删除观察者(removeObserver)、通知观察者更新(notify)。 当notify 时实际上调用全部观察者 observer 自身的 update 方法。
Observer 是构造函数,new Observer() 创建一个观察者对象,该对象有一个 update 方法,观察者可以订阅主题,实际上是把自己加入到主题的订阅者列表里。
class Subject{
observers = [];
addObserver(observer){
this.observers.push(observer)
}
removeObserver(observer){
let index = this.observers.indexOf(observer)
if(index>-1){
this.observers.splice(index,1)
}
}
notify(){
this.observers.forEach(observer=>{
observer.update()
})
}
}
class Observer{
update(){
subscribeTo(subject){
dubject.addObserver(this)
}
}
}
//测试代码
let subject = new Subject()
let observer = new Observer()
observer.update = function(){
console.log('observer update')
}
observer.subscribeTo(subject) //观察者订阅主题
subject.notify()
二十四、下拉框
二十五、实现一个圆绕着中心一直转
<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<title> 页面名称 </title>
<style type="text/css">
@keyframes animX{
0% {left: 0px;}
100% {left: 500px;}
}
@keyframes animY{
0% {top: 0px;}
100% {top: 500px;}
}
#ball {
width: 100px;
height: 100px;
background-color: #f99;
border-radius: 50%;
position: absolute;
animation:animX 4s ease-in-out -2s infinite alternate, animY 4s ease-in-out infinite alternate;
}
</style>
</head>
<body>
<div id="ball"></div>
</body>
</html>
二十六、手写简单轮询
轮询请求就是间隔相同的时间(如5s)后不断地向服务端发起同一个接口的请求,当然不能无限次去请求,所以轮询必须要有个停止轮询的机制。
首先能想到的就是用setInterval
去实现,但是setInterval
做轮询的话,会有以下严重的问题
1. 即使调用的代码报错了,setInterval会持续的调用
2. setInterval不会等到上一次的请求响应后再执行,只要到了指定的时间间隔就会执行,哪怕有报错也会执行
3. setInterval定时不准确,这个跟事件循环有关,这里不展开啦~
function setTimer () {
let timer
axios.post(url, params)
.then(function (res) {
if(res){
console.log(res);
timer = setTimeout(() => {
this.setTimer()
}, 5000)
}else {
clearTimeout(timer) //清理定时任务
}
})
.catch(function (error) {
console.log(error);
});
},
二十七、使用闭包实现数据缓存
/*
* 使用立即执行函数
* */
var cacheConfig = (function(){
var obj={};
return {
setCache:function(k,v){
obj[k]=v;
},
getCache:function(k){
return obj[k];
}
}
})();
场景题、
1.实现sleep休眠函数
function Sleep(time){
return new Promise(resolve=>{
setTimeout(resolve, time);
})
}
(async function(){
console.log('start sleep in '+ new Date());
await Sleep(7000);
console.log('end sleep in ' + new Date());
})()
2.setTimeout 实现 setInterval
function setInterval(fn, time){
var interval = function(){
// time时间过去,这个异步被执行,而内部执行的函数正是interval,就相当于进了一个循环
setTimeout(interval, time);
// 同步代码
fn();
}
//interval被延迟time时间执行
setTimeout(interval,time);
}
3.异步循环打印 1,2,3
var sleep = function (time, i) {
return new Promise(function (resolve, reject) {
setTimeout(function () {
resolve(i);
}, time);
})
};
var start = async function () {
for (let i = 1; i <= 3; i++) {
let result = await sleep(1000, i);
console.log(result);
}
};
start();
4.循环打印红、黄、绿
function red() {
console.log('red');
}
function green() {
console.log('green');
}
function yellow() {
console.log('yellow');
}
const task = (timer, light) => {
new Promise((resolve, reject) => {
setTimeout(() => {
if (light === 'red') {
red()
}
else if (light === 'green') {
green()
}
else if (light === 'yellow') {
yellow()
}
resolve()
}, timer)
})
}
const taskRunner = async () => {
await task(3000, 'red')
await task(2000, 'green')
await task(2100, 'yellow')
taskRunner()
}
taskRunner()
中频
1.手写事件委托
function delegateEvent(parent,selector,type,fn){}
parent:事件绑定的父级
selector:选择器
type:事件类型
handle:事件处理函数
写之前先了解一下事件委托的概念:
它是通过事件冒泡机制,
即子元素上触发的事件会冒泡到父级上,即父级也会触发该类型的事件,
通过父级触发的事件拿到事件源对象e.target就可以知道真正触发事件的元素是什么。
举个例子,一个ul下面有1000个li,我们要给li绑定点击事件,如果给每个li都绑定一个点击事件会大量占用内存,不利于性能优化,这种情况下我们只需要在ul上绑定一个点击事件,通过class或者id来识别每个li,这样就大大减少了事件注册,而且再有新增的li时我们也无需再去注册点击事件
功能:点击li,哪个变成绿色,再次点击取消
HTML
<ul id="parent">
<li>1</li>
<li>1</li>
<li>1</li>
</ul>
CSS
.active{
background-color:green;
}
JS
const parent = document.getElementById('parent')
function changeColor(){
if(this.classList.contains('active')){
this.classList.remove('active')
}else{
this.classList.add('active');
}
}
delegateEvent(parent,'li','click',changeColor)
事件委托函数
// ============ 简单的事件委托
function delegateEvent(parent, selector, type, fn) {
if (parent.addEventListener){
parent.addEventListener(type, eventfn,false);
} else {//兼容老IE
parent.attachEvent( "on" + type, eventfn);
}
function eventfn(e){
//兼容老IE
const e = e || window.event;
//兼容老IE
const target = e.target || e.srcElement;
//如果目标元素与选择器匹配则执行函数
if (matchSelector(target, selector)) {
if (fn) {//将fn内部的this指向target(在此之前this都是指向的绑定事件的元素即interfaceEle)
fn.call(target, e);
}
}
}
}
/**
* only support #id, tagName, .className
* and it's simple single, no combination
*/
//比较函数:判断事件的作用目标是否与选择器匹配;匹配则返回true
function matchSelector(ele, selector) {
// 如果选择器为ID
if (selector.charAt(0) === "#" ) {
return ele.id === selector.slice(1);
}
//charAt(0),返回索引为0的字符
//slice(a,b),从已有的数组或字符串返回从索引从a处开始,截取到索引b之前的子数组或子字符串;
//如果选择器为Class
if (selector.charAt(0) === "." ) {
return ( " " + ele.className + " " ).indexOf( " " + selector.slice(1) + " " ) != -1;
}
// 如果选择器为tagName
return ele.tagName.toLowerCase() === selector.toLowerCase();
}
//toLowerCase()将字符串转换成小写