146. LRU 缓存机制

原题链接：LeetCode 146. LRU 缓存机制

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

- `LRUCache(int capacity)` 以 **正整数** 作为容量 `capacity` 初始化 LRU 缓存

- `int get(int key)` 如果关键字 `key` 存在于缓存中，则返回关键字的值，否则返回 `-1` 。

- `void put(int key, int value)` 如果关键字 `key` 已经存在，则变更其数据值 `value` ；如果不存在，则向缓存中插入该组 `key-value` 。如果插入操作导致关键字数量超过 `capacity` ，则应该 **逐出** 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]

解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

提示：

- `1 <= capacity <= 3000`

- `0 <= key <= 10000`

0 <= value <= 105
最多调用 2 * 105 次 `get` 和 `put`

难度： Medium

题解代码

javascript

/**
 * @param {number} capacity
 */

// 这个题如果不用两个虚拟头部尾部节点 边界条件直接弄死人
class LinkListNode {
  constructor(key, val) {
    this.key = key;
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.hash = {};
    this.length = 0;
    this.capacity = capacity;
    this.head = new LinkListNode();
    this.tail = new LinkListNode();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key) {
    const node = this.hash[key];
    if (node) {
      this.moveToTail(node);
      return node.val;
    }
    return -1;
  }

  put(key, val) {
    let node = this.hash[key];
    if (node) {
      node.val = val;
      this.moveToTail(node);
    } else {
      node = new LinkListNode(key, val);
      node.val = val;
      this.addToTail(node);
      this.hash[key] = node;
      this.length++;
      if (this.length > this.capacity) {
        const key = this.removeHead();
        delete this.hash[key];
        this.length--;
      }
    }
  }

  moveToTail(node) {
    this.removeFromList(node);
    this.addToTail(node);
  }

  removeFromList(node) {
    const prev = node.prev;
    const next = node.next;
    prev.next = next;
    next.prev = prev;
  }

  addToTail(node) {
    const prev = this.tail.prev;
    prev.next = node;
    node.prev = prev;
    node.next = this.tail;
    this.tail.prev = node;
  }

  removeHead() {
    const node = this.head.next;
    this.removeFromList(node);
    return node.key;
  }
}

146. LRU 缓存机制 #

题目描述 #

题解代码 #

146. LRU 缓存机制

题目描述

题解代码