原题
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
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
解法
思想
如果不限制 O(1) 时间复杂度，用链表就能完成了，但是限制时间复杂度就需要解决链表顺序访问的问题。
可以通过哈希表+链表解决，如果看过LinkedHashMap的源码就知道，LinkedHashMap本身就可以拓展成LRU缓存，这个我也在LinkedHashMap源码分析中提过。
代码
class LRUCache extends LinkedHashMap<Integer,Integer>{
private int capacity;
public LRUCache(int capacity) {
// 初始大小设为1024，避免leetcode上执行扩容带来的时间损耗
// 最后一个参数设为true，代表按访问顺序连接
super(1024,0.75f,true);
this.capacity = capacity;
}
// 重写该方法，可以在每一次添加元素后判断要不要移除队列首部的元素
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > capacity;
}
public int get(int key) {
return getOrDefault(key,-1);
}
public void put(int key, int value) {
super.put(key,value);
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode146-lru%e7%bc%93%e5%ad%98%e6%9c%ba%e5%88%b6/
相关推荐
-
leetcode1103-分糖果II
原题 排排坐，分糖果。 我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类...
-
leetcode79-单词搜索
原题 给定一个二维网格和一个单词，找出该单词是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格...
-
leetcode496-下一个更大元素I
原题 给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums...
-
leetcode1413-逐步求和得到正数的最小值
原题 给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。 你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums...
-
leetcode167-两数之和II-输入有序数组
原题 给定一个已按照 升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2，其中index1必须小于index2。 说明...
-
leetcode4-寻找两个有序数组的中位数
这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m...
-
leetcode100-相同的树
原题 给定两个二叉树，编写一个函数来检验它们是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 ...
-
leetcode21-合并两个有序链表
原题 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入： 1->2->4, 1->3->4 输出： 1->1->2->3-...
-
力扣杯春季个人赛-剧情触发时间
这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?，虽然大家的通过率也不咋地。。 最后排名 我记录一道做出来的题吧，这道题是一道中等题，通过率如下，虽然题目不难，但由于时...
-
leetcode151-翻转字符串里的单词
原题 给定一个字符串，逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: “ he...
