1 题目

Leetcode 题目：LRU缓存机制

早有耳闻，从来没有看过代码，在面试中又翻车了。实际上代码很简单也很好理解：

• 手动构建和管理双向链表，链表维护着 capacity 和 size；

• head 始终是最新访问的节点；

• 当 size 超过 capacity 的时候，删除 tail 节点；

• 维护一个哈希表，可以 O(1) 访问到目标节点；

2 代码

#include <unordered_map>

struct Node {
  int key;
  int value;
  Node* pre;
  Node* next;
  Node(int k, int v) : key(k), value(v), pre(nullptr), next(nullptr) {}
};

class LRUCache {
 public:
  LRUCache(int capacity) : capacity_(capacity), size_(0) {
    head_ = new Node(0, 0);
    tail_ = new Node(0, 0);
    head_->next = tail_;
    tail_->pre = head_;
  }

  int get(int key) {
    if (cache_.find(key) == cache_.end()) return -1;

    move_to_head(cache_[key]);
    return cache_[key]->value;
  }

  void put (int key, int value) {
    if (cache_.find(key) == cache_.end()) {
      Node* node = new Node(key, value);
      cache_[key] = node;
      add_to_head(node);
      ++size_;
      if (size_ > capacity_) {
        Node* removed_node = remove_tail();
        cache_.erase(removed_node->key);
        delete removed_node;
        --size_;
      }
    } else {
      cache_[key]->value = value;
      move_to_head(cache_[key]);
    }
  }

  void add_to_head(Node* node) {
    node->pre = head_;
    node->next = head_->next;
    head_->next->pre = node;
    head_->next = node;
  }

  void remove_node(Node* node) {
    node->pre->next = node->next;
    node->next->pre = node->pre;
  }

  void move_to_head(Node* node) {
    remove_node(node);
    add_to_head(node);
  }

  Node* remove_tail() {
    Node* tail_node = tail_->pre;
    remove_node(tail_node);
    return tail_node;
  }

 private:
  int capacity_;
  int size_;
  std::unordered_map<int, Node*> cache_;
  Node* head_;
  Node* tail_;
};