题解 | #设计LRU缓存结构#

使用双向链表和哈希表实现 O(1) 时间复杂度

class Solution {
  public:
    Solution(int capacity) : lru(capacity), cap(capacity) {
    }

    int get(int key) {
      if (hash.count(key)) {
        auto tmp = *(hash[key]);
        lru.erase(hash[key]);
        lru.push_front(tmp);
        hash[key] = lru.begin();
        return tmp.second;
      } 

      return -1;
    }

    void set(int key, int value){
      if (hash.count(key)) {
        lru.erase(hash[key]);
      }

      if (lru.size() >= cap) {
        auto tmp = lru.back();
        hash.erase(tmp.first);
        lru.pop_back();
      }

      lru.push_front({key, value});
      hash[key] = lru.begin();
    }
  private:
    int cap;
    //  使用to_string返回转换（由平台内部实现）
    std::list<std::pair<int, int>> lru;
    //  键映射到指定的迭代器
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> hash;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */

更新写法

class Solution {
  public:
    Solution(int capacity) {
      cap = capacity;
    }

    int get(int key) {
      if (hash.count(key)) {
        int val = hash[key]->second;
        lru.erase(hash[key]);
        lru.push_front({key, val});
        hash[key] = lru.begin();
        return val;
      } else {
        return -1;
      }
    }

    void set(int key, int value){
      if (hash.count(key)) {
        lru.erase(hash[key]);
      } else if (lru.size() >= cap) {
        hash.erase(lru.back().first);
        lru.pop_back();
      } 

      lru.push_front({key, value});
      hash[key] = lru.begin();
    }
  private:
    int cap;
    std::list<std::pair<int, int>> lru;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> hash;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */