專業(yè)網(wǎng)站設(shè)計(jì)招聘信息如何在百度上投放廣告
請(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;}
}