1.题目
2.思路
首先读懂题意：
首先缓存最大容量初始化为capacity这么大，然后实现：
put(key,val)存入键值对；get(key)获得键key对应的值val，如果键key不存在则返回-1。
为了实现O(1)的时间负责度进行get和put。使用哈希链表的组合——哈希表查找快，链表插入快但查找慢。借用labuladong的一张图：
其中双向链表可以使用list容器实现。
list的成员函数（举例）：
（1）push_front()在容器头部插入一个元素，和emplace_back()功能相当，但后者效率更高
（2）pop_front()删除容器头部的一个元素
（3）pop_back()删除容器尾部的一个元素
list的其他函数可以参考。
伪代码
（如果用java是用HashMap）
// key 映射到 Node(key, val) HashMap<Integer, Node> map; //如果用java是用HashMap。 // Node(k1, v1) <-> Node(k2, v2)... DoubleList cache; int get(int key) { if (key 不存在) { return -1; } else { 将数据 (key, val) 提到开头； return val; } } void put(int key, int val) { Node x = new Node(key, val); if (key 已存在) { 把旧的数据删除； 将新节点 x 插入到开头； } else { if (cache 已满) { 删除链表的最后一个数据腾位置； 删除 map 中映射到该数据的键； } 将新节点 x 插入到开头； map 中新建 key 对新节点 x 的映射； } }
3.代码（C++）
class LRUCache { private: list<pair<int,int>>cache; unordered_map<int,list<pair<int,int>>::iterator>key2node; int cap;//cache的最大容量 public: LRUCache(int capacity):cap(capacity){ } int get(int key) {//获取键key所对应的val值 if(key2node.find(key)==key2node.end()) return -1; //如果存在键key，即继续下步 pair<int,int>node=*key2node[key]; cache.erase(key2node[key]);//删除表中原有的结点 cache.push_front(node);//将节点插入到链表头部 key2node[key]=cache.begin();//易漏！不要只记得上面一步 return node.second;//返回键key对应的val值 } void put(int key, int val) { auto newNode =make_pair(key,val); if(key2node.count(key)){//该结点若已经存在，则删除旧结点（和上面类似） cache.erase(key2node[key]); }else{ if(cap==cache.size()){//如果cache已满 key2node.erase(cache.back().first);//删除key2node中映射到该数据的键 cache.pop_back();//删除链表的最后一个位置 } } cache.push_front(newNode);//插入新的结点到头部 key2node[key]=cache.begin();//新建映射 } }; /** * 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); */
4.注意点
其中LRUCache函数注意这种初始化操作：
pubic: LRUCache(int capacity):cap(capacity){}
这是初始化的意思
等你进入构造函数 这个对象以及在内存中构造好了
比如有个vector 等你进去构造函数 这个 vector已经存在了 长度是0 在构造函数里如果要改这个vector长度，就浪费了。
这个冒号后面的就是在对象一开始生成的时候执行的
这个时候vector设置多长 ，那么 构造的时候就会直接构造多长 避免重复更改
（1）写法一
cap是一个成员变量
capxxx是一个构造函数的参数，用来初始化cap
首先，调用构造函数，然后传入参数capxxxp
操作系统就开始生成一个类的对象，然后在给这个对象分配内存的时候，用参数capxxx初始化了cap这个变量，然后构造结束了
（2）写法二
如果不用这个写法
用大括号里写cap=capxxx
那么就是，操作系统初始化类的对象，分配内存。
cap这个成员变量的内存已经有了，但是没有初始化，值是多少是一种未定义的行为。
这个时候进去构造函数内部，注意，这个时候类其实已经构造好了，内存啥的都搞定了，内存中已经有一块内存是这个类了。
这个时候cap=capxxx
操作系统找到这个变量的地址，然后赋值给他。
区别就是在构造变量的同时初始化。还是构造结束了，再赋值
对于一个int差别不大
但是对于一些复杂类型，差别就大了。
比如举例的vector
如果冒号写法，就相当于调用构造函数
vector（size)，一开始就是有一定长度的
但是如果到了函数体再赋值，这个时候首先，他已经定义好了而且大小默是0，也就是说你要扩容，只能用扩容的方法，这个扩容肯定是耗费时间的。
而且因为已经构造好对象了，这个vector已经存在了，你就不能再用他的构造函数了，只能是给他赋值一个更大的。这其实是两重的构造，先构造一个大的vector。然后赋值给成员变量，成员变量拷贝。
然后退出的时候，这个函数内的vector还得析构.
reference
labuladong题解。
手写LUR。
