普通解法

export function LRU(operators: number[][], k: number): number[] {
  const result: number[] = [];
  let cache: number[][] = [];
  operators.forEach((cmd) => {
    const [op, key] = cmd;
    let value: number;
    const index = cache.findIndex((c) => c && c[0] === key);
    let args = index === -1 ? undefined : cache[index];
    switch (op) {
      case 1:
        value = cmd[2];
        if (args) {
          args[1] = value;
        } else {
          args = [key, value];
        }
        if (cache.length >= k) {
          cache.splice(index === -1 ? 0 : index, 1);
        }
        cache.push(args);
        break;
      case 2:
        if (args) {
          value = args[1];
          cache.splice(index, 1);
          cache.push([key, value]);
        }
        result.push(args ? args[1] : -1);
        break;
    }
  });
  return result;
}

使用双向链表

export function LRU(operators: number[][], k: number): number[] {
  return useCache(operators, k);
}

export function useCache(operators: number[][], k: number): number[] {
  const result: number[] = [];
  let cache = new LRUCache(k);
  operators.forEach((cmd) => {
    const [op, key, value] = cmd;
    switch (op) {
      case 1:
        cache.add(new Node(key, value))
        break;
      case 2:
        const node = cache.get(key)
        result.push(node === -1 ? -1 : node.value);
        break;
    }
  });
  return result;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
export function LRU(operators: number[][], k: number): number[] {
  return useCache(operators, k);
}

/**
 * 双向链表
 */
export function useCache(operators: number[][], k: number): number[] {
  const result: number[] = [];
  let cache = new LRUCache(k);
  operators.forEach((cmd) => {
    const [op, key, value] = cmd;
    switch (op) {
      case 1:
        cache.add(new Node(key, value))
        break;
      case 2:
        const node = cache.get(key)
        result.push(node === -1 ? -1 : node.value);
        break;
    }
  });
  return result;
}

class Node {
  public prev!: Node | undefined;
  public next!: Node | undefined;
  constructor(public key: number, public value: number) { }
}

class DoubleList {
  protected _size = 0;
  protected _first!: Node | undefined;
  protected _last!: Node | undefined;
  constructor(protected _limit: number) { }

  remove(node: Node | undefined): Node | undefined {
    if (!node) return node
    const prev = node.prev;
    const next = node.next;
    node.prev = undefined;
    node.next = undefined;
    if (prev) prev.next = next;
    if (next) next.prev = prev;
    if (node === this._first) this._first = next;
    if (node === this._last) this._last = prev;
    this._size--;
    return node;
  }

  put(node: Node): (callBack: (removedNode: Node | undefined) => void) => void {
    let removedNode: Node | undefined;
    if (this._size === this._limit) {
      removedNode = this._first;
      this.remove(this._first);
    }
    this._size++;

    if (!this._first) this._first = node;
    if (this._last) this._last.next = node;
    node.prev = this._last;
    this._last = node;
    return (callBack) => { callBack(removedNode) };
  }

  list(): Node[] {
    const result: Node[] = [];
    let tmp = this._last;
    while (tmp?.prev) {
      result.unshift(tmp);
      tmp = tmp.prev;
    }
    return result;
  }
}

class LRUCache {
  protected _list: DoubleList;
  protected _map: { [key: number]: Node } = {};
  constructor(limit: number) {
    this._list = new DoubleList(limit);
  }

  add(node: Node): this {
    const oldNode = this._map[node.key];
    if (oldNode) {
      this._list.remove(oldNode);
      delete this._map[oldNode.key]
    }
    this._list.put(node)(removedNode => removedNode && (delete this._map[removedNode.key]));
    this._map[node.key] = node;
    return this;
  }

  get(key: number) {
    const node = this._map[key];
    if (!node) return -1;
    this._list.remove(node);
    this._list.put(node);
    return node;
  }

  list(): Node[] {
    return this._list.list();
  }
}