Question

146. LRU 缓存

English Version

题目描述

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

解法

方法一：哈希表 + 双向链表

我们可以用“哈希表”和“双向链表”实现一个 LRU 缓存。

• 哈希表：用于存储 key 和对应的节点位置。
• 双向链表：用于存储节点数据，按照访问时间排序。

当访问一个节点时，如果节点存在，我们将其从原来的位置删除，并重新插入到链表头部。这样就能保证链表尾部存储的就是最近最久未使用的节点，当节点数量大于缓存最大空间时就淘汰链表尾部的节点。

当插入一个节点时，如果节点存在，我们将其从原来的位置删除，并重新插入到链表头部。如果不存在，我们首先检查缓存是否已满，如果已满，则删除链表尾部的节点，将新的节点插入链表头部。

时间复杂度 $O(1)$，空间复杂度 $O(capacity)$。

class Node:
  def __init__(self, key=0, val=0):
    self.key = key
    self.val = val
    self.prev = None
    self.next = None


class LRUCache:
  def __init__(self, capacity: int):
    self.cache = {}
    self.head = Node()
    self.tail = Node()
    self.capacity = capacity
    self.size = 0
    self.head.next = self.tail
    self.tail.prev = self.head

  def get(self, key: int) -> int:
    if key not in self.cache:
      return -1
    node = self.cache[key]
    self.move_to_head(node)
    return node.val

  def put(self, key: int, value: int) -> None:
    if key in self.cache:
      node = self.cache[key]
      node.val = value
      self.move_to_head(node)
    else:
      node = Node(key, value)
      self.cache[key] = node
      self.add_to_head(node)
      self.size += 1
      if self.size > self.capacity:
        node = self.remove_tail()
        self.cache.pop(node.key)
        self.size -= 1

  def move_to_head(self, node):
    self.remove_node(node)
    self.add_to_head(node)

  def remove_node(self, node):
    node.prev.next = node.next
    node.next.prev = node.prev

  def add_to_head(self, node):
    node.next = self.head.next
    node.prev = self.head
    self.head.next = node
    node.next.prev = node

  def remove_tail(self):
    node = self.tail.prev
    self.remove_node(node)
    return node


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

class Node {
  int key;
  int val;
  Node prev;
  Node next;

  Node() {
  }

  Node(int key, int val) {
    this.key = key;
    this.val = val;
  }
}

class LRUCache {
  private Map<Integer, Node> cache = new HashMap<>();
  private Node head = new Node();
  private Node tail = new Node();
  private int capacity;
  private int size;

  public LRUCache(int capacity) {
    this.capacity = capacity;
    head.next = tail;
    tail.prev = head;
  }

  public int get(int key) {
    if (!cache.containsKey(key)) {
      return -1;
    }
    Node node = cache.get(key);
    moveToHead(node);
    return node.val;
  }

  public void put(int key, int value) {
    if (cache.containsKey(key)) {
      Node node = cache.get(key);
      node.val = value;
      moveToHead(node);
    } else {
      Node node = new Node(key, value);
      cache.put(key, node);
      addToHead(node);
      ++size;
      if (size > capacity) {
        node = removeTail();
        cache.remove(node.key);
        --size;
      }
    }
  }

  private void moveToHead(Node node) {
    removeNode(node);
    addToHead(node);
  }

  private void removeNode(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  private void addToHead(Node node) {
    node.next = head.next;
    node.prev = head;
    head.next = node;
    node.next.prev = node;
  }

  private Node removeTail() {
    Node node = tail.prev;
    removeNode(node);
    return node;
  }
}

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

struct Node {
  int k;
  int v;
  Node* prev;
  Node* next;

  Node()
    : k(0)
    , v(0)
    , prev(nullptr)
    , next(nullptr) {}
  Node(int key, int val)
    : k(key)
    , v(val)
    , prev(nullptr)
    , next(nullptr) {}
};

class LRUCache {
public:
  LRUCache(int capacity)
    : cap(capacity)
    , size(0) {
    head = new Node();
    tail = new Node();
    head->next = tail;
    tail->prev = head;
  }

  int get(int key) {
    if (!cache.count(key)) return -1;
    Node* node = cache[key];
    moveToHead(node);
    return node->v;
  }

  void put(int key, int value) {
    if (cache.count(key)) {
      Node* node = cache[key];
      node->v = value;
      moveToHead(node);
    } else {
      Node* node = new Node(key, value);
      cache[key] = node;
      addToHead(node);
      ++size;
      if (size > cap) {
        node = removeTail();
        cache.erase(node->k);
        --size;
      }
    }
  }

private:
  unordered_map<int, Node*> cache;
  Node* head;
  Node* tail;
  int cap;
  int size;

  void moveToHead(Node* node) {
    removeNode(node);
    addToHead(node);
  }

  void removeNode(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
  }

  void addToHead(Node* node) {
    node->next = head->next;
    node->prev = head;
    head->next = node;
    node->next->prev = node;
  }

