LeetCode 面试题 16.25. LRU 缓存

一、题目

  设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

  它应该支持以下操作： 获取数据 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 的思想就是将不常使用的元素优先级设置最低。因此算法规则如下：

1. 新数据插入到链表头部；
2. 当缓存命中（即缓存数据被访问），数据要移到表头；
3. 当链表满的时候，将链表尾部的数据丢弃。

  这里使用数组存储链表结构，因为简单高效。

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<int, int> _dic;public LRUCache(int capacity) {_cap = capacity;_size = 0;_list = new Node[_cap + 1];        // _list[0] 用作 head 结点，存储 first 和 rear 位置_dic = new Dictionary<int, int>(); // 记录 key 所在结点的位置 pos}public int Get(int key) {// Cache 中存在 key，则将其移到表头，并返回对应的 valueif (_dic.TryGetValue(key, out int pos)) {MoveToFirst(pos);return _list[pos].Value;}// 不存在，返回 -1return -1;}public void Put(int key, int value) {// Cache 中存在 key，则将其移到表头，并更新 valueif (_dic.TryGetValue(key, out int pos)) {MoveToFirst(pos);_list[pos].Value = value;}// 不存在 keyelse {// 链表未满，则直接插入新结点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# 的用户