【每日一题Day337】LC460LFU 缓存 | 双链表+哈希表

LFU 缓存【LC460】

请你为 最不经常使用LFU缓存算法设计并实现数据结构。

实现 LFUCache 类

• LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
• int get(int key) - 如果键 key 存在于缓存中则获取键的值否则返回 -1 。
• void put(int key, int value) - 如果键 key 已存在则变更其值如果键不存在请插入键值对。当缓存达到其容量 capacity 时则应该在插入新项之前移除最不经常使用的项。在此问题中当存在平局即两个或更多个键具有相同使用频率时应该去除 最近最久未使用 的键。

为了确定最不常使用的键可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

• 错误答案

  class LFUCache {
      // 注意PriorityQueue要插入(删除)数据顺序会发生改变如果仅仅是修改已经稳定队列的值或内容而不进行插入或者删除那么这个顺序是不会变的。
      // 使用Node存储每个key对应的value以及该key的操作次数、最近操作时间
      // 小顶堆存储每个元素 以使用次数及最近使用时间降序排序
      int capacity;
      PriorityQueue<Node> pq;
      Map<Integer, Node> map;
      int time;
      public LFUCache(int capacity) {
          this.capacity = capacity;
          this.pq = new PriorityQueue<>((o1, o2) -> o1.freq == o2.freq ? o1.time - o2.time : o1.freq - o2.freq);
          this.map = new HashMap<>();
          this.time = 0;
      }
      
      public int get(int key) {
          if (!map.containsKey(key)) return -1;
          Node node = map.get(key);
          node.freq += 1;
          node.time = time++;
          return node.val;
      }
      
      public void put(int key, int value) {
          if (map.containsKey(key)){
              Node node = map.get(key);
              node.val = value;
              node.freq += 1;
              node.time = time++;
          }else{
              Node node = new Node(key, value, time++, 1);
              if (pq.size() == capacity){
                  Node node1 = pq.poll();
                  map.remove(node1.key);
              }
              pq.add(node);
              map.put(key, node);
          }
      }
  }
  class Node{
      int key;
      int val;
      int time;
      int freq;
      public Node(){
          this.freq = 0;
      }
      public Node(int key, int val, int time, int freq){
          this.key = key;
          this.val = val;
          this.time = time;
          this.freq = freq;
      }
  }
  
  /**
   * Your LFUCache object will be instantiated and called as such:
   * LFUCache obj = new LFUCache(capacity);
   * int param_1 = obj.get(key);
   * obj.put(key,value);
   */
  

• 思路

  • LFU和LRU不同之处
    • LRU移除元素时移除最近最久未使用的元素
    • LFU移除元素时移除使用频率最少的最近最久未使用的元素
  • 因此LFU实现可以仿照LRU使用哈希表记录每个频率下的节点相同频率下的各个节点以双向链表的形式组织
    • 每次移除元素时移除频率最小的最久未使用的元素
    • 每操作一次元素需要修改节点频率至相应链表
    • 链表的首部存放最新操作的元素
    • 为了快速找到某个节点在链表中的位置可以使用哈希表存储每个key对应的节点
    • 为了快速找到最小频率维护一个int变量记录最小频率

• 实现

  class LFUCache {
      private static class Node {
          int key, value, freq = 1; // 新书只读了一次
          Node prev, next;
  
          Node(int key, int value) {
              this.key = key;
              this.value = value;
          }
      }
  
      private final int capacity;
      private final Map<Integer, Node> keyToNode = new HashMap<>();
      private final Map<Integer, Node> freqToDummy = new HashMap<>();
      private int minFreq;
  
      public LFUCache(int capacity) {
          this.capacity = capacity;
      }
  
      public int get(int key) {
          Node node = getNode(key);
          return node != null ? node.value : -1;
      }
  
      public void put(int key, int value) {
          Node node = getNode(key);
          if (node != null) { // 有这本书
              node.value = value; // 更新 value
              return;
          }
          if (keyToNode.size() == capacity) { // 书太多了
              Node dummy = freqToDummy.get(minFreq);
              Node backNode = dummy.prev; // 最左边那摞书的最下面的书
              keyToNode.remove(backNode.key);
              remove(backNode); // 移除
              if (dummy.prev == dummy) { // 这摞书是空的
                  freqToDummy.remove(minFreq); // 移除空链表
              }
          }
          node = new Node(key, value); // 新书
          keyToNode.put(key, node);
          pushFront(1, node); // 放在「看过 1 次」的最上面
          minFreq = 1;
      }
  
      private Node getNode(int key) {
          if (!keyToNode.containsKey(key)) { // 没有这本书
              return null;
          }
          Node node = keyToNode.get(key); // 有这本书
          remove(node); // 把这本书抽出来
          Node dummy = freqToDummy.get(node.freq);
          if (dummy.prev == dummy) { // 抽出来后这摞书是空的
              freqToDummy.remove(node.freq); // 移除空链表
              if (minFreq == node.freq) { // 这摞书是最左边的
                  minFreq++;
              }
          }
          pushFront(++node.freq, node); // 放在右边这摞书的最上面
          return node;
      }
  
      // 创建一个新的双向链表
      private Node newList() {
          Node dummy = new Node(0, 0); // 哨兵节点
          dummy.prev = dummy;
          dummy.next = dummy;
          return dummy;
      }
  
      // 在链表头添加一个节点把一本书放在最上面
      private void pushFront(int freq, Node x) {
          Node dummy = freqToDummy.computeIfAbsent(freq, k -> newList());
          x.prev = dummy;
          x.next = dummy.next;
          x.prev.next = x;
          x.next.prev = x;
      }
  
      // 删除一个节点抽出一本书
      private void remove(Node x) {
          x.prev.next = x.next;
          x.next.prev = x.prev;
      }
  }