Skip to content

lru-cache.md

Latest commit

 

History

History
249 lines (182 loc) · 7.37 KB

lru-cache.md

File metadata and controls

249 lines (182 loc) · 7.37 KB
Raw

146. LRU Cache - LRU 缓存

Tags - 题目标签

Description - 题目描述

EN:

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

 

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 104
  • 0 <= value <= 105
  • At most 2 * 105 calls will be made to get and put.

ZH-CN:

请你设计并实现一个满足  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

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language Runtime Memory Submission Time
typescript 568 ms 99.1 MB 2022/09/16 10:54 
type DBLinkNode = {
  prev: DBLinkNode | null;
  next: DBLinkNode | null;
  key: number;
  val: number;
}

class LRUCache {
  private static cap: number;
  private static len: number;
  private static DBLink: DBLinkNode;
  private static cache: Map<number, DBLinkNode>;
  private static head: DBLinkNode;
  private static tail: DBLinkNode;
  constructor(capacity: number) {
    LRUCache.cap = capacity;
    LRUCache.len = 0;
    // init tail guard and head guard
    LRUCache.DBLink = {
      prev: null,
      next: {
        prev: null,
        next: null,
        key: -1,
        val: -1,
      },
      key: -1,
      val: -1,
    };

    LRUCache.DBLink.next.prev = LRUCache.DBLink;

    LRUCache.head = LRUCache.DBLink;

    LRUCache.tail = LRUCache.DBLink.next;

    LRUCache.cache = new Map<number, DBLinkNode>();
  }

  get(key: number): number {
    if (!LRUCache.cache.has(key)) {
      return -1;
    }

    const node = LRUCache.cache.get(key);

    this.moveToHead(node);

    return node.val;
  }

  put(key: number, value: number): void {
    if (LRUCache.cache.has(key)) {
      const node = LRUCache.cache.get(key);
      node.val = value;
      this.moveToHead(node);
      return;
    }

    if (LRUCache.len + 1 > LRUCache.cap) {
      this.removeTail();
    }

    this.addToHead({
      prev: null,
      next: null,
      key,
      val: value,
    } as DBLinkNode);
  }

  moveToHead(node: DBLinkNode): void {
    node.prev.next = node.next;
    node.next.prev = node.prev;

    LRUCache.len -= 1;

    this.addToHead(node);
  }

  addToHead(node: DBLinkNode): void {
    node.prev = LRUCache.head;

    node.next = LRUCache.head.next;

    LRUCache.head.next.prev = node;

    LRUCache.head.next = node;

    if (!LRUCache.cache.has(node.key)) {
      LRUCache.cache.set(node.key, node);
    }

    LRUCache.len += 1;
  }

  removeTail(): void {
    let shouldDeleted = LRUCache.tail.prev;

    shouldDeleted.next = null;

    LRUCache.tail.prev = shouldDeleted.prev;

    LRUCache.tail.prev.next = LRUCache.tail;

    LRUCache.cache.delete(shouldDeleted.key);

    shouldDeleted = null;

    LRUCache.len -= 1;
  }
}

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

My Notes - 我的笔记

No notes