程序员面试金典面试题16。25。LRU缓存

　　题目难度: 中等
　　原题链接  [1]
　　今天继续更新程序员面试金典系列, 大家在公众号   算法精选   里回复  面试金典   就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
　　设计和构建一个＂最近最少使用＂缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
　　它应该支持以下操作： 获取数据 get 和 写入数据 put 。 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。 示例:LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );  cache.put(1, 1); cache.put(2, 2); cache.get(1);       // 返回  1 cache.put(3, 3);    // 该操作会使得密钥 2 作废 cache.get(2);       // 返回 -1 (未找到) cache.put(4, 4);    // 该操作会使得密钥 1 作废 cache.get(1);       // 返回 -1 (未找到) cache.get(3);       // 返回  3 cache.get(4);       // 返回  4 题目思考相当经典的一道题目, 要使得更新和查询都是 O(1)复杂度, 你想到了哪些数据结构组合能做到? 解决方案思路先设计需要使用的数据结构 根据 LRU 描述, 我们至少需要一个数据结构来存节点的新旧程度, 新的可以放一边, 老的放另一边, 这自然就是双向链表但是问题是链表虽然更新很快, 是 O(1), 但如何快速通过一个 key 查到对应的节点呢?很容易想到字典/hash 可以做到 O(1)查询, 然后要做的就是把这两个数据结构结合起来: 双向链表存节点的先后顺序, head 最新, tail 最老字典存 key=>节点的映射, 方便快速根据 key 定位到节点 接下来就是写具体的逻辑了, 这里一共有 3 种操作: get 和 put 已经存在的节点: 把已经存在的节点重新放在头部put 新的节点: 把新的节点放在头部删除最老的节点: 如果加入新节点后超过 capacity, 那么需要把最老的 tail 给去掉 逻辑优化 根据第 2 步中分析的 3 种操作, 我们可以直接写出每一种操作对应的代码, 但是里面会有很多重复的部分, 比如放在头部的操作在 2.1 和 2.2 都有, 而删除节点的操作则在 2.1 和 2.3 都有所以我们完全可以将这两部分操作提取出来一个是 add 节点操作, 把节点放到头部, 并更新连接关系和字典一个是 remove 节点操作, 删除某个节点, 并更新连接关系和字典 最后就是具体的代码部分了, 下面代码对每步操作都有详细的注释, 希望可以帮助大家更好理解 复杂度时间复杂度 O(1): 链表保证更新是 O(1), 字典保证查询是 O(1) 空间复杂度 O(C): C 是 capacity, 字典需要存这么多个 kv, 所以是 O(C) 代码class LRUCache:     class BiNode:         def __init__(self, k, v):             self.key = k             self.val = v             self.pre = None             self.nex = None      def __init__(self, capacity: int):         # 双向链表+字典         # 双向链表存节点的先后顺序, head最新, tail最老         # 字典方便快速根据key定位到节点         # 注意链表节点需要存key和value, 存key的目的是用于字典的检索         # 两者结合就能保证更新和查询的时间复杂度都是O(1), 链表保证更新是O(1), 字典保证查询是O(1)         # 注意提取新增和移除节点的逻辑, 方便复用, 简化代码         self.head = None         self.tail = None         self.kv = {}         self.capacity = capacity      def add(self, node):         # 将节点加到链表头         # 先操作字典         self.kv[node.key] = node         # 再更新节点连接关系和头尾         if not self.head:             # 没有head, 说明当前链表为空, 直接head和tail都设为node即可             self.head = self.tail = node         else:             # 更新新的head以及它与老head的连接关系             node.nex = self.head             self.head.pre = node             self.head = node      def remove(self, node):         # 移除某个节点         # 先操作字典         if node.key in self.kv:             del self.kv[node.key]         # 再更新节点连接关系和头尾         # 更新左右邻居的连接关系         pre, nex = node.pre, node.nex         # 注意当前节点的pre和nex都要重置为None         node.pre = node.nex = None         if pre:             pre.nex = nex         if nex:             nex.pre = pre         # 更新新的头尾         if node == self.head:             self.head = nex         if node == self.tail:             self.tail = pre      def get(self, key: int) -> int:         # 注意get操作也需要将node更新到链表头         if key in self.kv:             node = self.kv[key]             # 先把node从当前位置移除, 然后加入头部             self.remove(node)             self.add(node)             return node.val         return -1      def put(self, key: int, value: int) -> None:         if self.capacity <= 0:             # 如果capacity是0, 直接无法添加             return         if key in self.kv:             # 如果当前key存在的话, 先移除它             self.remove(self.kv[key])         elif len(self.kv) == self.capacity:             # 注意如果当前已经达到capacity的话先移除tail             self.remove(self.tail)         # 加入新节点到头部         newNode = self.BiNode(key, value)         self.add(newNode) 参考资料
　　[1]
　　原题链接: https://leetcode-cn.com/problems/lru-cache-lcci/