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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <map>
using namespace std;

class LFUCache {
  struct ListNode {
    int freq;
    int key;
    int value;
    ListNode* prev;
    ListNode* next;
    ListNode() : key(-1), value(-1), freq(0), prev(nullptr), next(nullptr) {}
    ListNode(int k, int v) : key(k), value(v), freq(1), prev(nullptr), next(nullptr) {}
  };
  struct FreqList {
    explicit FreqList(int f) : freq(f) {
      head = new ListNode;
      tail = new ListNode;

      head->next = tail;
      tail->prev = head;
    }

    void addNodeToHead(ListNode* node) {
      node->next = head->next;
      head->next->prev = node;
      node->prev = head;
      head->next = node;
    }

    void deleteNode(ListNode* node) {
      node->next->prev = node->prev;
      node->prev->next = node->next;
    }

    bool empty() const {
      return head->next == tail;
    }

    int freq;
    ListNode* head;
    ListNode* tail;
  };
public:
  LFUCache(int k) : capacity_(k), min_freq_(0) {}

  int get(int key) {
    if (hash_.count(key) == 0) {  // 不在缓存中
      return -1;
    }
    auto node = hash_[key];
    deleteNode(node);
    node->freq++;
    if (freq_map_[min_freq_]->empty()) {
      ++min_freq_;
    }
    addNodeToHead(node);
    return node->value;
  }

  void put(int key, int value) {
    if (capacity_ == 0) return; // 缓存容量为0，直接返回
    if (get(key) != -1) { // 如果在缓存中
      hash_[key]->value = value;
      return;
    }
    if (hash_.size() >= capacity_) {  // 缓存空间不足
      deleteTailNode();
    }
    auto node = new ListNode(key, value);
    min_freq_ = 1;
    addNodeToHead(node);
    hash_[key] = node;
  }

private:
  void deleteNode(ListNode* node) {
    auto lst = freq_map_[node->freq];
    lst->deleteNode(node);
  }

  void addNodeToHead(ListNode* node) {
    if (freq_map_.count(node->freq) == 0) {
      freq_map_[node->freq] = new FreqList(node->freq);
    }
    auto lst = freq_map_[node->freq];
    lst->addNodeToHead(node);
  }

  void deleteTailNode() {
    auto node = freq_map_[min_freq_]->tail->prev;
    deleteNode(node);
    hash_.erase(node->key);
  }
private:
  int capacity_;  // 缓存大小
  int min_freq_;  // 最小使用频率

  unordered_map<int/*key*/, ListNode*> hash_;
  unordered_map<int/*freq*/, FreqList*> freq_map_;
};

class Solution {
public:
  /**
   * lfu design
   * @param operators int整型vector<vector<>> ops
   * @param k int整型 the k
   * @return int整型vector
   */
  vector<int> LFU(vector<vector<int> >& operators, int k) {
    vector<int> ans;
    auto cache = new LFUCache(k);
    for (const auto& opt : operators) {
      if (opt[0] == 1) {
        cache->put(opt[1], opt[2]);
      } else {
        ans.emplace_back(cache->get(opt[1]));
      }
    }
    return ans;
  }
};

int main()
{
  Solution s;
  vector<vector<int>> vec{ {1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {1, 2, 4}, {1, 3, 5}, {2, 2}, {1, 4, 4}, {2, 1} };
  auto ans = s.LFU(vec, 3);
  return 0;
}