当前位置：首页 > 编程日记 > 正文

LeetCode实战：LRU缓存机制

编程日记 2024-09-27 14:10:00

背景

为什么你要加入一个技术团队？
如何加入 LSGO 软件技术团队？
我是如何组织“算法刻意练习活动”的？
为什么要求团队的学生们写技术Blog

题目英文

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:

Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

题目中文

运用你所掌握的数据结构，设计和实现一个 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

算法实现

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

利用单链表的方式：

public class LRUCache
{private readonly int _length;private readonly List<KeyValuePair<int, int>> _lst;public LRUCache(int capacity){_length = capacity;_lst = new List<KeyValuePair<int, int>>();}private int GetIndex(int key){for (int i=0,len=_lst.Count;i<len;i++){if (_lst[i].Key == key){return i;}}return -1;}public int Get(int key){int index = GetIndex(key);if (index!=-1){int val = _lst[index].Value;_lst.RemoveAt(index);_lst.Add(new KeyValuePair<int, int>(key, val));return val;}return -1;}public void Put(int key, int value){int index = GetIndex(key);if (index!=-1){_lst.RemoveAt(index);}else if (_lst.Count == _length){_lst.RemoveAt(0);}_lst.Add(new KeyValuePair<int, int>(key, value));}
}/*** 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);*/

利用字典（哈希）+单链表的方式：

public class LRUCache
{private readonly List<int> _keys;private readonly Dictionary<int, int> _dict;public LRUCache(int capacity){_keys = new List<int>(capacity);_dict = new Dictionary<int, int>(capacity);}public int Get(int key){if (_dict.ContainsKey(key)){_keys.Remove(key);_keys.Add(key);return _dict[key];}return -1;}public void Put(int key, int value){if (_dict.ContainsKey(key)){_dict.Remove(key);_keys.Remove(key);}else if (_keys.Count == _keys.Capacity){_dict.Remove(_keys[0]);_keys.RemoveAt(0);}_keys.Add(key);_dict.Add(key, value);}
}/*** 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);*/

实验结果

利用单链表的方式：

状态：通过
18 / 18 个通过测试用例
执行用时: 868 ms, 在所有 C# 提交中击败了 6.25% 的用户
内存消耗: 47.8 MB, 在所有 C# 提交中击败了 26.67% 的用户

提交结果

利用字典（哈希）+单链表的方式：

状态：通过
18 / 18 个通过测试用例
执行用时: 392 ms, 在所有 C# 提交中击败了 76.56% 的用户
内存消耗: 47.9 MB, 在所有 C# 提交中击败了 20.00% 的用户

提交结果

LeetCode实战：LRU缓存机制

背景

题目英文

题目中文

算法实现

实验结果

相关图文

相关文章：

探索性测试，笔记二

python 监控windows磁盘空间和备份大小

如何高效学习java课程

2021年web前端发展方向有哪些

weblogic服务器部署的程序，如何直接通过IP访问（即URL中去掉工程名）

LeetCode实战：二叉搜索树中第K小的元素

xml文件-1

学习web前端难不难

Android对话框-下篇-之设置activity为Dialog

Codeforces 846 B Math Show DFS + 贪心

LeetCode实战：二叉树的最近公共祖先

学习UI设计都需要了解哪些知识

Marty Cagan：怎样寻找出色的产品经理

LeetCode实战：除自身以外数组的乘积

PHP+MySql获取自动增长字段的新添加记录ID值

MyBatis框架添加客户有哪些步骤

磁盘IO的总结

UI设计培训之设计中的点线面-面

projecteuler_problem10

LeetCode实战：排序链表

技术图文：双指针在链表问题中的应用

[BuildRelease]build number / id

Windows Azure Storage (25) Azure Append Blob

学python培训到底能干嘛

使用VB.NET加快代码开发速度

技术图文：举例详解Python中 split() 函数的使用方法

Burning

UI设计工作好找吗?有哪些面试技巧?

刻意练习：Python基础 -- Task10. 类与对象

CentOS 7更新时出现Multilib version problems