题解 | #设计LRU缓存结构#

手写一个LRUMap

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
export function LRU(operators: number[][], k: number): number[] {
    // write code here
    const lruMap = new LRUMap(k)
    const result = []
    
    operators.forEach((ops) => {
        const [opt, ...item] = ops
        const [_key, value] = item
        const key = `${_key}`
        
        if (opt === 1){
           lruMap.set(key, value)
        } else if (opt === 2){
            result.push(lruMap.get(key))
        }

    })
    
    return result
}

class LRUMap {
    list: {key: string; value: any}[];
    size: number;
    keyIndex: object;
    constructor(size: number) {
        this.list = []
        this.size = size
        this.keyIndex = {}
    }
    has(key: string) {
        return key in this.keyIndex
    }
    delete(key: string) {
        const delIndex = this.keyIndex[key]
        
        // 开始删除
        delete this.keyIndex[key]
        const delItem = this.list.splice(delIndex, 1)
        
        // 更新索引，O(n)破功了
        this.updateIndex(delIndex)
        return delItem
    }
    updateIndex(index: number) {
        for(let i = index; i < this.list.length; i++){
            this.keyIndex[this.list[i].key] = i
        }
    }
    getIndex(key: string) {
        if(!this.has(key)){
            return  -1
        }
        return this.keyIndex[key]
    }
    get(key: string) {
        const index = this.getIndex(key)
        if(index === -1){
            return -1
        }
        
        // 删除并更新
        const delItem = this.delete(key)[0]
        this.update(key, delItem.value)
        
        return delItem.value
    }
    update(key: string, value: any) {
        // 添加并更新索引数据
        this.list.push({key, value})
        this.keyIndex[key] = this.list.length - 1
    }
    set(key: string, value: any){
        if(this.has(key)){
            this.delete(key)
        }else if(this.list.length >= this.size){
            const delItem = this.list[0]
            this.delete(delItem.key)
        }
        
        // 更新
        this.update(key, value)
    }
}