力扣hot100 LRU 缓存 有序Map

Problem: 146. LRU 缓存

思路

👨‍🏫 参考题解

👩‍🏫 参考图解

💖 Code

⏰ 两操作 时间复杂度: $O(1)$

class LRUCache
{
int cap;
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();

public LRUCache(int capacity)
{
this.cap = capacity;// 初始化容量
}

public int get(int key)
{
if (!cache.containsKey(key))// 缓存不存在返回 -1
return -1;
makeRecntly(key);// 更新访问时间
return cache.get(key);
}

//让 key 重新入 缓存 
private void makeRecntly(int key)
{
int val = cache.get(key);
cache.remove(key);
cache.put(key, val);
}

public void put(int key, int val)
{
if (cache.containsKey(key))
{
cache.put(key, val);// 更新 cache 的值，已存在则不增加容量
makeRecntly(key);
return;
}
if (cache.size() >= this.cap)// 其实 == 就要删除旧元素了，先删后加
{
// 用迭代器拿出 keySet 中的第一个 key
int old = cache.keySet().iterator().next();
cache.remove(old);// 删除最旧的数据
}
cache.put(key, val);
}
}

原文地址：https://blog.csdn.net/lt6666678/article/details/135838250

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！