力扣labuladong——一刷day89
2024-01-09 17:21:03
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
前言
LFU 算法是要复杂很多的,而且经常出现在面试中,因为 LFU 缓存淘汰算法在工程实践中经常使用,也有可能是因为 LRU 算法太简单了。不过话说回来,这种著名的算法的套路都是固定的,关键是由于逻辑较复杂,不容易写出漂亮且没有 bug 的代码
一、力扣460. LFU 缓存
class LFUCache {
private int cap;
private int minFreq;
private HashMap<Integer,Integer> keyToVal;
private HashMap<Integer,Integer> keyToFreq;
private HashMap<Integer,LinkedHashSet<Integer>> freqToKeys;
public LFUCache(int capacity) {
this.cap = capacity;
minFreq = 0;
keyToVal = new HashMap<>();
keyToFreq = new HashMap<>();
freqToKeys = new HashMap<>();
}
public int get(int key) {
if(!keyToVal.containsKey(key)){
return -1;
}
increase(key);
return keyToVal.get(key);
}
public void put(int key, int value) {
if(cap <= 0)return;
if(keyToVal.containsKey(key)){
keyToVal.put(key,value);
increase(key);
return;
}
if(cap <= keyToVal.size()){
removeMinFreq();
}
keyToVal.put(key,value);
keyToFreq.put(key,1);
freqToKeys.putIfAbsent(1,new LinkedHashSet<Integer>());
freqToKeys.get(1).add(key);
this.minFreq = 1;
}
private void increase(int key){
int freq = keyToFreq.get(key);
keyToFreq.put(key,freq+1);
freqToKeys.get(freq).remove(key);
freqToKeys.putIfAbsent(freq+1,new LinkedHashSet<Integer>());
freqToKeys.get(freq+1).add(key);
if(freqToKeys.get(freq).isEmpty()){
freqToKeys.remove(freq);
if(freq == minFreq){
this.minFreq ++;
}
}
}
private void removeMinFreq(){
LinkedHashSet<Integer> list = freqToKeys.get(this.minFreq);
int key = list.iterator().next();
list.remove(key);
if(list.isEmpty()){
freqToKeys.remove(this.minFreq);
}
keyToFreq.remove(key);
keyToVal.remove(key);
}
}
/**
* 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);
*/
文章来源:https://blog.csdn.net/ResNet156/article/details/135482449
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!