Python 哈希表+双向链表/有序字典
设计LRU缓存结构
http://www.nowcoder.com/questionTerminal/e3769a5f49894d49b871c09cadd13a61
最近使用的放在链表尾部
哈希表 + 双向链表
class DListNode:
def __init__(self, x=0, y=0):
self.key = x
self.value = y
self.pre = None
self.next = None
class Solution:
def __init__(self):
self.head = DListNode()
self.tail = DListNode()
self.head.next = self.tail
self.tail.pre = self.head
self.cache = dict()
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self.move_to_end(node)
return node.value
def set(self, key, value, k):
if key in self.cache:
node = self.cache[key]
node.value = value
self.move_to_end(node)
else:
node = DListNode(key, value)
self.cache[key] = node
self.add_to_end(node)
if len(self.cache) > k:
removed = self.head.next
self.remove(removed)
del self.cache[removed.key]
def remove(self, node):
node.pre.next = node.next
node.next.pre = node.pre
def add_to_end(self, node):
node.pre = self.tail.pre
node.next = self.tail
self.tail.pre.next = node
self.tail.pre = node
def move_to_end(self, node):
self.remove(node)
self.add_to_end(node)
def LRU(self, operators, k):
res = []
for opt in operators:
if opt[0] == 1:
self.set(opt[1], opt[2], k)
elif opt[0] == 2:
res.append(self.get(opt[1]))
return res有序字典
from collections import OrderedDict
class Solution:
def __init__(self):
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def set(self, key, value, k):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > k:
self.cache.popitem(last=False)
def LRU(self, operators, k):
res = []
for opt in operators:
if opt[0] == 1:
self.set(opt[1], opt[2], k)
elif opt[0] == 2:
res.append(self.get(opt[1]))
return res
