LeetCode题解460.lfu-cache

题目地址

https://leetcode.com/problems/lfu-cache/

题目描述

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

思路

LFU（Least frequently used) 但内存容量满的情况下，有新的数据进来，需要更多空间的时候，就需要删除被访问频率最少的元素。

举个例子，比如说cache容量是 3，按顺序依次放入 1，2，1，2，1，3， cache已存满 3 个元素 (1，2，3)， 这时如果想放入一个新的元素 4 的时候，就需要腾出一个元素空间。
用 LFU，这里就淘汰 3， 因为 3 的次数只出现依次， 1 和 2 出现的次数都比 3 多。

题中 get 和 put 都是 O(1)的时间复杂度，那么删除和增加都是O(1)，可以想到用双链表，和HashMap，用一个HashMap, nodeMap, 保存当前key，和 node{key, value, frequent} 的映射。
这样get(key)的操作就是O(1). 如果要删除一个元素，那么就需要另一个HashMap，freqMap，保存元素出现次数（frequent）和双链表（DoublyLinkedlist） 映射，
这里双链表存的是frequent相同的元素。每次get或put的时候，frequent+1，然后把node插入到双链表的head node, head.next=node
每次删除freqent最小的双链表的tail node, tail.prev。

用给的例子举例说明：

1. put(1, 1), 
   - 首先查找nodeMap中有没有key=1对应的value，
       没有就新建node(key, value, freq) -> node1(1, 1, 1), 插入 nodeMap，{[1, node1]}
   - 查找freqMap中有没有freq=1 对应的value，
       没有就新建doublylinkedlist(head, tail), 把node1 插入doublylinkedlist head->next = node1.
   如下图，

LeetCode题解460.lfu-cache

2. put(2, 2), 
   - 首先查找nodeMap中有没有key=2对应的value，
       没有就新建node(key, value, freq) -> node2(2, 2, 1), 插入 nodeMap，{[1, node1], [2, node2]}
   - 查找freqMap中有没有freq=1 对应的value，
       没有就新建doublylinkedlist(head, tail), 把node2 插入doublylinkedlist head->next = node2.
   如下图，

LeetCode题解460.lfu-cache

3. get(1), 
   - 首先查找nodeMap中有没有key=1对应的value，nodeMap:{[1, node1], [2, node2]},
       找到node1，把node1 freq+1 -> node1(1,1,2)
   - 更新freqMap，删除freq=1，node1
   - 更新freqMap，插入freq=2，node1
   如下图，

LeetCode题解460.lfu-cache

4. put(3, 3), 
   - 判断cache的capacity，已满，需要淘汰使用次数最少的元素，找到最小的freq=1，删除双链表tail node.prev 
       如果tailnode.prev != null, 删除。然后从nodeMap中删除对应的key。
   - 首先查找nodeMap中有没有key=3对应的value，
       没有就新建node(key, value, freq) -> node3(3, 3, 1), 插入 nodeMap，{[1, node1], [3, node3]}
   - 查找freqMap中有没有freq=1 对应的value，
       没有就新建doublylinkedlist(head, tail), 把node3 插入doublylinkedlist head->next = node3.
   如下图，

LeetCode题解460.lfu-cache

5. get(2) 
   - 查找nodeMap，如果没有对应的key的value，返回 -1。
 
6. get(3)
   - 首先查找nodeMap中有没有key=3对应的value，nodeMap:{[1, node1], [3, node3]},
       找到node3，把node3 freq+1 -> node3(3,3,2)
   - 更新freqMap，删除freq=1，node3
   - 更新freqMap，插入freq=2，node3
   如下图，

LeetCode题解460.lfu-cache

7. put(4, 4), 
   - 判断cache的capacity，已满，需要淘汰使用次数最少的元素，找到最小的freq=1，删除双链表tail node.prev 
       如果tailnode.prev != null, 删除。然后从nodeMap中删除对应的key。
   - 首先查找nodeMap中有没有key=4对应的value，
       没有就新建node(key, value, freq) -> node4(4, 4, 1), 插入 nodeMap，{[4, node4], [3, node3]}
   - 查找freqMap中有没有freq=1 对应的value，
       没有就新建doublylinkedlist(head, tail), 把 node4 插入doublylinkedlist head->next = node4.
   如下图，

LeetCode题解460.lfu-cache

8. get(1) 
   - 查找nodeMap，如果没有对应的key的value，返回 -1。
 
9. get(3)
   - 首先查找nodeMap中有没有key=3对应的value，nodeMap:{[4, node4], [3, node3]},
       找到node3，把node3 freq+1 -> node3(3,3,3)
   - 更新freqMap，删除freq=2，node3
   - 更新freqMap，插入freq=3，node3
   如下图，

LeetCode题解460.lfu-cache

10. get(4)
   - 首先查找nodeMap中有没有key=4对应的value，nodeMap:{[4, node4], [3, node3]},
       找到node4，把node4 freq+1 -> node4(4,4,2)
   - 更新freqMap，删除freq=1，node4
   - 更新freqMap，插入freq=2，node4
   如下图，

