public class LRUCache
{
int Capacity = ;
int Curlen = ;
long sernumbers;
long SerNumbers
{
get
{
if (sernumbers <= long.MaxValue)
{
return sernumbers;
}
else
{
dic.Clear();
return ;
}
}
set
{
sernumbers = value;
} }
Dictionary<int, KeyValuePair<int, long>> dic = new Dictionary<int, KeyValuePair<int, long>>();
//外层的Key为LRU的key，
//内层的Key为LRU的Value，内层的Value为访问编号 public LRUCache(int capacity)
{
Capacity = capacity;
} public int Get(int key)
{
if (dic.ContainsKey(key))
{
var K = dic[key].Key;
dic[key] = new KeyValuePair<int, long>(K, SerNumbers++);
return K;
}
else
{
return -;
}
} public void Put(int key, int value)
{
if (dic.ContainsKey(key))
{
dic[key] = new KeyValuePair<int, long>(value, SerNumbers++);
}
else
{
if (Curlen < Capacity)
{
dic.Add(key, new KeyValuePair<int, long>(value, SerNumbers++));
Curlen++;
}
else
{
var evictkey = dic.OrderBy(x => x.Value.Value).FirstOrDefault().Key;
dic.Remove(evictkey);
dic.Add(key, new KeyValuePair<int, long>(value, SerNumbers++));
} }
}
}
经典题目LRU被从Hard降低为Medium类别了，原来的实现有一点问题，
我又找了一个使用C#封装的数据结构LinkedList的实现，写起来更加简单。
linkedlist，链头记录最旧的数据，链尾记录最新的数据。
public class LRUCache
{ private readonly LinkedList<int> _queue;
private readonly Dictionary<int, int> _dict;
private readonly int _capacity; public LRUCache(int capacity)
{
_queue = new LinkedList<int>();
_dict = new Dictionary<int, int>();
_capacity = capacity;
} public void Put(int key, int value)
{
if (_dict.TryGetValue(key, out var previousValue))
{
_dict.Remove(key);
_queue.Remove(key);
} if (_queue.Count == _capacity)
{
var first = _queue.First;
_dict.Remove(first.Value);
_queue.RemoveFirst();
} _dict[key] = value;
_queue.AddLast(key);
} public int Get(int key)
{
if (!_dict.TryGetValue(key, out int value))
{
return -;
} _queue.Remove(key); _queue.AddLast(key); return value;
}
}