题目：

解法1：ordered dictionary

用python内置的工具，关于这种解法不做详述，因为LRU这个题目肯定还是要要考察他的具体实现的，所以这种解法参考Leetcode官方即可：
https://leetcode.com/problems/lru-cache/solution/

解法2：Hashmap+double linked list

这种解法是标准解法。这道题的关键在于如何理解least recently used这个含义。大体来讲就是，只要某个元素进行过任何操作，那么这个元素就是last recently used，或者说最先用到过的。具体参考：https://www.interviewcake.com/concept/java/lru-cache#:~:text=A%20Least%20Recently%20Used%20(LRU,other%20end%20of%20the%20rack.

这边的解法是这样的：构建一个hashmap，key是查询元素的key，value是double linked listnode。通过hasmap的特性保证查找元素的复杂度是O(1)，通过double linked list保证删除node，添加node的复杂度也是O(1)。具体步骤如下：

• 构建add_node操作，这个操作将一个新的节点加到linked list的头部
• 构建remove_node操作，删除特定的某的node
• 构建move_to_head操作，如果说一个node一旦被进行任何操作，那就要把它移到linked list的头部，表示他最近被使用过
• 构建pop_tail操作，当目前的linked list容量超过给定的容量时，要删除linked list尾部的node，也就是被使用的时间离现在最远的那个节点

class DLinkedNode():def __init__(self):self.key = 0self.value = 0self.prev = Noneself.next = None
class LRUCache:def __init__(self, capacity: int):# value of capacity is double linked list nodeself.cache = {}self.size= 0self.capacity = capacityself.head,self.tail = DLinkedNode(),DLinkedNode()# initialize a empty double linked listself.head.next = self.tailself.tail.prev = self.headdef get(self, key: int) -> int:node = self.cache.get(key)if not node:return -1self.move_to_head(node)return node.valuedef put(self, key: int, value: int) -> None:node = self.cache.get(key)if not node:newNode = DLinkedNode()newNode.key = keynewNode.value = valueself.cache[key] = newNodeself.add_node(newNode)self.size += 1# pop the tail if size over capacityif self.size > self.capacity:tail = self.pop_tail()del self.cache[tail.key]self.size -= 1else:node.value = valueself.move_to_head(node)def add_node(self,node):# add node right after headnode.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef remove_node(self,node):prev = node.prev_next = node.nextprev.next = _next_next.prev = prevdef move_to_head(self,node):self.remove_node(node)self.add_node(node)def pop_tail(self):poped_node = self.tail.prevself.remove_node(poped_node)return poped_node