請(qǐng)你為?最不經(jīng)常使用（LFU）緩存算法設(shè)計(jì)并實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)。

實(shí)現(xiàn)?LFUCache?類：

• LFUCache(int capacity)?- 用數(shù)據(jù)結(jié)構(gòu)的容量?capacity?初始化對(duì)象
• int get(int key)?- 如果鍵?key?存在于緩存中，則獲取鍵的值，否則返回?-1?。
• void put(int key, int value)?- 如果鍵?key?已存在，則變更其值；如果鍵不存在，請(qǐng)插入鍵值對(duì)。當(dāng)緩存達(dá)到其容量?capacity?時(shí)，則應(yīng)該在插入新項(xiàng)之前，移除最不經(jīng)常使用的項(xiàng)。在此問(wèn)題中，當(dāng)存在平局（即兩個(gè)或更多個(gè)鍵具有相同使用頻率）時(shí)，應(yīng)該去除?最久未使用?的鍵。

為了確定最不常使用的鍵，可以為緩存中的每個(gè)鍵維護(hù)一個(gè)?使用計(jì)數(shù)器?。使用計(jì)數(shù)最小的鍵是最久未使用的鍵。

當(dāng)一個(gè)鍵首次插入到緩存中時(shí)，它的使用計(jì)數(shù)器被設(shè)置為?1?(由于 put 操作)。對(duì)緩存中的鍵執(zhí)行?get?或?put?操作，使用計(jì)數(shù)器的值將會(huì)遞增。

函數(shù)?get?和?put?必須以?O(1)?的平均時(shí)間復(fù)雜度運(yùn)行。

示例：

輸入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
輸出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]解釋：
// cnt(x) = 鍵 x 的使用計(jì)數(shù)
// cache=[] 將顯示最后一次使用的順序（最左邊的元素是最近的）
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // 返回 1// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 去除鍵 2 ，因?yàn)?cnt(2)=1 ，使用計(jì)數(shù)最小// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // 去除鍵 1 ，1 和 3 的 cnt 相同，但 1 最久未使用// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // 返回 4// cache=[3,4], cnt(4)=2, cnt(3)=3

提示：

• 1 <= capacity?<= 104
• 0 <= key <= 105
• 0 <= value <= 109
• 最多調(diào)用?2 * 105?次?get?和?put?方法

其中?cnt?表示緩存使用的頻率，time?表示緩存的使用時(shí)間，key?和?value?表示緩存的鍵值。

題解：比較直觀的想法就是我們用哈希表?key_table?以鍵?key?為索引存儲(chǔ)緩存，建立一個(gè)平衡二叉樹(shù)?S?來(lái)保持緩存根據(jù)?(cnt，time)?雙關(guān)鍵字。還有一道類似的題LRU:146. LRU 緩存機(jī)制-CSDN博客

code:

class LFUCache {// 緩存容量，時(shí)間戳int capacity, time;Map<Integer, Node> key_table;TreeSet<Node> S;public LFUCache(int capacity) {this.capacity = capacity;this.time = 0;key_table = new HashMap<Integer, Node>();S = new TreeSet<Node>();}public int get(int key) {if (capacity == 0) {return -1;}// 如果哈希表中沒(méi)有鍵 key，返回 -1if (!key_table.containsKey(key)) {return -1;}// 從哈希表中得到舊的緩存Node cache = key_table.get(key);// 從平衡二叉樹(shù)中刪除舊的緩存S.remove(cache);// 將舊緩存更新cache.cnt += 1;cache.time = ++time;// 將新緩存重新放入哈希表和平衡二叉樹(shù)中S.add(cache);key_table.put(key, cache);return cache.value;}public void put(int key, int value) {if (capacity == 0) {return;}if (!key_table.containsKey(key)) {// 如果到達(dá)緩存容量上限if (key_table.size() == capacity) {// 從哈希表和平衡二叉樹(shù)中刪除最近最少使用的緩存key_table.remove(S.first().key);S.remove(S.first());}// 創(chuàng)建新的緩存Node cache = new Node(1, ++time, key, value);// 將新緩存放入哈希表和平衡二叉樹(shù)中key_table.put(key, cache);S.add(cache);} else {// 這里和 get() 函數(shù)類似Node cache = key_table.get(key);S.remove(cache);cache.cnt += 1;cache.time = ++time;cache.value = value;S.add(cache);key_table.put(key, cache);}}
}class Node implements Comparable<Node> {int cnt, time, key, value;Node(int cnt, int time, int key, int value) {this.cnt = cnt;this.time = time;this.key = key;this.value = value;}public boolean equals(Object anObject) {if (this == anObject) {return true;}if (anObject instanceof Node) {Node rhs = (Node) anObject;return this.cnt == rhs.cnt && this.time == rhs.time;}return false;}public int compareTo(Node rhs) {return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt;}public int hashCode() {return cnt * 1000000007 + time;}
}