146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
函数 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
思路：
LRU缓存也算是比较高频和经典的题目了，尤其是后端选手很容易遇到这个题（不过我这里是用python来实现的）。对于LRU主要就是定义一个get和一个put的接口，然后每次操作到相关的数据之后，就需要把该数据更新到面板最前面。
首先直接说实现方式和结论：为了使get和put的平均时间复杂度都为O(1)，我们需要使用一个双向链表和一个哈希表。
根据题意，每次存入的数据都是key-value的形式，因此对于链表中的每一个节点，内部至少有两个变量：key和value，其次因为它是双向链表，我们要需要pre指针和next指针；而哈希表的使用则是这样的：哈希表中的key就是存入数据的key，哈希表中的value就是节点，直观点可以这么理解：哈希表[3]=Node(3,5)，即int型对应Node型。
因此节点的定义方式是这样的：
class ListNode():#里面有四个变量
def __init__(self,key=None,value=None):
self.key = key
self.value=value
#还有两个指针，创建了但是没值，就等于None吧
self.pre=None
self.next=None
整个LRUCache的定义方式是这样的：
class LRUCache():
def __init__(self,capacity): #一开始除了头尾节点外，长度为0，头尾互相指
self.head=ListNode()#头结点
self.tail=ListNode()#尾节点
self.head.next=self.tail#头节点的next初始化指向尾
self.tail.pre=self.head#为节点的pre初始化指向头
self.hashmap={} #双向链表有了，再定义一个哈希表
self.capacity=capacity#第四个参数 容量
数据结构弄清了，接下来就是put和get的算法部分。
在说get和put之前，先要弄清一个事情，LRU的一大特点就是在操作某个数据之后，需要我们把某个数据移动到“最上面”，表示刚刚操作过。因此后面不管是get还是put都会有这个需求，我们可以提前定义出来。目前我们的双向链表头结点是head，尾节点是tail，这两个变量我们不会用来存放实际数据，只是用于插入和取出真正的首位数据。
注意：我这里默认越往右的数据越新，越往左的数据越老。
比如现在我们要把数据移到LRU的“最上面”、“最新处”，我们把这个功能叫做move_to_first，而这个first的位置是在最右边，也就是tail之前的那个节点。而最老的节点在哪呢？在head的后面。
知道了first的位置，我们定义起这个功能就很简单了：
def move_to_first(self,key):
node = self.hashmap[key] #把node从当前双向链表取出
#取出时让原来的左右两边相连，不要断开
node.pre.next=node.next
node.next.pre=node.pre
#把node移动到最后当作first （严格说其实是tail的前面一位，head，tail始终首尾）
#双向链表插入节点方式：先建立新链接（前两句）再断开和改变原链接（后两句）
node.next=self.tail
node.pre = self.tail.pre
node.next.pre=node
node.pre.next=node
现在我们可以正式开始看get和put了。
首先是get，这个很简单，通过哈希表来进行get(key)的查找，复杂度就是O(1)，如果查不到则按提议返回-1，若查到了则返回这个Node的value值，并且因为get过这个数字，需要把这个节点move_to_first。
其次是put，put是往链表里添加节点了，会涉及到容量capacity的问题，所以会麻烦一些。Put的总体逻辑是这样的：首先判断要添加的节点的key在不在哈希表中，如果在的话，我们不需要添加新节点，只需要更新value值即可，并且将其move_to_first。如果不在哈希表中，我们要先去判断容量是否足够，如果容量足够，则我们直接在first（tail之前）的位置插入这个新节点；如果容量不够，则需要先删除最末尾（head之后）的节点，空出一个位置后，再在first位置插入这个新节点。
代码：
# class LRUCache:
# def __init__(self, capacity: int):
# def get(self, key: int) -> int:
# def put(self, key: int, value: int) -> None:
class ListNode():#里面有四个变量
def __init__(self,key=None,value=None):
self.key = key
self.value=value
#还有两个指针，创建了但是没值，就等于None吧
self.pre=None
self.next=None
class LRUCache():
def __init__(self,capacity): #一开始除了头尾节点外，长度为0，头尾互相指
self.head=ListNode()#头结点
self.tail=ListNode()#尾节点
self.head.next=self.tail#头节点的next初始化指向尾
self.tail.pre=self.head#为节点的pre初始化指向头
#双向链表有了，再定义一个哈希表
self.hashmap={}
#第四个参数 容量
self.capacity=capacity
def move_to_first(self,key):
node = self.hashmap[key] #把node从当前双向链表取出
#取出时让原来的左右两边相连，不要断开
node.pre.next=node.next
node.next.pre=node.pre
#把node移动到最后当作first （严格说其实是tail的前面一位，head，tail始终首尾）
#双向链表插入节点方式：先建立新链接（前两句）再断开和改变原链接（后两句）
node.next=self.tail
node.pre = self.tail.pre
node.next.pre=node
node.pre.next=node
#按要求写get方法，传入一个key
def get(self,key):
#判断有无
if key not in self.hashmap:
return -1#无则直接返回-1
#如果有，调用move_to_first更新一波
self.move_to_first(key)
node = self.hashmap[key]#通过哈希表取出节点
return node.value#通过节点取出值
#put方法，传入key和value两个值
def put(self,key,value):
#首先判断key是不是已经在hash表中了
if key in self.hashmap:
node = self.hashmap[key]
node.value=value#有则更新值
#再移至第first
self.move_to_first(key)
else:#不在hash表里
#判断够不够装下
if len(self.hashmap)==self.capacity:#已经满了
#删除掉head后面的节点
#既要删除节点 还要删除哈希表中的映射！！！不要漏写
delete_key = self.head.next.key#定位到要删除的key
self.hashmap.pop(delete_key)#哈希表删除映射，这里容易漏
#删除这个节点
self.head.next = self.head.next.next
self.head.next.pre = self.head
#插入这个新节点
node = ListNode(key,value)#new一个节点
self.hashmap[key]=node#建立映射
#双向链表插入节点方式：
#先建立新链接（前两句）再断开和改变原链接（后两句）
node.next=self.tail
node.pre=self.tail.pre
node.next.pre = node
node.pre.next=node
小结：
LRU机制首先得知道它是做什么的，清楚它最基本的机制（好像就类似于手机后台的缓存一样，刚刚用过的会出现在最上面，很久不用的在最底部直至被淘汰挤没）。然后要记住满足题目复杂度的实现方法：使用双向链表+哈希表。此外把尝试用的功能move_to_first提前定义出来，方便put和get等地方的调用。最后要注意一些细节，put 的时候先查找是否已存在，插入的时候考虑容量等。
总体来说LRU看起来步骤挺复杂的但是逻辑很清楚，不过能不出错地一遍写出来也不是很容易。写的时候要注意细节，一定要自己亲自写一下才知道哪些地方要注意。
