人人摸人人摸人人,亚洲三高青在线观看免费,青青草免费在线观看,日韩AV在线动漫国产,91逼特逼,亚洲日韩一级精品片在线播放,日本五十路熟女视频,亚洲黄色电影在线

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?LRU 緩存機(jī)制，我們先來看題面：

https://leetcode-cn.com/problems/lru-cache/

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

題意

運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計和實(shí)現(xiàn)一個? LRU (最近最少使用) 緩存機(jī)制。

實(shí)現(xiàn) LRUCache 類：

LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

進(jìn)階：你是否可以在 O(1) 時間復(fù)雜度內(nèi)完成這兩種操作？

樣例

輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋
LRUCache lRUCache = new?LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 該操作會使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

解題

https://blog.csdn.net/qq_41231926/article/details/86173740

思路：用LinkedHashMap實(shí)現(xiàn)

注意點(diǎn)，由于LinkedHashMap默認(rèn)的LRU算法是根據(jù)鍵的進(jìn)入順序來定的，對于更新值和獲取值的操作是忽視的，因此在更新值和獲取值時我們需要先把原值刪除再添進(jìn)一個新值，這樣實(shí)現(xiàn)的LRU算法才是題目所述的LRU算法。

LinkedHashMap內(nèi)部的結(jié)構(gòu)其實(shí)就是HashMap的基礎(chǔ)上多個雙向指針，下面給出LinkedHashMap源碼中Entry的定義：

/**
?* HashMap.Node subclass for normal LinkedHashMap entries.
?*/
static?class?Entry extends?HashMap.Node {
?????Entry before, after;
?????Entry(int?hash, K key, V value, Node next) {
??????????super(hash, key, value, next);
?????}
}

put和get操作的時間復(fù)雜度均是O(1)。空間復(fù)雜度是O(n)，其中n為緩存容量。

class?LRUCache?{
?
????private?int?capacity;
????private?LRULinkedHashMap lruLinkedHashMap = new?LRULinkedHashMap<>();
?
????private?class?LRULinkedHashMap<K, V> extends?LinkedHashMap<K, V> {
????????@Override
????????protected?boolean?removeEldestEntry(Map.Entry eldest)?{
????????????if?(size() > capacity) {
????????????????return?true;
????????????} else?{
????????????????return?false;
????????????}
????????}
????}
?
????public?LRUCache(int?capacity)?{
????????this.capacity = capacity;
????}
?
????public?int?get(int?key)?{
????????Integer value = lruLinkedHashMap.get(key);
????????if?(null?== value) {
????????????return?-1;
????????}
????????lruLinkedHashMap.remove(key);
????????lruLinkedHashMap.put(key, value);
????????return?value;
????}
?
????public?void?put(int?key, int?value)?{
????????if?(lruLinkedHashMap.containsKey(key)) {
????????????lruLinkedHashMap.remove(key);
????????}
????????lruLinkedHashMap.put(key, value);
????}
?
}

好了，今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)個在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動力。

上期推文：

LeetCode1-140題匯總，希望對你有點(diǎn)幫助！

LeetCode刷題實(shí)戰(zhàn)141：環(huán)形鏈表

LeetCode刷題實(shí)戰(zhàn)142：環(huán)形鏈表 II

LeetCode刷題實(shí)戰(zhàn)143：重排鏈表

LeetCode刷題實(shí)戰(zhàn)144：二叉樹的前序遍歷

LeetCode刷題實(shí)戰(zhàn)145：二叉樹的后序遍歷

?LeetCode刷題實(shí)戰(zhàn)146：LRU 緩存機(jī)制

題意

解題