题解 | #设计LRU缓存结构# （day2）

这个题非常经常会考！出现次数很多，但是前端好像没怎么见到过

希望o（1）操作get和set，看了解释双向链表和map做。 而js中map本身可以定义一个可迭代的iterator，再走next（）可以按照插入的顺序访问，一旦size超过限度，就把最开始加入的（也就是走一次next的）清除就ok。

注意next（）每次调用一次，指针就会往后走一次

此外额外注意坑： 已有（1,1）重新插入（1,2）要额外做判断

每次get的时候要提到经常使用那一列，为了方便可以直接删除原来的 ，加入新的（新加入的在末尾），也就应了最常使用

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */

function LRU( operators ,  k ) {
    //if(operators===null)return [];
    var ans=new Array();
    var m=new Map();
    operators.forEach((item,index)=>{
        if(item[0]===2){//查询 get
             let value=m.get(item[1]);
            if(value){
                ans.push(value);
                 m.delete(item[1]);
                m.set(item[1],value);
            }else{
                ans.push(-1);
            }
        }else if(item[0]===1){//插入  set
            if(m.get(item[1])){
                m.delete(item[1]);
                m.set(item[1],item[2]);
            }else{
                m.set(item[1],item[2]);
                if(m.size>k){
                    let iterator=m.entries();
                    m.delete(iterator.next().value[0]);
                }
            }
          }
    })
    return ans;
}
module.exports = {
    LRU : LRU
};