題目：
運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制伴找。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 抖誉。
獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中袒炉，則獲取密鑰的值（總是正數(shù)），否則返回 -1夺艰。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在郁副，則寫入其數(shù)據(jù)值。當(dāng)緩存容量達(dá)到上限時(shí)愕贡，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值固以，從而為新的數(shù)據(jù)值留出空間。
示例:
LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會使得密鑰 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會使得密鑰 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
這種設(shè)計(jì)題的思路是找到合適的數(shù)據(jù)結(jié)構(gòu)去做事情，最想到的是哈希表和雙向鏈表遍略，那么想到的就是HashMap和LinkedList。而且時(shí)間復(fù)雜度很低應(yīng)該是O(1)蕾久。
那么有沒有更懶一點(diǎn)的方式呢僧著？也有盹愚，用LinkedHashMap霞篡，畢竟我的原則是有就用污淋，JDK里的結(jié)構(gòu)和方法設(shè)計(jì)出來不就是為了給咱用的嗎礁鲁？仅醇？？
這題想解決不難叶摄，具體的看代碼即可~
class LRUCache {
int cap;
LinkedHashMap<Integer,Integer> cache;
public LRUCache(int capacity) {
this.cap = capacity;
cache = new LinkedHashMap<>(capacity);
}
public int get(int key) {
Integer value = cache.getOrDefault(key, -1);
if (value!=-1){
// 如果有值会傲，則放后面
cache.remove(key);
cache.put(key,value);
}
return value;
}
public void put(int key, int value) {
if (cache.get(key)!=null){
//如果有value值就先刪除cache中的key，再放隊(duì)尾
cache.remove(key);
} else if (cache.size()==cap) {
//滿了就優(yōu)先刪除最首的元素，再放隊(duì)尾
cache.remove(cache.entrySet().iterator().next().getKey());
}
// 放隊(duì)尾
cache.put(key,value);
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
