分析

题目要求时间复杂度为O(1)，且最多储存k个key

梳理下javascript可用的数据结构：

  1. 对象 ：

    object.create(null) 无法获取最早插入的key，不能满足超过k个数就删除

  2. 数组 ：

    数组可以满足排序，但是查找和删除的时间复杂度都为O(n)

我们需要的数据结构是能够记录操作顺序，即可以快速删除，又可以快速查找。

因此可以将双向链表和字典结合使用。

  1. 构建字典用于存放ListNode节点
  2. 设置双向链表的head和tail
  3. set操作时构建ListNode节点，并将其放在链表尾部。
    1. 若字典长度超出k,则将链表头部数据删除，并删除字典中相应的keydelete cache[key]
  4. get操作时根据字典查找到指定ListNode节点，删除后，再重新插入，执行3操作

题解

方案一：使用双向链表和字典结合实现

class ListNode {
  prev: ListNode | null;
  next: ListNode | null;
  value: any;
  key: string | number;
  constructor(key = 0, val = '', prev = null, next = null) {
    this.value = val || '';
    this.prev = prev || null;
    this.next = next || null;
    this.key = key;
  }
}
class Solution {
  cache: { [key: string]: ListNode | null };
  head: ListNode;
  tail: ListNode;
  max = 0;
  constructor(max: number) {
    this.cache = {};
    this.head = new ListNode();
    this.tail = new ListNode();
    this.tail.prev = this.head;
    this.head.next = this.tail;
    this.max = max;
  }
  set(key: string | number, value: any) {
    if (this.cache.hasOwnProperty(key)) {
      // 若存在，先删除指定节点，后添加
      const node = this.cache[key];
      this.remove(node);
    }
    const node = new ListNode(key as number, value, null, null);
    this.addToEnd(node);
    this.cache[key] = node;

    if (Object.keys(this.cache).length > this.max) {
      // 若超出，删除第一个的节点
      var fnode = this.head.next;
      this.remove(fnode);
      delete this.cache[fnode.key];
    }

  }
  get(key: string | number) {
    if (this.cache[key]) {
      const node = this.cache[key];
      this.remove(node);
      this.addToEnd(node);
      return node.value;
    } else {
      return -1;
    }
  }
  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  addToEnd(node) {
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev.next = node;
    this.tail.prev = node;
  }
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 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 solution = new Solution(k);
  const result: number[] = [];
  for (let k = 0; k < operators.length; k++) {
    const opt = operators[k];
    if (opt[0] === 1) {
      solution.set(opt[1], opt[2])
    } else if (opt[0] === 2) {
      result.push(solution.get(opt[1]));
    }
  }
  return result;
}

方案二：使用map数据结构

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
 function LRU( operators , k){
  const n = operators.length;
  const map = new Map();
  const res = []
  for(let i = 0;i < n;i ++){
      if(operators[i][0] === 1){
          set(operators[i][1],operators[i][2]);
      }else{
          res.push(get(operators[i][1]));
      }
  }
  function get(key){
      const val = map.get(key);
      if(val === undefined) return -1;
      map.delete(key);
      map.set(key,val);
      return val;
  }
  function set(key,val){
      if(map.has(key)) map.delete(key);
      map.set(key,val);
      if(map.size > k){
          map.delete(map.keys().next().value);
      }
  }
  return res;
}
module.exports = {
  LRU : LRU
};