[LeetCode146] LRU 缓存机制(LinkedHashMap 实现)
2021/12/8 23:48:30
本文主要是介绍[LeetCode146] LRU 缓存机制(LinkedHashMap 实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
解法
package com.wangxiaohu; import java.util.LinkedHashMap; public class LeetCode146 { /** * 题目:146. LRU 缓存机制 * leetcode:https://leetcode-cn.com/problems/lru-cache/ * 实现思路:哈希链表 * LRU 缓存机制特点: * 1、查询快(哈希表的特点) * 2、插入快(链表特点) * 3、删除快(链表特点) * 4、数据有顺序(链表特点) * 时间复杂度:O(1) */ class LRUCache { private int size; LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>(); public LRUCache(int capacity) { this.size = capacity; } public int get(int key) { if (!cache.containsKey(key)) { return -1; } // 将 key 变为最近使用 makeKeyRecently(key); return cache.get(key); } public void put(int key, int value) { if (cache.containsKey(key)) { // 修改 key 的值 cache.put(key, value); // 将 key 变为最近使用 makeKeyRecently(key); return; } // 如果不存在 // 缓存满了 if (cache.size() >= this.size) { // 链表头部就是最久未使用的 key int oldestKey = cache.keySet().iterator().next(); cache.remove(oldestKey); } // 将新的 key 添加链表尾部 cache.put(key, value); } private void makeKeyRecently(int key) { int val = cache.get(key); // 删除 key,重新插入到队尾 cache.remove(key); cache.put(key, val); } } }
这篇关于[LeetCode146] LRU 缓存机制(LinkedHashMap 实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享