内容总结
本章讲解编写高质量代码的面试题，即常见的“手写代码”面试题。有比较基础的类型判断、手写 new，也有比较复杂的 LazyMan 和 LRU 缓存。
划重点
- 编码规范性
- 功能完整性
- 鲁棒性（健壮性）
8-4 手写一个JS函数，实现数组扁平化Array Flatten
题目
写一个函数，实现 Array flatten 扁平化，只减少一个嵌套层级
例如输入 [1, 2, [3, 4, [100, 200], 5], 6] 返回 [1, 2, 3, 4, [100, 200], 5, 6]
解答
- 遍历数组
- 如果 item 是数字，则累加
- 如果 item 是数组，则 forEach 累加其元素
8-5 【连环问】手写一个JS函数，实现数组深度扁平化
像 lodash flattenDepth ，例如输入 [1, 2, [3, 4, [100, 200], 5], 6] 返回 [1, 2, 3, 4, 100, 200, 5, 6]
最容易想到的解决方案就是递归
/**
* 数组深度扁平化，使用 push
* @param arr arr
*/
export function flattenDeep1(arr: any[]): any[] {
const res: any[] = []
arr.forEach(item => {
if (Array.isArray(item)) {
const flatItem = flattenDeep1(item) // 递归
flatItem.forEach(n => res.push(n))
} else {
res.push(item)
}
})
return res
}
/**
* 数组深度扁平化，使用 concat
* @param arr arr
*/
export function flattenDeep2(arr: any[]): any[] {
let res: any[] = []
arr.forEach(item => {
if (Array.isArray(item)) {
const flatItem = flattenDeep2(item) // 递归
res = res.concat(flatItem)
} else {
res = res.concat(item)
}
})
return res
}
// // 功能测试
// const arr = [1, [2, [3, ['a', [true], 'b'], 4], 5], 6]
// console.info( flattenDeep2(arr) )
还有一种 hack 的方式 toString —— 但万一数组元素是 {x: 100} 等引用类型就不可以了。
const nums = [1, 2, [3, 4, [100, 200], 5], 6]
nums.toString() // '1,2,3,4,100,200,5,6'
8-6 手写一个getType函数，获取详细的数据类型
题目
实现一个 getType 函数，传入一个变量，能准确的获取它的类型。
如 number string function object array map regexp 等。
类型判断
常规的类型判断一般用 typeof 和 instanceof ，但这俩也有一些缺点
- typeof 无法继续区分 object 类型
- instanceof 需要知道构造函数，即需要两个输入
枚举不是好方法
你可能觉得 typeof 和 instanceof 结合起来可以判断，枚举所有的类型。
这并不是一个好方法，因为手动枚举是不靠谱的，不具备完整性。
第一，你有可能忽略某些类型，如；第二，ES 有会继续增加新的类型，如 Symbol BigInt
function getType(x: any): string {
if (typeof x === 'object') {
if (Array.isArray(x)) return 'array'
if (x instance of Map) return 'map'
// 继续枚举...
}
return typeof x
}
使用 Object.prototype.toString
注意，必须用 Object.prototype.toString ，不可以直接用 toString。后者可能是子类重写的。
[1, 2].toString() // '1,2' （ 这样使用的其实是 Array.prototype.toString ）
Object.prototype.toString.call([1, 2]) // '[object Array]'
/**
* 获取详细的数据类型
* @param x x
*/
export function getType(x: any): string {
const originType = Object.prototype.toString.call(x) // '[object String]'
const spaceIndex = originType.indexOf(' ')
const type = originType.slice(spaceIndex + 1, -1) // 'String'
return type.toLowerCase() // 'string'
}
// // 功能测试
// console.info( getType(null) ) // 'null'
// console.info( getType(undefined) )
// console.info( getType(100) )
// console.info( getType('abc') )
// console.info( getType(true) )
// console.info( getType(Symbol()) )
// console.info( getType({}) )
// console.info( getType([]) )
// console.info( getType(() => {}) )
8-7 new一个对象的过程是什么，手写代码表示
题目
new 一个对象内部发生了什么，手写代码表示
class 是语法糖
ES6 使用 class 代替了 ES6 的构造函数
class Foo {
constructor(name) {
this.name = name
this.city = '北京'
}
getName() {
return this.name
}
}
const f = new Foo('双越')
其实 class 就是一个语法糖，它本质上和构造函数是一样的
function Foo(name) {
this.name = name
this.city = '北京'
}
Foo.prototype.getName = function () { // 注意，这里不可以用箭头函数
return this.name
}
const f = new Foo('双越')
new 一个对象的过程
- 创建一个空对象 obj，继承构造函数的原型
- 执行构造函数（将 obj 作为 this）
- 返回 obj
实现 new
export function customNew<T>(constructor: Function, ...args: any[]): T {
// 1. 创建一个空对象，继承 constructor 的原型
const obj = Object.create(constructor.prototype)
// 2. 将 obj 作为 this ，执行 constructor ，传入参数
constructor.apply(obj, args)
// 3. 返回 obj
return obj
}
// class Foo {
// // 属性
// name: string
// city: string
// n: number
// constructor(name: string, n: number) {
// this.name = name
// this.city = '北京'
// this.n = n
// }
// getName() {
// return this.name
// }
// }
// const f = new Foo('双越', 100)
// // const f = customNew<Foo>(Foo, '双越', 100)
// console.info(f)
// console.info(f.getName())
面试连环问：Object.create 和 {} 的区别
Object.create 可以指定原型，创建一个空对象。[HTML_REMOVED]
{} 就相当于 Object.create(Object.prototype) ，即根据 Object 原型的空对象。
8-8 8-9 广度优先遍历一个DOM树
题目
写一个函数遍历 DOM 树，分别用深度优先和广度优先
PS：注意回顾 “Node 和 Element 和区别”
深度优先 vs 广度优先
深度优先的结果 <div> <p> "hello" <b> "world" <img> 注释 <ul> <li> "a" <li> "b"
广度优先的结果 <div> <p> <img> 注释 <ul> "hello" <b> <li> <li> "world" "a" "b"
解答
- 深度优先，递归
- 广度优先，队列
/**
* 访问节点
* @param n node
*/
function visitNode(n: Node) {
if (n instanceof Comment) {
// 注释
console.info('Comment node ---', n.textContent)
}
if (n instanceof Text) {
// 文本
const t = n.textContent?.trim()
if (t) {
console.info('Text node ---', t)
}
}
if (n instanceof HTMLElement) {
// element
console.info('Element node ---', `<${n.tagName.toLowerCase()}>`)
}
}
/**
* 深度优先遍历
* @param root dom node
*/
function depthFirstTraverse1(root: Node) {
visitNode(root)
const childNodes = root.childNodes // .childNodes 和 .children 不一样
if (childNodes.length) {
childNodes.forEach(child => {
depthFirstTraverse1(child) // 递归
})
}
}
/**
* 深度优先遍历
* @param root dom node
*/
function depthFirstTraverse2(root: Node) {
const stack: Node[] = []
// 根节点压栈
stack.push(root)
while (stack.length > 0) {
const curNode = stack.pop() // 出栈
if (curNode == null) break
visitNode(curNode)
// 子节点压栈
const childNodes = curNode.childNodes
if (childNodes.length > 0) {
// reverse 反顺序压栈
Array.from(childNodes).reverse().forEach(child => stack.push(child))
}
}
}
/**
* 广度优先遍历
* @param root dom node
*/
function breadthFirstTraverse(root: Node) {
const queue: Node[] = [] // 数组 vs 链表
// 根节点入队列
queue.unshift(root)
while (queue.length > 0) {
const curNode = queue.pop()
if (curNode == null) break
visitNode(curNode)
// 子节点入队
const childNodes = curNode.childNodes
if (childNodes.length) {
childNodes.forEach(child => queue.unshift(child))
}
}
}
const box = document.getElementById('box')
if (box == null) throw new Error('box is null')
depthFirstTraverse2(box)
8-10 【连环问】深度优先遍历可以不用递归吗
深度优先遍历，可以使用栈代替递归，递归本质上就是栈。代码参考 dom-traverse.ts
递归和非递归哪个更好？
- 递归逻辑更加清晰，但容易出现 stack overflow 错误（可使用尾递归，编译器有优化）
- 非递归效率更高，但使用栈，逻辑稍微复杂一些
8-11 手写一个LazyMan，实现sleep机制
题目
手写 LazyMan ，实现 sleep 和 eat 两个方法，支持链式调用。
代码示例：
const me = new LazyMan('双越')
me.eat('苹果').eat('香蕉').sleep(5).eat('葡萄') // 打印结果如下：
// '双越 eat 苹果'
// '双越 eat 香蕉'
// （等待 5s）
// '双越 eat 葡萄'
设计 class 框架
class LazyMan {
private name: string
constructor(name: string) {
this.name = name
}
eat(x: string) {
// 打印 eat 行为
return this // 支持链式调用
}
sleep(seconds: number) {
// 等待 10s 的处理逻辑
return this // 支持链式调用
}
}
处理 sleep 逻辑
初始化一个任务队列，执行 eat 和 sleep 是都往队列插入一个函数。依次执行队列的任务，遇到 sleep 就延迟触发 next 。
class LazyMan {
private name: string
private tasks: Function[] = [] // 任务列表
constructor(name: string) {
this.name = name
setTimeout(() => {
this.next()
})
}
private next() {
const task = this.tasks.shift() // 取出当前 tasks 的第一个任务
if (task) task()
}
eat(food: string) {
const task = () => {
console.info(`${this.name} eat ${food}`)
this.next() // 立刻执行下一个任务
}
this.tasks.push(task)
return this // 链式调用
}
sleep(seconds: number) {
const task = () => {
console.info(`${this.name} 开始睡觉`)
setTimeout(() => {
console.info(`${this.name} 已经睡完了 ${seconds}s，开始执行下一个任务`)
this.next() // xx 秒之后再执行下一个任务
}, seconds * 1000)
}
this.tasks.push(task)
return this // 链式调用
}
}
const me = new LazyMan('双越')
me.eat('苹果').eat('香蕉').sleep(2).eat('葡萄').eat('西瓜').sleep(2).eat('橘子')
总结
- 链式调用
- 任务队列
- 延迟触发
8-12 手写curry函数，实现函数柯里化
题目
写一个 curry 函数，可以把其他函数转为 curry 函数
function add(a, b, c) { return a + b + c }
add(1, 2, 3) // 6
const curryAdd = curry(add)
curryAdd(1)(2)(3) // 6
解答
export function curry(fn: Function) {
const fnArgsLength = fn.length // 传入函数的参数长度
let args: any[] = []
// ts 中，独立的函数，this 需要声明类型
function calc(this: any, ...newArgs: any[]) {
// 积累参数
args = [
...args,
...newArgs
]
if (args.length < fnArgsLength) {
// 参数不够，返回函数
return calc
} else {
// 参数够了，返回执行结果
return fn.apply(this, args.slice(0, fnArgsLength))
}
}
return calc
}
// function add(a: number, b: number, c: number): number {
// return a + b + c
// }
// // add(10, 20, 30) // 60
// const curryAdd = curry(add)
// const res = curryAdd(10)(20)(30) // 60
// console.info(res)
总结
- 判断参数长度
- 中间态返回函数，最后返回执行结果
- 如用 this 慎用箭头函数
8-13 instanceof原理是什么，请写代码表示
题目
instanceof 的原理是什么，请用代码来表示
instanceof 原理
例如 a instanceof b 就是：顺着 a 的 __proto__ 链向上找，能否找到 b.prototype
/**
* 自定义 instanceof
* @param instance instance
* @param origin class or function
*/
export function myInstanceof(instance: any, origin: any): boolean {
if (instance == null) return false // null undefined
const type = typeof instance
if (type !== 'object' && type !== 'function') {
// 值类型
return false
}
let tempInstance = instance // 为了防止修改 instance
while (tempInstance) {
if (tempInstance.__proto__ === origin.prototype) {
return true // 配上了
}
// 未匹配
tempInstance = tempInstance.__proto__ // 顺着原型链，往上找
}
return false
}
// // 功能测试
// console.info( myInstanceof({}, Object) )
// console.info( myInstanceof([], Object) )
// console.info( myInstanceof([], Array) )
// console.info( myInstanceof({}, Array) )
// console.info( myInstanceof('abc', String) )
总结
- 原型链
- 循环判断
8-14 手写函数bind功能
bind 应用
- 返回一个新的函数（旧函数不会更改）
- 绑定
this和部分参数 - 箭头函数，无法改变
this，只能改变参数
function fn(a, b, c) {
console.log(this, a, b, c)
}
const fn1 = fn.bind({x: 100})
fn1(10, 20, 30) // {x: 100} 10 20 30
const fn2 = fn.bind({x: 100}, 1, 2)
fn2(10, 20, 30) // {x: 100} 1 2 10 （注意第三个参数变成了 10）
fn(10, 20, 30) // window 10 20 30 （旧函数不变）
解答
// @ts-ignore
Function.prototype.customBind = function (context: any, ...bindArgs: any[]) {
// context 是 bind 传入的 this
// bindArgs 是 bind 传入的各个参数
const self = this // 当前的函数本身
return function (...args: any[]) {
// 拼接参数
const newArgs = bindArgs.concat(args)
return self.apply(context, newArgs)
}
}
// // 功能测试
// function fn(this: any, a: any, b: any, c: any) {
// console.info(this, a, b, c)
// }
// // @ts-ignore
// const fn1 = fn.customBind({x: 100}, 10)
// fn1(20, 30)
要点
- 返回新函数
- 拼接参数（bind 参数 + 执行参数）
- 重新绑定 this
8-15 【连环问】手写函数call和apply功能
bind 生成新函数，暂不执行。而 call apply 会直接立即执行函数
- 重新绑定 this （箭头函数不支持）
- 传入参数
function fn(a, b, c) {
console.log(this, a, b, c)
}
fn.call({x: 100}, 10, 20, 30)
fn.apply({x: 100}, [10, 20, 30])
// @ts-ignore
Function.prototype.customCall = function (context: any, ...args: any[]) {
if (context == null) context = globalThis
if (typeof context !== 'object') context = new Object(context) // 值类型，变为对象
const fnKey = Symbol() // 不会出现属性名称的覆盖
context[fnKey] = this // this 就是当前的函数
const res = context[fnKey](...args) // 绑定了 this
delete context[fnKey] // 清理掉 fn ，防止污染
return res
}
// @ts-ignore
Function.prototype.customApply = function (context: any, args: any[] = []) {
if (context == null) context = globalThis
if (typeof context !== 'object') context = new Object(context) // 值类型，变为对象
const fnKey = Symbol() // 不会出现属性名称的覆盖
context[fnKey] = this // this 就是当前的函数
const res = context[fnKey](...args) // 绑定了 this
delete context[fnKey] // 清理掉 fn ，防止污染
return res
}
function fn(this: any, a: any, b: any, c: any) {
console.info(this, a, b, c)
}
// // @ts-ignore
// fn.customCall({x: 100}, 10, 20, 30)
// @ts-ignore
// fn.customApply({x: 200}, [100, 200, 300])
- 使用
obj.fn执行，即可设置fn执行时的this - 考虑
context各种情况 - 使用
symbol类型扩展属性
注意：有些同学用 call 来实现 apply （反之亦然），这样是不符合面试官期待的。
8-16 手写EventBus自定义事件
题目
Bus 不是“车”，而是“总线”
请手写 EventBus 自定义事件，实现 no once emit 和 off
EventBus 功能
const event = new EventBus()
function fn1(a, b) { console.log('fn1', a, b) }
function fn2(a, b) { console.log('fn2', a, b) }
function fn3(a, b) { console.log('fn3', a, b) }
event.on('key1', fn1)
event.on('key1', fn2)
event.once('key1', fn3)
event.on('xxxxxx', fn3)
event.emit('key1', 10, 20) // 触发 fn1 fn2 fn3
event.off('key1', fn1)
event.emit('key1', 100, 200) // 触发 fn2
实现
class结构- 注意区分
on和off
export default class EventBus {
/**
* {
* 'key1': [
* { fn: fn1, isOnce: false },
* { fn: fn2, isOnce: false },
* { fn: fn3, isOnce: true },
* ]
* 'key2': [] // 有序
* 'key3': []
* }
*/
private events: {
[key: string]: Array<{fn: Function; isOnce: boolean}>
}
constructor() {
this.events = {}
}
on(type: string, fn: Function, isOnce: boolean = false) {
const events = this.events
if (events[type] == null) {
events[type] = [] // 初始化 key 的 fn 数组
}
events[type].push({ fn, isOnce })
}
once(type: string, fn: Function) {
this.on(type, fn, true)
}
off(type: string, fn?: Function) {
if (!fn) {
// 解绑所有 type 的函数
this.events[type] = []
} else {
// 解绑单个 fn
const fnList = this.events[type]
if (fnList) {
this.events[type] = fnList.filter(item => item.fn !== fn)
}
}
}
emit(type: string, ...args: any[]) {
const fnList = this.events[type]
if (fnList == null) return
// 注意
this.events[type] = fnList.filter(item => {
const { fn, isOnce } = item
fn(...args)
// once 执行一次就要被过滤掉
if (!isOnce) return true
return false
})
}
}
// const e = new EventBus()
// function fn1(a: any, b: any) { console.log('fn1', a, b) }
// function fn2(a: any, b: any) { console.log('fn2', a, b) }
// function fn3(a: any, b: any) { console.log('fn3', a, b) }
// e.on('key1', fn1)
// e.on('key1', fn2)
// e.once('key1', fn3)
// e.on('xxxxxx', fn3)
// e.emit('key1', 10, 20) // 触发 fn1 fn2 fn3
// e.off('key1', fn1)
// e.emit('key1', 100, 200) // 触发 fn2
连环问：EventBus 里的数组可以换成 Set 吗？
数组和 Set 比较 （除了语法 API）
- 数组，有序结构，查找、中间插入、中间删除比较慢
- Set 不可排序的，插入和删除都很快
Set 初始化或者 add 时是一个有序结构，但它无法再次排序，没有 index 也没有 sort 等 API
验证
- 生成一个大数组，验证 push unshift includes splice
- 生成一个大 Set ，验证 add delete has
答案：不可以，Set 是不可排序的，如再增加一些“权重”之类的需求，将不好实现。
Map 和 Object
Object 是无序的
const data1 = {'1':'aaa','2':'bbb','3':'ccc','测试':'000'}
Object.keys(data1) // ["1", "2", "3", "测试"]
const data2 = {'测试':'000','1':'aaa','3':'ccc','2':'bbb'};
Object.keys(data2); // ["1", "2", "3", "测试"]
Map 是有序的
const m1 = new Map([
['1', 'aaa'],
['2', 'bbb'],
['3', 'ccc'],
['测试', '000']
])
m1.forEach((val, key) => { console.log(key, val) })
const m2 = new Map([
['测试', '000'],
['1', 'aaa'],
['3', 'ccc'],
['2', 'bbb']
])
m2.forEach((val, key) => { console.log(key, val) })
另外，Map 虽然是有序的，但它的 get set delete 速度非常快，和 Object 效率一样。它是被优化过的有序结构。
8-17 手写EventBus自定义事件-on和once分开存储
export default class EventBus2 {
private events: { [key: string]: Array<Function> } // { key1: [fn1, fn2], key2: [fn1, fn2] }
private onceEvents: { [key: string]: Array<Function> }
constructor() {
this.events = {}
this.onceEvents = {}
}
on(type: string, fn: Function) {
const events = this.events
if (events[type] == null) events[type] = []
events[type].push(fn)
}
once(type: string, fn: Function) {
const onceEvents = this.onceEvents
if (onceEvents[type] == null) onceEvents[type] = []
onceEvents[type].push(fn)
}
off(type: string, fn?: Function) {
if (!fn) {
// 解绑所有事件
this.events[type] = []
this.onceEvents[type] = []
} else {
// 解绑单个事件
const fnList = this.events[type]
const onceFnList = this.onceEvents[type]
if (fnList) {
this.events[type] = fnList.filter(curFn => curFn !== fn)
}
if (onceFnList) {
this.onceEvents[type] = onceFnList.filter(curFn => curFn !== fn)
}
}
}
emit(type: string, ...args: any[]) {
const fnList = this.events[type]
const onceFnList = this.onceEvents[type]
if (fnList) {
fnList.forEach(f => f(...args))
}
if (onceFnList) {
onceFnList.forEach(f => f(...args))
// once 执行一次就删除
this.onceEvents[type] = []
}
}
}
// const e = new EventBus2()
// function fn1(a: any, b: any) { console.log('fn1', a, b) }
// function fn2(a: any, b: any) { console.log('fn2', a, b) }
// function fn3(a: any, b: any) { console.log('fn3', a, b) }
// e.on('key1', fn1)
// e.on('key1', fn2)
// e.once('key1', fn3)
// e.on('xxxxxx', fn3)
// e.emit('key1', 10, 20) // 触发 fn1 fn2 fn3
// e.off('key1', fn1)
// e.emit('key1', 100, 200) // 触发 fn2
8-19 用JS实现一个LRU缓存-分析数据结构特点，使用Map
LRU 使用
Least Recently Used 最近最少使用[HTML_REMOVED]
即淘汰掉最近最少使用的数据，只保留最近经常使用的资源。它是一个固定容量的缓存容器。
const lruCache = new LRUCache(2); // 最大缓存长度 2
lruCache.set(1, 1); // 缓存是 {1=1}
lruCache.set(2, 2); // 缓存是 {1=1, 2=2}
lruCache.get(1); // 返回 1
lruCache.set(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lruCache.get(2); // 返回 null
lruCache.set(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lruCache.get(1); // 返回 null
lruCache.get(3); // 返回 3
lruCache.get(4); // 返回 4
分析
- 哈希表，即
{ k1: v1, k2: v2, ... }形式。可以O(1)事件复杂度存取keyvalue - 有序。可以根据最近使用情况清理缓存
JS 内置的数据结构类型 Object Array Set Map ，恰好 Map 符合这两条要求
Map 是有序的
Map 有序，Object 无序
实现
export default class LRUCache {
private length: number
private data: Map<any, any> = new Map()
constructor(length: number) {
if (length < 1) throw new Error('invalid length')
this.length = length
}
set(key: any, value: any) {
const data = this.data
if (data.has(key)) {
data.delete(key)
}
data.set(key, value)
if (data.size > this.length) {
// 如果超出了容量，则删除 Map 最老的元素
const delKey = data.keys().next().value
data.delete(delKey)
}
}
get(key: any): any {
const data = this.data
if (!data.has(key)) return null
const value = data.get(key)
data.delete(key)
data.set(key, value)
return value
}
}
// const lruCache = new LRUCache(2)
// lruCache.set(1, 1) // {1=1}
// lruCache.set(2, 2) // {1=1, 2=2}
// console.info(lruCache.get(1)) // 1 {2=2, 1=1}
// lruCache.set(3, 3) // {1=1, 3=3}
// console.info(lruCache.get(2)) // null
// lruCache.set(4, 4) // {3=3, 4=4}
// console.info(lruCache.get(1)) // null
// console.info(lruCache.get(3)) // 3 {4=4, 3=3}
// console.info(lruCache.get(4)) // 4 {3=3, 4=4}
注意，get set 时都要把操作数据移动到 Map 最新的位置。
扩展
实际项目中可以使用第三方 lib
- https://www.npmjs.com/package/quick-lru
- https://www.npmjs.com/package/lru-cache
- https://www.npmjs.com/package/tiny-lru
- https://www.npmjs.com/package/mnemonist
8-21 【连环问】不用Map实现LRU缓存-分析问题，使用双向链表
连环问：不用 Map 如何实现 LRU cache ？
LRU cache 是很早就有的算法，而 Map 仅仅是这几年才加入的 ES 语法。
使用 Object 和 Array
根据上文的分析，两个条件
- 哈希表，可以用 Object 实现
- 有序，可以用 Array 实现
// 执行 lru.set('a', 1) lru.set('b', 2) lru.set('c', 3) 后的数据
const obj1 = { value: 1, key: 'a' }
const obj2 = { value: 2, key: 'b' }
const obj3 = { value: 3, key: 'c' }
const data = [obj1, obj2, obj3]
const map = { 'a': obj1, 'b': obj2, 'c': obj3 }
模拟 get set 操作，会发现几个问题，都来自于数组
- 超出 cache 容量时，要移除最早的元素，数组 shift 效率低
- 每次 get set 时都要把当前元素移动到最新的位置，数组 splice 效率低
Array 改为双向链表
数组有问题，就需要使用新的数据结构 双向链表
Interface INode {
value: any
next?: INode
prev?: INode
}
双向链表可以快速移动元素。末尾新增元素 D 很简单，开头删除 A 元素也很简单。
要把中间的元素 B 移动到最后（如 LRU set get 时移动数据位置），只需要修改前后的指针即可，效率很高。
实现
interface IListNode {
value: any
key: string // 存储 key ，方便删除（否则删除时就需要遍历 this.data )
prev?: IListNode
next?: IListNode
}
export default class LRUCache {
private length: number
private data: { [key: string]: IListNode } = {}
private dataLength: number = 0
private listHead: IListNode | null = null
private listTail: IListNode | null = null
constructor(length: number) {
if (length < 1) throw new Error('invalid length')
this.length = length
}
private moveToTail(curNode: IListNode) {
const tail = this.listTail
if (tail === curNode) return
// -------------- 1. 让 prevNode nextNode 断绝与 curNode 的关系 --------------
const prevNode = curNode.prev
const nextNode = curNode.next
if (prevNode) {
if (nextNode) {
prevNode.next = nextNode
} else {
delete prevNode.next
}
}
if (nextNode) {
if (prevNode) {
nextNode.prev = prevNode
} else {
delete nextNode.prev
}
if (this.listHead === curNode) this.listHead = nextNode
}
// -------------- 2. 让 curNode 断绝与 prevNode nextNode 的关系 --------------
delete curNode.prev
delete curNode.next
// -------------- 3. 在 list 末尾重新建立 curNode 的新关系 --------------
if (tail) {
tail.next = curNode
curNode.prev = tail
}
this.listTail = curNode
}
private tryClean() {
while (this.dataLength > this.length) {
const head = this.listHead
if (head == null) throw new Error('head is null')
const headNext = head.next
if (headNext == null) throw new Error('headNext is null')
// 1. 断绝 head 和 next 的关系
delete headNext.prev
delete head.next
// 2. 重新赋值 listHead
this.listHead = headNext
// 3. 清理 data ，重新计数
delete this.data[head.key]
this.dataLength = this.dataLength - 1
}
}
get(key: string): any {
const data = this.data
const curNode = data[key]
if (curNode == null) return null
if (this.listTail === curNode) {
// 本身在末尾（最新鲜的位置），直接返回 value
return curNode.value
}
// curNode 移动到末尾
this.moveToTail(curNode)
return curNode.value
}
set(key: string, value: any) {
const data = this.data
const curNode = data[key]
if (curNode == null) {
// 新增数据
const newNode: IListNode = { key, value }
// 移动到末尾
this.moveToTail(newNode)
data[key] = newNode
this.dataLength++
if (this.dataLength === 1) this.listHead = newNode
} else {
// 修改现有数据
curNode.value = value
// 移动到末尾
this.moveToTail(curNode)
}
// 尝试清理长度
this.tryClean()
}
}
// const lruCache = new LRUCache(2)
// lruCache.set('1', 1) // {1=1}
// lruCache.set('2', 2) // {1=1, 2=2}
// console.info(lruCache.get('1')) // 1 {2=2, 1=1}
// lruCache.set('3', 3) // {1=1, 3=3}
// console.info(lruCache.get('2')) // null
// lruCache.set('4', 4) // {3=3, 4=4}
// console.info(lruCache.get('1')) // null
// console.info(lruCache.get('3')) // 3 {4=4, 3=3}
// console.info(lruCache.get('4')) // 4 {3=3, 4=4}
注意事项
- 数据结构如何定义，data 和链表分别存储什么
- 双向链表的操作（非常繁琐，写代码很容易出错，逻辑一定要清晰！！！）
- 链表 node 中要存储 data.key ，否则删除 data 需要遍历、效率低
8-23 手写JS深拷贝-考虑各种数据类型和循环引用
分析
这是一个很常见的问题，看似也很简单，但是如果考虑到“高质量代码”的要求，写起来还是挺麻烦的。
别说写代码，就本节所有的情况你能否考虑全面，这都不一定。
错误答案1
使用 JSON.stringify 和 JSON.parse
- 无法转换函数
- 无法转换 Map Set
- 无法转换循环引用
PS：其实普通对象使用 JSON API 的运算速度很快，但功能不全
错误答案2
使用 Object.assign —— 这根本就不是深拷贝，是浅拷贝 ！！！
错误答案3
只考虑了普通的对象和数组
- 无法转换 Map Set
- 无法转换循环引用
正确答案
// /**
// * 深拷贝 - 只考虑了简单的数组、对象
// * @param obj obj
// */
// function cloneDeep(obj: any) {
// if (typeof obj !== 'object' || obj == null ) return obj
// let result: any
// if (obj instanceof Array) {
// result = []
// } else {
// result = {}
// }
// for (let key in obj) {
// if (obj.hasOwnProperty(key)) {
// result[key] = cloneDeep(obj[key]) // 递归调用
// }
// }
// return result
// }
// // 功能测试
// const a: any = {
// set: new Set([10, 20, 30]),
// map: new Map([['x', 10], ['y', 20]])
// }
// a.self = a
// console.log( cloneDeep(a) ) // 无法处理 Map Set 和循环引用
/**
* 深拷贝
* @param obj obj
* @param map weakmap 为了避免循环引用
*/
export function cloneDeep(obj: any, map = new WeakMap()): any {
if (typeof obj !== 'object' || obj == null ) return obj
// 避免循环引用
const objFromMap = map.get(obj)
if (objFromMap) return objFromMap
let target: any = {}
map.set(obj, target)
// Map
if (obj instanceof Map) {
target = new Map()
obj.forEach((v, k) => {
const v1 = cloneDeep(v, map)
const k1 = cloneDeep(k, map)
target.set(k1, v1)
})
}
// Set
if (obj instanceof Set) {
target = new Set()
obj.forEach(v => {
const v1 = cloneDeep(v, map)
target.add(v1)
})
}
// Array
if (obj instanceof Array) {
target = obj.map(item => cloneDeep(item, map))
}
// Object
for (const key in obj) {
const val = obj[key]
const val1 = cloneDeep(val, map)
target[key] = val1
}
return target
}
// // 功能测试
// const a: any = {
// set: new Set([10, 20, 30]),
// map: new Map([['x', 10], ['y', 20]]),
// info: {
// city: '北京'
// },
// fn: () => { console.info(100) }
// }
// a.self = a
// console.log( cloneDeep(a) )
循环引用
Map Set 函数
8-24 扩展补充：根据一个 DOM 树，写出一个虚拟 DOM 对象
题目
讲一下 DOM 结构转换为 vnode 数据
<div id="div1" style="border: 1px solid #ccc; padding: 10px;">
<p>一行文字<a href="xxx.html" target="_blank">链接</a></p>
<img src="xxx.png" alt="图片" class="image"/>
<button click="clickHandler">点击</button>
</div>
答案
vdom 就是用 JS 对象的形式来表示 DOM 结构。vnode 即对应着 DOM 结构的一个 node 节点。
const vnode = {
tag: 'div', // <div>
data: {
id: 'div1',
style: {
'border': '1px solid #ccc',
'padding': '10px'
}
},
children: [
{
tag: 'p', // <p>
data: {},
children: [
'一行文字',
{
tag: 'a', // <a>
data: {
href: 'xxx.html',
target: '_blank'
},
children: ['链接']
}
]
},
{
tag: 'img', // <img>
data: {
className: 'image', // 注意，这里要用 className
src: 'xxx.png',
alt: '图片'
}
},
{
tag: 'button', // <button>
data: {
events: {
click: clickHandler
}
}
children: ['点击']
}
]
}
注意事项
- vdom 结构没有固定的标准，例如
tag可以改为name，data可以改为props。只要能合理使用 JS 数据表达 DOM 即可。 style和events要以对象的形式，更易读，更易扩展class是 ES 内置关键字，要改为className。其他的还有如for改为htmlFor
