AlgoPressAppearance
题目描述
https://leetcode.cn/problems/lru-cache
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
- 1 <= capacity <= 3000
- 0 <= key <= 10000
- 0 <= value <= 105
- 最多调用 2 * 105 次 get 和 put
思路
使用hash表储存字典值，再使用另外一个字典表储存访问时间。 当添加数据到缓存的时候，如果发现缓存已经满了，找寻使用时间最久的那个删除掉。 为了计算简便，将时间使用递增数据表示，在 Get 和 Put 的时候，递增时间值。
参考代码
csharp
public class LRUCache {
int capacity = 0;
int time = 0; //调用时序，用来表示时间
Dictionary<int,int> dict;
Dictionary<int,int> usedTime;
public LRUCache(int capacity) {
time = 0;
this.capacity = capacity;
dict = new Dictionary<int,int>();
usedTime = new Dictionary<int,int>();
}
public int Get(int key) {
time++;
if(dict.ContainsKey(key)){
usedTime[key]=time;
return dict[key];
}
return -1;
}
public void Put(int key, int value) {
time++;
if(dict.ContainsKey(key)){
dict[key] = value;
usedTime[key] = time;
return;
}
if(dict.Count == capacity){
//找出最小的time值
int maxTime = int.MaxValue;
int keyToDelete = 0;
foreach(int myKey in usedTime.Keys){
if(usedTime[myKey] < maxTime){
maxTime = usedTime[myKey];
keyToDelete = myKey;
}
}
//删除
//Console.WriteLine("删除{0}",keyToDelete);
dict.Remove(keyToDelete);
usedTime.Remove(keyToDelete);
}
dict.Add(key,value);
usedTime.Add(key,time);
}
}
/**
* 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);
*/
复习：20220704
csharp
public class LRUCache {
public class CacheItem{
public int Value;
public int Time;
public CacheItem(int value, int time){
Value = value;
Time = time;
}
}
private int time;
private int capacity;
private Dictionary<int, CacheItem> dict;
public LRUCache(int capacity) {
this.time = 0;
this.capacity = capacity;
dict = new Dictionary<int, CacheItem>();
}
public int Get(int key) {
time++;
if(dict.ContainsKey(key)){
dict[key].Time = time;
return dict[key].Value;
}
return -1;
}
public void Put(int key, int value) {
time++;
if(!dict.ContainsKey(key)){
dict.Add(key,new CacheItem(value,time));
}
else{
dict[key].Value = value;
dict[key].Time = time;
}
//Console.WriteLine("count1:{0}",dict.Count);
//outputDict();
//删除
if(capacity < dict.Count){
int keyToDelete = -1;
int minTime = time;
foreach(int k in dict.Keys){
//Console.WriteLine("foreach key : {0}, time:{1},minTime:{2}",k,dict[k].Time,minTime);
if(dict[k].Time < minTime){
minTime = dict[k].Time;
//Console.WriteLine("minTime {0}",minTime);
keyToDelete = k;
}
}
//Console.WriteLine("removing {0}",keyToDelete);
dict.Remove(keyToDelete);
}
//Console.WriteLine("count2:{0}",dict.Count);
//outputDict();
}
private void outputDict(){
foreach(int k in dict.Keys){
Console.WriteLine("{0}={1}, time={2}",k,dict[k].Value,dict[k].Time);
}
}
}
/**
* 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);
*/