力扣hot100 LRU 缓存有序Map

本文介绍: java

Problem: 146. LRU 缓存

文章目录

思路
💖 Code

思路

👨‍🏫 参考题解
在这里插入图片描述

👩‍🏫 参考图解
在这里插入图片描述

💖 Code

⏰ 两操作时间复杂度:

(

)

O(1)

$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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_62123.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。