题解 | #设计LRU缓存结构#

思路

我是利用双链表+hash table的思路。
此代码有于76%的提交方案。

#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
class DoubleLinkedListNode:
    def __init__(self, x=None, y=None):
        self.key = x
        self.val = y
        self.pre = None
        self.next = None

class classLRU:
    def __init__(self,k):
        self.head = DoubleLinkedListNode()
        self.tail = DoubleLinkedListNode()
        self.head.next = self.tail
        self.tail.pre = self.head
        self.cache = dict()
        self.count = 0
        self.limit = k
    def get(self,key):
        if key in self.cache.keys():
            # move this key to the head
            self.move(key)
            return self.cache[key].val
        return -1
    def set(self,key,value):
        if key in self.cache.keys():
            self.cache[key].val = value
        else:
            nodeA = DoubleLinkedListNode(key,value)
            if self.count<self.limit:
                # add to the head
                self.addHead(nodeA)
                self.count+=1
            else:
                # remove the tail node
                self.removeTail()
                # add to this key:value to the head
                self.addHead(nodeA)
            self.cache[key] = nodeA
    def move(self,key,pos=0):
        if pos==0:
            #move this key to the head
            if key in self.cache.keys():
                node = self.cache[key]
                preN = node.pre
                nextN = node.next
                preN.next = nextN
                nextN.pre = preN
                self.addHead(node)
        if pos==1:
            #move this key to the tail
            pass

    def removeTail(self):
        # remove tail
        if self.count>0:
            # remove tail node
            nodeR = self.tail.pre
            nodePre = nodeR.pre
            nodePre.next = self.tail
            self.tail.pre = nodePre
            # remove from cache
            del self.cache[nodeR.key]
    def addHead(self,nodeA):
            tempN = self.head.next
            self.head.next = nodeA
            nodeA.pre = self.head
            nodeA.next = tempN
            tempN.pre = nodeA

class Solution:
    def LRU(self , operators , k ):
        # write code here
        res = []
        cLRU = classLRU(k)
        for op in operators:
            if op[0]==1:
                #print("add {},{}\n".format(op[1],op[2]))
                cLRU.set(op[1], op[2])
            elif op[0]==2:
                res.append(cLRU.get(op[1]))
        return res