设计LRU缓存结构

function set(record,key,value,k){
  record.unshift({key,value})//每次都从头部插入，作为最常用的位置
  //如果超过设定长度，则从尾部删除最不常用
  if(record.length>k){
    record.pop()
  }
}
function get(record,key){
  let pos=-1
  //遍历数组，找到对应的对象的位置
  for(let i=0;i<record.length;i++){
    if(record[i].key===key){
      pos = i
      break
    }
  }
  //如果找到，则先从当前位置删除，并将其移入头部位置，作为最常用
  if(pos!=-1){
    let res = record.splice(pos,1)
    record.unshift(res[0])
  }
  //默认pos为-1没找到
  return pos
}

  function LRU( operators ,  k ) {
      // write code here
    let res=[]
    let record=[]
    for(let i=0;i<operators.length;i++){
      //根据操作数组长度判断是设置值还是取值
      if(operators[i].length===3){
        set(record,operators[i][1],operators[i][2],k)
      } else {
        let getres = get(record,operators[i][1])
        //如果没有找到，则推入-1，找到则推入value，此时要找的对象已经在位置[0]
        getres===-1?res.push(-1):res.push(record[0].value)
      }
    }
    return res
  }
  module.exports = {
      LRU : LRU
  };

/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
/* 双向链表node*/
class LinkNode {
  constructor(key, value) {
    this.key = key;
    this.val = value;
    this.front = null;
    this.next = null;
  }
}
// LRU缓存数据结构
class LRUCache {
  constructor(capacity) {
    // 容量
    this.capacity = capacity;
    // cache链表元素map
    this.map = new Map();
    // 头
    this.head = new LinkNode(0, 0);
    // 尾
    this.tail = new LinkNode(0, 0);
    // 头==next==>尾
    this.head.next = this.tail;
    // 头<==front==尾
    this.tail.front = this.head;
  }
  // 增加
  set(key, value) {
    // 如果不在map里 添加进来
    if (!this.map.has(key)) {
      // 如果已经满容量了 删除尾部最后一个节点
      if (this.capacity === this.map.size) {
        this.deleteLastNode();
      }
      const temp = this.head.next;
      const node = new LinkNode(key, value);
      node.next = temp;
      node.front = this.head;
      this.head.next = node;
      temp.front = node;
      this.map.set(key, node);
    } else {
      const node = this.map.get(key);
      node.val = value;
      this.moveNodeTopTop(node);
    }

  }
  // 获取
  get(key) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      this.moveNodeTopTop(node);
      return node.val;
    }
    return -1;
  }
  // 删除最后一个节点
  deleteLastNode() {
    const lastNode = this.tail.front;
    lastNode.front.next = this.tail;
    this.tail.front = lastNode.front;
    this.map.delete(lastNode.key);
  }
  // 把节点移动到头部变成最新的
  moveNodeTopTop(node) {
    node.front.next = node.next;
    node.next.front = node.front;
    const temp = this.head.next;
    this.head.next = node;
    node.front = this.head;
    node.next = temp;
    temp.front = node;
  }
}
function LRU(operators, k) {
  const lruCache = new LRUCache(k);
  // 存储
  const res = [];
  for (let i = 0; i < operators.length; i++) {
    const item = operators[i];
    if (item.length === 3) {
      lruCache.set(item[1], item[2]);
    } else {
      // 拿最新的
      const val = lruCache.get(item[1]);
      res.push(val);
    }
  }
  return res;
}
module.exports = {
  LRU: LRU
};

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
function LRU( operators ,  k ) {
    const map = new Map();
    let head = new LinkNode(-1, -1);
    let tail = head;
    head.next = tail;
    tail.prev = head;
    function setHead(linkNode) {
        linkNode.next = head;
        linkNode.prev = tail;
        head.prev = linkNode;
        tail.next = linkNode;
        head = linkNode;
    }
    function deleteNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    let result = [];
    for(let i = 0; i < operators.length; i++) {
        const [op, key, val] = operators[i];
        const currentNode = map.get(key);
        if(currentNode) {
            if(currentNode !== head) { // 加了这一句就过了
                deleteNode(currentNode);
                setHead(currentNode);
            }
            if(op===2) {
              result.push(currentNode.val);
            } else {
              currentNode.val = val;
            }
        } else {
            if(op === 2) {
              result.push(-1)
            } else {
                const newNode = new LinkNode(key ,val);
                map.set(key, newNode);
                setHead(newNode);
                if(map.size > k) {
                    map.delete(tail.prev.key);
                    deleteNode(tail.prev);
                }
            }
        }
    }
    return result;
}

function LinkNode(key, val) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
}
module.exports = {
    LRU : LRU
};

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
function LRU( operators ,  k ) {
    const map = new Map();
    const arr = [];
    const result = [];
    for (let op of operators) {
        if (op[0] === 1) {
            map.set(op[1], op[2])
        } else if (op[0] === 2) {
            result.push(map.has(op[1]) ? map.get(op[1]) : -1)
        }
        let has = false;
        let index = arr.indexOf(op[1])
        if (index !== -1) {
            arr.splice(index, 1);
        }
        arr.push(op[1])
        if (arr.length > k) {
            const num = arr.shift();
            map.delete(num);
        }
    }
    return result;
}
module.exports = {
    LRU : LRU
};

function LRU( operators ,  k ) {
    // write code here
  this.map = new Map()
  this.set = function (key, val) {
    if (this.map.has(key)) {
      this.map.delete(key)
    } else {
      if (this.map.size === k) {
        let keys = this.map.keys()
        let key = keys.next().value
        this.map.delete(key)
      }
    }
    this.map.set(key, val)
  }
  this.get = function (key) {
    if (this.map.has(key)){
      let val = this.map.get(key)
      this.map.delete(key)
      this.map.set(key, val)
      return val
    }
    return -1
  }
  let res = []
  for(let o of operators){
    if (o[0] === 1) {
      this.set(o[1], o[2])
    } else if (o[0] === 2) {
      res.push(this.get(o[1]))
    }
  }
  return res
}
module.exports = {
    LRU : LRU
};