# leetcode460. 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.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

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(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(3);       // returns 3
cache.get(4);       // returns 4```

## 思路和代码

1. key-val映射，满足缓存的基本要求
2. key-count映射，记录当前的key最近被访问的次数

```HashMap<Integer, Integer> vals;
HashMap<Integer, Integer> counts;
int cap;
int min = -1;
public LFUCache(int capacity) {
cap = capacity;
vals = new HashMap<>();
counts = new HashMap<>();
lists = new HashMap<>();
}

public int get(int key) {
if(!vals.containsKey(key)) {
return -1;
}
int count = counts.get(key);
counts.put(key, count+1);
lists.get(count).remove(key);
if(count==min && lists.get(count).size()==0) {
min++;
}
if(!lists.containsKey(count+1)) {
}
return vals.get(key);
}

public void put(int key, int value) {
if(cap<=0) {
return;
}
if(vals.containsKey(key)) {
vals.put(key, value);
get(key);
return;
}
if(vals.size() >= cap) {
int evit = lists.get(min).iterator().next();
lists.get(min).remove(evit);
vals.remove(evit);
}
vals.put(key, value);
counts.put(key, 1);
min = 1;
}```

0 条评论

• ### leetcode502. IPO

Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

• ### leetcode477. Total Hamming Distance

计算N个数字之间的汉明码距离之和。 汉明码是指两个数字的二进制表示形式中，在对应位置上值不同的数量总和。如2和4，4的二进制表达式为100， 2的二进制表达式0...

• ### leetcode508. Most Frequent Subtree Sum

Given the root of a tree, you are asked to find the most frequent subtree sum. T...

• ### Top 10 Features of Angular 8

In the first quarter of 2019, Google launched Angular 8 which was much awaited b...

• ### 学习FDD系统中的 CSI 恢复(cs IT)

我们提出了一种创新的机器学习技术，以解决频率划分复式系统基站的渠道采集问题。在此背景下，基站根据移动终端有限的下行链路状态信息反馈，在下行链路频率范围内重建全信...

• ### MySQL数据同步【双主热备】

应用环境 数据库服务器  虚拟机  OS:  Windows Server 2003  1.数据库服务器242 IP:192.168.206.242   2...

• ### 数学--数论--HDU 2104 丢手绢（离散数学 mod N+ 剩余类 生成元）+（最大公约数）

The Children’s Day has passed for some days .Has you remembered something happen...

• ### Python Elasticsearch API操作ES集群

关键是DSL语法的编写涉及查询与聚合可以通过kibana的visualize或者devtool先测试出正确语法，然后结合python对列表、字典、除法、字符串等...