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思路： 自定义 node class，双链表，class，双hashmap
node class：包括 key，value和这个node的freq， next， prev指针
双链表：支持 add，remove， remove last
用一个hashmap nodeMap建立 key和node的mapping，node是 map的value
用另一个hashmap freqMap 建立freq和node list的映射，freq是key， 具有同样freq的node list
LFU 更新策略
1.get(); nodeMap 根据这个key get到的node如果是空，返回-1， 如果不为空 返回node的key，并更新这个node的频率
2. put(): 如果nodeMAP包含这个key，那么就更新对应node的值，并且更新node频率； 如果不包含这个key，那么要新建一个node，加到nodeMap里，同时判断 如果这时候没有空间了，就把freqMap 里freq min那一个list的最后一个删掉，并且如果最后一个node不是null，删掉他在nodeMap的entry，size--， 如果有空间，直接加到对应的lis里。 min 设为1
update node freq
找到node原来的freq list，从中删除，如果这个freq是1，删掉后list为空了，那么更新最小频率
把他加到对应频率的fre list里，如果没哟 就新建
class LFUCache {
class Node{
int key, val, freq;
Node next, prev;
public Node(int key, int val){
this.key = key;
this.val = val;
this.freq = 1;
next = null;
prev = null;
}
}
class DLList{
Node header, tail;
int size;
public DLList(){
header = new Node(0,0);
tail = new Node(0,0);
size = 0;
header.next = tail;
tail.prev = header;
}
public void add(Node node){
node.next = header.next;
node.prev = header;
header.next.prev = node;
header.next = node;
size++;
}
public void remove(Node node){
if(size == 0)
return;
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = null;
node.prev = null;
size--;
}
public Node removeLast(){
if(tail.prev == header || size ==0)
return null;
Node node = tail.prev;
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = null;
node.prev = null;
size--;
return node;
}
}
private Map<Integer,Node> nodeMap;
private Map<Integer,DLList> freqMap;
private int size, capacity, min;
public LFUCache(int capacity) {
nodeMap = new HashMap<>();
freqMap = new HashMap<>();
this.size = 0;
this.capacity = capacity;
this.min = 0;
}
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 = null;
if(nodeMap.containsKey(key)){
node = nodeMap.get(key);
node.val = value;
update(node);
}else{
node = new Node(key, value);
nodeMap.put(key, node);
if(size == capacity){
DLList tmpList = freqMap.get(min);
Node lastNode = tmpList.removeLast();
if(lastNode != null)
nodeMap.remove(lastNode.key);
size--;
}
size++;
min = 1;
DLList oldList = freqMap.getOrDefault(node.freq,new DLList());
oldList.add(node);
freqMap.put(node.freq,oldList);
}
}
public void update(Node node){
DLList oldList = freqMap.get(node.freq);
oldList.remove(node);
if(node.freq == 1 && oldList.size == 0) min++;
node.freq++;
DLList newList = freqMap.getOrDefault(node.freq,new DLList());
newList.add(node);
freqMap.put(node.freq, newList);
}
}
/**
* 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);
*/Last updated