【LinkedHashMap】146. LRU 缓存

146. LRU 缓存

解题思路

• 与普通的 HashMap 不同，LinkedHashMap 会保持元素的有序性。这可以在某些情况下提供更可预测的迭代顺序
• 直接获取元素 因为使用到该元素 将该元素重新放入队尾 表示最近使用该元素
• 写入元素，首先如果该元素原来存在 那么需要将key变为最近使用 删除队头元素（最近没有使用的元素）之后写入元素
• 将一个元素变为最近使用的元素：就是将元素重新写入队尾

class LRUCache {int cap;// 与普通的 HashMap 不同，LinkedHashMap 会保持元素的有序性。这可以在某些情况下提供更可预测的迭代顺序LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();public LRUCache(int capacity) {this.cap = capacity;// 初始化容器}public int get(int key) {if(!cache.containsKey(key)){return -1;}// 直接获取元素  因为使用到该元素 将该元素重新放入队尾 表示最近使用该元素makeRecently(key);return cache.get(key);}public void put(int key, int value) {if(cache.containsKey(key)){// 修改key的值cache.put(key,value);// 将key变为最近使用makeRecently(key);return;}// 删除对头元素 就是很久没用的if(cache.size() >= this.cap){// 链表头部就是最久未使用的keyint oldestKey = cache.keySet().iterator().next();cache.remove(oldestKey);}cache.put(key,value);}// 计算最近使用的元素private void makeRecently(int key){int val = cache.get(key);// 获取元素// 移除keycache.remove(key);// 因为现在使用到该元素  所以将该元素插入队列尾部cache.put(key,val);}
}/*** 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);*/