Description

算法步骤

题目要求get和put时间复杂度在O(1)。那么需要找到符合get或者put复杂度在O(1)内，符合这样的常见结构有链表、哈希表、数组，同时满足的只有map。但是map没法表达"最久没用"这个概念，同时我们还需要在超出容量的时候O(1)删除最久没用的key，因此我们想到双链表：

• 设计双向链表list，越靠近头部，那么说明结点加入的时间越久远
• n1 <=> n2 <=> n3 <=> n4 <=> n5
• capacity代表链表的节点总数
• 但是双链表没法O(1)获取，于是我们加入哈希表结构，让整个数据结构能够以O(1)的方式获取。我们让key-node的映射关系存储在map当中
• 通过key迅速拿到node，然后拿到其中的value

注意：对于双链表，在进行get或者put操作后，需要更新相关节点，让其处于链表头部表示最近使用了，它应该从尾部删除，因为它不是最久没使用的了。

整体方案：实现新数据结构的"增、删、查、改"，利用哈希表+双链表实现这个数据结构。

class Node {
  constructor(
    public key: number,
    public val: number,
    public next: Node | null = null,
    public prev: Node | null = null,
  ) { }
}

class LinkedList {
  private dummy: Node;

  constructor() {
    this.dummy = new Node(-1, -1);
    this.dummy.prev = this.dummy;
    this.dummy.next = this.dummy;
  }

  get last() {
    return this.dummy.prev;
  }

  addNodeByKey(key: number, val: number): Node {
    return this.addNode(new Node(key, val));
  }

  // 头插法，把新节点放到最前面（dummy后面）
  addNode(node: Node): Node {
    // 记住当前的位置
    const dummy = this.dummy;
    const oldFirst = this.dummy.next!;

    // 把新节点放到最前面（dummy后面）
    node.prev = dummy;
    dummy.next = node;

    // 把新节点和原来的第一个节点连起来（这个部分做到了双链表的循环）
    node.next = oldFirst;
    oldFirst.prev = node;

    return node;
  }

  delNode(node: Node): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }
}

class LRUCache {
  private nodeList: LinkedList = new LinkedList();
  private keyToNode: Map<number, Node> = new Map();

  constructor(private capacity: number) { }

  /**
   * O(1)
   * 如果key存在，返回key对应的value
   * 如果key不存在，返回-1
   */
  get(key: number): number {
    const node = this.getNode(key);

    return node ? node.val : -1;
  }

  /**
   * 如果key存在，变更key对应的value；
   * 如果key不存在，插入key。
   */
  put(key: number, val: number): void {
    const node = this.getNode(key);

    // 如果key存在，变更key对应的value
    if (node) {
      node.val = val;
    }
    else {
      this.addNode(key, val);
    }
  }

  protected addNode(key: number, val: number): Node {
    // 如果key不存在，插入key。（插入之前，如果插入的时候超出了容量capacity，那么应该放弃最久没使用的key）
    // 如果插入的时候超出了容量capacity,应该放弃最久没使用的key。涉及的两个结构都要删除key相关的内容
    if (this.keyToNode.size === this.capacity) {
      this.delNotUsed();
    }

    const node = this.nodeList.addNodeByKey(key, val);
    this.keyToNode.set(key, node);

    return node;
  }

  protected getNode(key: number): Node | undefined {
    const node = this.keyToNode.get(key);

    if (node) {
      this.markUsed(node);
    }

    return node;
  }

  protected markUsed(node: Node): void {
    this.nodeList.delNode(node);
    this.nodeList.addNode(node);
  }

  protected delNotUsed(): void {
    const node = this.nodeList.last;

    if (node) {
      this.nodeList.delNode(node);
      this.keyToNode.delete(node.key);
    }
  }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
Copy