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

#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#

class ListNode:
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None
    
    
    def __str__(self):
        if not self:
            return "None"
        return str((self.key,self.value)) + " --> " + str(self.next)
        
        
        
class Solution:
    def __init__(self):
        self.head = ListNode(-1,-1)
        self.tail = ListNode(-1,-1)
        self.head.next = self.tail
        self.tail.pre = self.head
        self.size = 0
        self.mark = {}
        
        
    def LRU(self , operators , k ):
        # write code here
        self.k = k
        res = []
        for operator in operators:
            if operator[0]==1:
                self.set(operator[1],operator[2])
#                 print(self.head)
            else:
                value = self.get(operator[1])
                res.append(value)
#                 print(self.head)
        return res
        
    def set(self,key,value):
        if not self.mark.get(key,None):
            node = ListNode(key,value)
            # insert node after head
            node.next = self.head.next
            node.pre = self.head 
            self.head.next.pre = node
            self.head.next = node
            self.mark[key] = node
            if self.size==self.k:
                # delete last node
                key_to_del = self.tail.pre.key
                node = self.tail.pre.pre
                node.next = self.tail
                self.tail.pre = node
                self.mark[key_to_del] = None
            else:
                self.size += 1
        else:
            # delete node
            node = self.mark.get(key)
            node.value = value
            pre_node = node.pre
            pre_node.next = node.next
            node.next.pre = pre_node
            # insert node after head
            node.next = self.head.next
            node.pre = self.head 
            self.head.next.pre = node
            self.head.next = node

    def get(self,key):
        if self.mark.get(key,None):
            #delete node
            node = self.mark.get(key)
            pre_node = node.pre
            pre_node.next = node.next
            node.next.pre = pre_node
            # insert node after head
            node.next = self.head.next
            node.pre = self.head 
            self.head.next.pre = node
            self.head.next = node
            # 
            return node.value
        else:
            return -1