  Node* removeTail() {
    Node* node = tail->prev;
    removeNode(node);
    return node;
  }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

type node struct {
  key, val   int
  prev, next *node
}

type LRUCache struct {
  capacity   int
  cache    map[int]*node
  head, tail *node
}

func Constructor(capacity int) LRUCache {
  head := new(node)
  tail := new(node)
  head.next = tail
  tail.prev = head
  return LRUCache{
    capacity: capacity,
    cache:  make(map[int]*node, capacity),
    head:   head,
    tail:   tail,
  }
}

func (this *LRUCache) Get(key int) int {
  n, ok := this.cache[key]
  if !ok {
    return -1
  }
  this.moveToFront(n)
  return n.val
}

func (this *LRUCache) Put(key int, value int) {
  n, ok := this.cache[key]
  if ok {
    n.val = value
    this.moveToFront(n)
    return
  }
  if len(this.cache) == this.capacity {
    back := this.tail.prev
    this.remove(back)
    delete(this.cache, back.key)
  }
  n = &node{key: key, val: value}
  this.pushFront(n)
  this.cache[key] = n
}

func (this *LRUCache) moveToFront(n *node) {
  this.remove(n)
  this.pushFront(n)
}

func (this *LRUCache) remove(n *node) {
  n.prev.next = n.next
  n.next.prev = n.prev
  n.prev = nil
  n.next = nil
}

func (this *LRUCache) pushFront(n *node) {
  n.prev = this.head
  n.next = this.head.next
  this.head.next.prev = n
  this.head.next = n
}

class LRUCache {
  capacity: number;
  map: Map<number, number>;
  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key: number): number {
    if (this.map.has(key)) {
      const val = this.map.get(key)!;
      this.map.delete(key);
      this.map.set(key, val);
      return val;
    }
    return -1;
  }

  put(key: number, value: number): void {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

/**
 * 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)
 */

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

struct Node {
  key: i32,
  value: i32,
  prev: Option<Rc<RefCell<Node>>>,
  next: Option<Rc<RefCell<Node>>>,
}

impl Node {
  #[inline]
  fn new(key: i32, value: i32) -> Self {
    Self {
      key,
      value,
      prev: None,
      next: None,
    }
  }
}

struct LRUCache {
  capacity: usize,
  cache: HashMap<i32, Rc<RefCell<Node>>>,
  head: Option<Rc<RefCell<Node>>>,
  tail: Option<Rc<RefCell<Node>>>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl LRUCache {
  fn new(capacity: i32) -> Self {
    Self {
      capacity: capacity as usize,
      cache: HashMap::new(),
      head: None,
      tail: None,
    }
  }

  fn get(&mut self, key: i32) -> i32 {
    match self.cache.get(&key) {
      Some(node) => {
        let node = Rc::clone(node);
        self.remove(&node);
        self.push_front(&node);
        let value = node.borrow().value;
        value
      }
      None => -1,
    }
  }

  fn put(&mut self, key: i32, value: i32) {
    match self.cache.get(&key) {
      Some(node) => {
        let node = Rc::clone(node);
        node.borrow_mut().value = value;
        self.remove(&node);
        self.push_front(&node);
      }
      None => {
        let node = Rc::new(RefCell::new(Node::new(key, value)));
        self.cache.insert(key, Rc::clone(&node));
        self.push_front(&node);
        if self.cache.len() > self.capacity {
          let back_key = self.pop_back().unwrap().borrow().key;
          self.cache.remove(&back_key);
        }
      }
    };
  }

  fn push_front(&mut self, node: &Rc<RefCell<Node>>) {
    match self.head.take() {
      Some(head) => {
        head.borrow_mut().prev = Some(Rc::clone(node));
        node.borrow_mut().prev = None;
        node.borrow_mut().next = Some(head);
        self.head = Some(Rc::clone(node));
      }
      None => {
        self.head = Some(Rc::clone(node));
        self.tail = Some(Rc::clone(node));
      }
    };
  }

  fn remove(&mut self, node: &Rc<RefCell<Node>>) {
    match (node.borrow().prev.as_ref(), node.borrow().next.as_ref()) {
      (None, None) => {
        self.head = None;
        self.tail = None;
      }
      (None, Some(next)) => {
        self.head = Some(Rc::clone(next));
        next.borrow_mut().prev = None;
      }
      (Some(prev), None) => {
        self.tail = Some(Rc::clone(prev));
        prev.borrow_mut().next = None;
      }
      (Some(prev), Some(next)) => {
        next.borrow_mut().prev = Some(Rc::clone(prev));
        prev.borrow_mut().next = Some(Rc::clone(next));
      }
    };
  }

  fn pop_back(&mut self) -> Option<Rc<RefCell<Node>>> {
    match self.tail.take() {
      Some(tail) => {
        self.remove(&tail);
        Some(tail)
      }
      None => None,
    }
  }
}/**
 * Your LRUCache object will be instantiated and called as such:
 * let obj = LRUCache::new(capacity);
 * let ret_1: i32 = obj.get(key);
 * obj.put(key, value);
 */

public class LRUCache {
  class Node {
    public Node Prev;
    public Node Next;
    public int Key;
    public int Val;
  }

  private Node head = new Node();
  private Node tail = new Node();
  private Dictionary<int, Node> cache = new Dictionary<int, Node>();
  private readonly int capacity;
  private int size;

  public LRUCache(int capacity) {
    this.capacity = capacity;
    head.Next = tail;
    tail.Prev = head;
  }

  public int Get(int key) {
    Node node;
    if (cache.TryGetValue(key, out node)) {
      moveToHead(node);
      return node.Val;
    }
    return -1;
  }

  public void Put(int key, int Val) {
    Node node;
    if (cache.TryGetValue(key, out node)) {
      moveToHead(node);
      node.Val = Val;
    } else {
      node = new Node() { Key = key, Val = Val };
      cache.Add(key, node);
      addToHead(node);
      if (++size > capacity) {
        node = removeTail();
        cache.Remove(node.Key);
        --size;
      }
    }
  }

  private void moveToHead(Node node) {
    removeNode(node);
    addToHead(node);
  }

  private void removeNode(Node node) {
    node.Prev.Next = node.Next;
    node.Next.Prev = node.Prev;
  }

  private void addToHead(Node node) {
    node.Next = head.Next;
    node.Prev = head;
    head.Next = node;
    node.Next.Prev = node;
  }

  private Node removeTail() {
    Node node = tail.Prev;
    removeNode(node);
    return node;
  }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.Get(key);
 * obj.Put(key,Val);
 */