LeetCode题解460.lfu-cache

关键点分析

用两个Map分别保存 nodeMap {key, node} 和 freqMap{frequent, DoublyLinkedList}。
实现get 和 put操作都是O(1)的时间复杂度。

可以用Java自带的一些数据结构，比如HashLinkedHashSet，这样就不需要自己自建Node，DoublelyLinkedList。
可以很大程度的缩减代码量。

代码（Java code）

public class LC460LFUCache {
  class Node {
    int key, val, freq;
    Node prev, next;

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

  class DoubleLinkedList {
    private Node head;
    private Node tail;
    private int size;

    DoubleLinkedList() {
      head = new Node(0, 0);
      tail = new Node(0, 0);
      head.next = tail;
      tail.prev = head;
    }

    void add(Node node) {
      head.next.prev = node;
      node.next = head.next;
      node.prev = head;
      head.next = node;
      size++;
    }

    void remove(Node node) {
      node.prev.next = node.next;
      node.next.prev = node.prev;
      size--;
    }

    // always remove last node if last node exists
    Node removeLast() {
      if (size > 0) {
        Node node = tail.prev;
        remove(node);
        return node;
      } else return null;
    }
  }

  // cache capacity
  private int capacity;
  // min frequent
  private int minFreq;
  Map<Integer, Node> nodeMap;
  Map<Integer, DoubleLinkedList> freqMap;
  public LC460LFUCache(int capacity) {
    this.minFreq = 0;
    this.capacity = capacity;
    nodeMap = new HashMap<>();
    freqMap = new HashMap<>();
  }

  public int get(int key) {
    Node node = nodeMap.get(key);
    if (node == null) return -1;
    update(node);
    return node.val;
  }

  public void put(int key, int value) {
    if (capacity == 0) return;
    Node node;
    if (nodeMap.containsKey(key)) {
      node = nodeMap.get(key);
      node.val = value;
      update(node);
    } else {
      node = new Node(key, value);
      nodeMap.put(key, node);
      if (nodeMap.size() == capacity) {
        DoubleLinkedList lastList = freqMap.get(minFreq);
        nodeMap.remove(lastList.removeLast().key);
      }
      minFreq = 1;
      DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());
      newList.add(node);
      freqMap.put(node.freq, newList);
    }
  }

  private void update(Node node) {
    DoubleLinkedList oldList = freqMap.get(node.freq);
    oldList.remove(node);
    if (node.freq == minFreq && oldList.size == 0) minFreq++;
    node.freq++;
    DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());
    newList.add(node);
    freqMap.put(node.freq, newList);
  }
 }

参考（References）

  1. LFU(Least frequently used) Cache
  2. Leetcode discussion mylzsd
  3. Leetcode discussion aaaeeeo
LeetCode题解146.lru-cache

题目地址 https://leetcode.com/problems/lru-cache/description/ 题目描述 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations…

为什么dict.get(key)起作用但dict [key]不起作用？ - python

我正在尝试根据字符串中存在的1将某些数字的二进制字符串分组在一起。这不起作用：s = "0 1 3 7 8 9 11 15" numbers = map(int, s.split()) binaries = [bin(x)[2:].rjust(4, '0') for x in numbers] one_groups =…

LeetCode题解1019.next-greater-node-in-linked-list

题目地址 https://leetcode-cn.com/problems/next-greater-node-in-linked-list/submissions/ 题目描述 给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。 每个节点都可能有下一个更大值（next larg…

LeetCode题解979. 在二叉树中分配硬币

给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。返回使每个结点上只有一枚硬币所需的移动次数。 示例 1：输入：[3,0,0]输出：2解…

隐藏开源应用程序中使用的API密钥 - java

我目前正在开发基于第三方网络API的桌面应用程序，并且已经为其程序注册并获得了两个访问密钥作为回报。但是，如果将这些键作为字符串粘贴到源代码中，那么任何人都可以拉回存储库的内容并轻松地找到它们。到目前为止，关于如何防止这种情况的最好的想法是将它们分别编译成一个类文件，对其进行模糊处理，然后再使用它，以便至少在源代码中不使用纯文本格式。但是，我是否缺少更好，更…

推荐标签：,

腾讯的同事天天给我安利让我看《三体》，说马化腾和雷军也在…

腾讯的同事天天给我安利让我看《三体》，说马化腾和雷军也在看。自己强行看了两个月，全部给看完了。感觉这文笔也就我读初中的水平……而且写着国内的一些情况，外国人能理解吗？这书为什么会这么火？这水平我也可以去写呀[笑哭][笑哭][笑哭] 招商银行员工：可以写赶紧写一个啊，能拿科幻文学雨果奖。 包清白：哦 楼主：pei ！tui ！你也配姓龙 楼主：@赵龙王 呵呵 […]