网络营销站点推广的方法,苍南县龙港哪里有做网站,龙岗区,传媒公司排行460. LFU 缓存
解题思路
get操作 返回key对应的val 然后增加对应的freq插入操作 如果key已经存在 直接进行更新 如果不存在 但是容器已经满了 直接进行删除freq最小的Key 之后进行插入 class LFUCache {// key到 val的映射 KVHashMapInteger,Integer keyToVal;// …460. LFU 缓存
解题思路
get操作 返回key对应的val 然后增加对应的freq插入操作 如果key已经存在 直接进行更新 如果不存在 但是容器已经满了 直接进行删除freq最小的Key 之后进行插入 class LFUCache {// key到 val的映射 KVHashMapInteger,Integer keyToVal;// 从key到freq的映射 KFHashMapInteger,Integer keyToFreq;// 一个频率对应多个 key 舍弃最久未使用的 FKHashMapInteger,LinkedHashSetInteger freqToKeys;// 记录最小的频率int minFreq;// 记录LFU 缓存的最大容量int cap;public LFUCache(int capacity) {keyToVal new HashMap();keyToFreq new HashMap();freqToKeys new HashMap();this.cap capacity;this.minFreq 0;}// 返回对应key的val 然后增加对应的freqpublic int get(int key) {if(!keyToVal.containsKey(key)){return -1;// 返回-1 说明没找到}// 增加key对应的freq 1 因为查找操作一次increaseFreq(key);return keyToVal.get(key);// 找到val}public void put(int key, int value) {// 如果key 已经存在直接更新if(this.cap 0){return;}if(keyToFreq.containsKey(key)){// 修改val即可keyToVal.put(key,value);// 对应的freq加一increaseFreq(key);return;}// key 不存在 需要插入 如果容量没有满 直接插入 如果已满 直接删除 freq最小的keyif(this.cap keyToVal.size()){removeMinFreqKey();// 删除freq最小的key}keyToVal.put(key,value);keyToFreq.put(key,1);// 插入KF 表 一种freq对应多种keyfreqToKeys.putIfAbsent(1,new LinkedHashSet());freqToKeys.get(1).add(key);// 获取频率 添加一种key// 插入新的key之后最小的freq肯定是1this.minFreq 1;}private void removeMinFreqKey(){// freq最小的key列表 通过 FKLinkedHashSetInteger keyList freqToKeys.get(this.minFreq);// 获取所有的key// 最先被插入的key就是该被淘汰的keyint deleteKey keyList.iterator().next();// 更新FK keyList.remove(deleteKey);if(keyList.isEmpty()){// 如果key列表是空的 说明都没有了直接删除freqfreqToKeys.remove(this.minFreq);}// 更新KVkeyToVal.remove(deleteKey);// 更新KFkeyToFreq.remove(deleteKey);}private void increaseFreq(int key){int freq keyToFreq.get(key);// 更新 KFkeyToFreq.put(key,freq 1);// 更新FK// 将key 从freq对应的列表中删除freqToKeys.get(freq).remove(key);// 将key加入freq 1 对应的列表freqToKeys.putIfAbsent(freq 1,new LinkedHashSet());// 创建新的freqToKeys.get(freq 1).add(key);// 如果对应的列表空if(freqToKeys.get(freq).isEmpty()){freqToKeys.remove(freq);if(freq this.minFreq){this.minFreq;}}}
}/*** 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);*/
