文章目录 一、题目二、C# 题解
一、题目
设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
它应该支持以下操作： 获取数据 get 和 写入数据 put。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
示例:
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
点击此处跳转题目。
二、C# 题解
LRU 的思想就是将不常使用的元素优先级设置最低。因此算法规则如下：
新数据插入到链表头部；当缓存命中（即缓存数据被访问），数据要移到表头；当链表满的时候，将链表尾部的数据丢弃。
这里使用数组存储链表结构，因为简单高效。
public class LRUCache { private struct Node { public int Key, Value, Left, Right; } private int _cap, _size; private Node[] _list; // 带头结点的双向链表数组实现，_list[0] 作为头结点 private int FirstPos { // 第一个结点的物理位置存储在 _list[0].Right 中 get => _list[0].Right; set => _list[0].Right = value; } private int RearPos { // 尾结点的物理位置存储在 _list[0].Left 中 get => _list[0].Left; set => _list[0].Left = value; } private Dictionary
_dic; public LRUCache(int capacity) { _cap = capacity; _size = 0; _list = new Node[_cap + 1]; // _list[0] 用作 head 结点，存储 first 和 rear 位置 _dic = new Dictionary(); // 记录 key 所在结点的位置 pos } public int Get(int key) { // Cache 中存在 key，则将其移到表头，并返回对应的 value if (_dic.TryGetValue(key, out int pos)) { MoveToFirst(pos); return _list[pos].Value; } // 不存在，返回 -1 return -1; } public void Put(int key, int value) { // Cache 中存在 key，则将其移到表头，并更新 value if (_dic.TryGetValue(key, out int pos)) { MoveToFirst(pos); _list[pos].Value = value; } // 不存在 key else { // 链表未满，则直接插入新结点 if (_size < _cap) { AddNode(key, value, ++_size); // 新结点的物理位置在数组的下一个位置 _dic.Add(key, _size); // 添加 key 的记录 } // 链表已满，需要移除尾结点，将新结点插入表头 else { int rear = RearPos; // 记录此时的尾结点位置 ReMoveAt(rear); // 移除尾结点 _dic.Remove(_list[rear].Key); AddNode(key, value, rear); // 向表头插入新结点，物理位置就存储在刚删掉的尾结点 rear 处 _dic.Add(key, rear); } } } // 向表头插入结点，结点存储在 _list[pos] 的位置中 private void AddNode(int key, int value, int pos) { // 创建结点 _list[pos].Key = key; _list[pos].Value = value; // 插入表头 _list[pos].Left = 0; _list[pos].Right = FirstPos; _list[FirstPos].Left = pos; FirstPos = pos; } // 将 pos 位置处的结点移到表头 private void MoveToFirst(int pos) { ReMoveAt(pos); // 将该结点从链表中移出 AddNode(_list[pos].Key, _list[pos].Value, pos); // 再插入表头 } // 将 _list[pos] 处的结点从链表中移除 private void ReMoveAt(int pos) { int leftPos = _list[pos].Left; int rightPos = _list[pos].Right; _list[leftPos].Right = rightPos; _list[rightPos].Left = leftPos; } } /** * 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); */ 时间：176 ms，击败 100.00% 使用 C# 的用户内存：64.35 MB，击败 85.71% 使用 C# 的用户 
