网站切换中英文/微信广告投放收费标准

Leetcode 146. LRU缓存机制

• LRU(最近最少使用)算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高。
• 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
• 获取数据 get(key)- 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
• 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

• 你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

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

class ListNode:def __init__(self, key=None, value=None):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass ListNode:def __init__(self, key=None, value=None):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache(object):def __init__(self, capacity):""":type capacity: int"""self.capacity = capacityself.hashmap = {}# 新建两个节点 head 和 tailself.head = ListNode()self.tail = ListNode()# 初始化链表为 head <-> tailself.head.next = self.tailself.tail.prev = self.head# 因为get与put操作都可能需要将双向链表中的某个节点移到末尾，所以定义一个方法def move_node_to_tail(self, key):# 先将哈希表key指向的节点拎出来，为了简洁起名node#      hashmap[key]                               hashmap[key]#           |                                          |#           V              -->                         V# prev <-> node <-> next         pre <-> next   ...   nodenode = self.hashmap[key]node.prev.next = node.nextnode.next.prev = node.prev# 之后将node插入到尾节点前#                 hashmap[key]                 hashmap[key]#                      |                            |#                      V        -->                 V# prev <-> tail  ...  node                prev <-> node <-> tailnode.prev = self.tail.prevnode.next = self.tailself.tail.prev.next = nodeself.tail.prev = nodedef get(self, key):""":type key: int:rtype: int"""if key in self.hashmap:# 如果已经在链表中了久把它移到末尾（变成最新访问的）self.move_node_to_tail(key)res = self.hashmap.get(key, -1)if res == -1:return reselse:return res.valuedef put(self, key, value):""":type key: int:type value: int:rtype: None"""if key in self.hashmap:# 如果key本身已经在哈希表中了就不需要在链表中加入新的节点# 但是需要更新字典该值对应节点的valueself.hashmap[key].value = value# 之后将该节点移到末尾self.move_node_to_tail(key)else:if len(self.hashmap) == self.capacity:# 去掉哈希表对应项self.hashmap.pop(self.head.next.key)# 去掉最久没有被访问过的节点，即头节点之后的节点self.head.next = self.head.next.nextself.head.next.prev = self.head# 如果不在的话就插入到尾节点前new = ListNode(key, value)self.hashmap[key] = newnew.prev = self.tail.prevnew.next = self.tailself.tail.prev.next = newself.tail.prev = new

• LRU 的思路是采用一个双向链表 + hashmap （通过key快速定位node {key: node}）, 每次缓存命中，会将其key对应的node重新放置于双向链表的尾部；如果put新的key时，超出cache大小，则丢弃掉双向链表的头部，同时将新的值插入到双向链表的尾部；