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

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

from collections import namedtuple
from threading import RLock

_CacheInfo = namedtuple('CacheInfo', 'maxsize currsize')

class LruCache:

    PRE, NEXT, KEY, VALUE = 0, 1, 2, 3

    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.currsize = 0
        self.cache = {}
        self.lock = RLock()
        self.root = []
        self.root[:] = [self.root, self.root, None, None]  # [PRE, NEXT, KEY, VALUE]

    def put(self, key, value):
        if self.maxsize <= len(self.cache):
            oldroot = self.root
            oldroot[self.KEY] = key
            oldroot[self.VALUE] = value
            self.root = oldroot[self.NEXT]
            oldkey = self.root[self.KEY]
            oldvalue = self.root[self.VALUE]
            self.root[self.KEY] = self.root[self.VALUE] = None
            del self.cache[oldkey]
            self.cache[key] = oldroot
        else:
            last = self.root[self.PRE]
            link = [last, self.root, key, value]
            last[self.NEXT] = self.root[self.PRE] = self.cache[key] = link

        self.currsize = len(self.cache)

    def get(self, key):
        link = self.cache.get(key)
        if link is not None:
            link_last, link_next, _key, _value = link

            # 在链表中取出数据节点
            link_last[self.NEXT] = link_next
            link_next[self.PRE] = link_last

            # 重新放入链表
            last = self.root[self.PRE]
            link[self.PRE] = last
            link[self.NEXT] = self.root
            last[self.NEXT] = self.root[self.PRE] = link

            return _value
        return None




class Solution:
    def LRU(self , operators , k ):
        # write code here
        lru = LruCache(k)
        ret = []
        for operator in operators:
            if operator[0] == 1:
                lru.put(operator[1], operator[2])
            else:
                value = lru.get(operator[1])
                ret.append(-1 if value is None else value)
        return ret