1.题目

请你设计并实现一个满足 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) 的平均时间复杂度运行。

2.示例

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

2）提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

3.分析

虽然这道题思路不难想，但是细节真的好多，我看着我的提交记录陷入了沉思，真的应该给hard难度啊。。。
题目要求我们使用数据结构将映射的key和value存储下来，同时要求：
1）有内存限制，不能无限添加
2）添加和查询都是O(1)的操作
3）添加和查询都会让这个key值的优先级变得最高
4）当内存都被使用，又需要插入操作时，就需要删除掉优先级最低的key值
那么根据上述的描述，我们应该分别使用map和一个链表类来进行存储，需要注意的点有：
1）删除和添加改变节点间关系的时候都需要特判节点是不是空指针
2）链表节点类记得声明public
3）put 和get都需要把查询和添加的key值移到链表的尾部

4.代码

class ListNode1{public:int K,V;ListNode1* next,*la;ListNode1(int key,int val){K=key;V=val;next=NULL;la=NULL;}
};
class LRUCache {
public:map<int,ListNode1*> map1;int num=0,num1=0;ListNode1* head,*last;LRUCache(int capacity) {num=capacity;head=new ListNode1(0,0);last=head;}void make_piar(ListNode1* x,ListNode1* y){x->next=y;if(y!=NULL) y->la=x;}int get(int key) {if(map1.count(key)){ListNode1* m=map1[key]->la,*n=map1[key]->next;if(map1[key]!=last){make_piar(m,n);make_piar(last,map1[key]);}last=map1[key];return map1[key]->V;}// return (head->next)->K;return -1;}void put(int key, int value) {if(map1.count(key)){map1[key]->V=value;ListNode1* m=map1[key]->la,*n=map1[key]->next;if(map1[key]!=last){make_piar(m,n);make_piar(last,map1[key]);}last=map1[key];}else{if(num1!=num){ListNode1* n=new ListNode1(key,value);make_piar(last,n);last=n;num1++;map1[key]=n;}else{map<int,ListNode1*>::iterator iter=map1.find((head->next)->K);map1.erase(iter);ListNode1* n=new ListNode1(key,value);make_piar(last,n);map1[key]=n;last=n;ListNode1* m=(head->next)->next;make_piar(head,m);}}}
};