146:LRU缓存

说说怎么背这道题。

需要运用 双端队列和哈希表，这是一种复合数据结构，如python中的OrderedDict
哈希表只是根据key,能找到对应的node,即<key,node*>
双端队列是双值双指针的形式,key,value,*prev,*next
哈希表的操作，API已经提供了，现在就是看自己创建双端队列，并看其需要哪些操作。
python中API叫 move_to_end，所谓move操作，就是一个删除操作，一个插入操作。
所以双端队列的基本操作需要删掉节点，和插入节点到最新这两个。
3.到目前位置双端队列和哈希表的基本操作都够了，现在就是LRUCache这个复合类需要哪些操作。get_node这个名字起的很好，我开始觉得应该叫做find_node,因为是根据key，找到返回node,找不到返回nullptr,但这个题让我们写一个API叫做put,根据key，找到返回value，找不到返回-1。那我们这个额外的API叫做get_node那就再合适不过了。
4.到目前位置put,和get怎么写其实就很简单了。
get操作，只会更新双端队列类的元素
put操作，即会更新双端队列类的操作，也会更新哈希表类的元素。
总结一下：
1.两个数据结构，双端队列和哈希表
2.需要自己自定义双端队列和其基本操作删除和插入操作
3.定义get_node API，这个才是这个复合数据结构的操作，剩下就是记得怎么更新双端队列和哈希表了

额外说下dummy的作用：
1.快速找到双端队列中最末尾的节点
2.插入时，快速找到最新位置
3.操作可以不区分head节点和tail节点，让其更普通节点一样

总结：同化了head节点和tail节点的操作，要提供了快速找到head和tail的方法。额外的一点空间却极大简化的操作。妙！