设计LRU缓存结构_

Python3

已注销

class DlinkNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class Solution:
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        self.cache = {}
        self.head = DlinkNode()
        self.tail = DlinkNode()
        self.head.next = self.tail
        self.tail.pre = self.head
        self.capacity = k
        self.size = 0
        
        def addTohead(node):
            node.pre = self.head
            node.next = self.head.next
            self.head.next.pre = node
            self.head.next = node
        
        def removenode(node):
            node.pre.next = node.next
            node.next.pre = node.pre
        
        def moveTohead(node):
            removenode(node)
            addTohead(node)
        
        def removeTail():
            node = self.tail.pre
            removenode(node)
            return node
        
        def get(key):
            if key not in self.cache:
                return -1
            else:
                node = self.cache[key]
                moveTohead(node)
                return node.value
        
        def set(key, value):
            if key not in self.cache:
                node = DlinkNode(key, value)
                self.cache[key] = node
                addTohead(node)
                self.size += 1
                if self.size>self.capacity:
                    rem = removeTail()
                    self.cache.pop(rem.key)
                    self.size -= 1
            else:
                node = self.cache[key]
                node.value = value
                moveTohead(node)
        res = []
        for opt in operators:
            if len(opt)==3:
                set(opt[1], opt[2])
            else:
                val = get(opt[1])
                res.append(val)
        return res

发表于 2021-11-23 10:53:46 回复(0)

Python3

JimPanda

class Solution:
    def LRU(self , operators , k ):
        # write code here
        stack = []
        kv_pair = {}
        ans = []
        for op in operators:
            if(op[0]==1):
                if(len(stack)>=k):
                    del kv_pair[stack.pop(0)]
                if(op[1] in kv_pair):
                    stack.pop(stack.index(op[1]))    
                stack.append(op[1])
                kv_pair[op[1]] = op[2]
            elif(op[0]==2):
                if(op[1] not in kv_pair):
                    ans.append(-1)
                else:
                    ans.append(kv_pair[op[1]])
                    stack.append(stack.pop(stack.index(op[1])))
        return ans

发表于 2021-10-14 10:01:21 回复(0)

Python3

牛客45854653号

class Solution:
    def LRU(self , operators , k ):
        # write code here
        key=[]
        anw=[]
        out=[]
        for i  in operators:
            if i[0]==1:
                if i[1] not in key:
                    key.append(i[1])
                    anw.append(i[2])
                    if len(key)>k:
                        key.pop(0)
                        anw.pop(0)
                else:
                    anw.pop(key.index(i[1]))
                    key.pop(key.index(i[1]))
                    key.append(i[1])
                    anw.append(i[2])
            elif i[0]==2:
                if i[1] in key:
                    out.append(anw[key.index(i[1])])
                    anw.pop(key.index(i[1]))
                    key.pop(key.index(i[1]))
                    key.append(i[1])
                    anw.append(out[-1])
                else:
                    out.append(-1)
        return out

暴力解，居然也能过

发表于 2021-08-24 15:48:26 回复(0)

Python3

无神小小志

class Solution:
@staticmethod
def clean_save(save_arrays, k, key, value):
if len(list(save_arrays.keys())) < k:
save_arrays[key] = value
else:
save_arrays.pop(list(save_arrays.keys())[0])
save_arrays[key] = value

def LRU(self, operators, k):
# write code here
save_arrays = dict()
res_list = list()
for opts in operators:
if len(opts) == 3:
_, key, value = opts
self.clean_save(save_arrays, k, key, value)
if len(opts) == 2:
_, key = opts
try:
value = save_arrays[key]
except:
value = -1
res_list.append(value)
self.clean_save(save_arrays, k, key, value)
print(save_arrays)
return res_list

发表于 2021-08-14 10:27:13 回复(0)

Python3

牛客352198672号

class Solution:
    def LRU(self, operators, k):
        lru = []
        lrud = {}
        result=[]
        for i in operators:
            if i[0] == 1:
                lrud[i[1]] = i[2]
                if len(lru) == k and i[1] not in lru:
                    lru.pop(0)
                else:
                    if i[1] in lru:
                        lru.remove(i[1])
                lru.append(i[1])
            if i[0] == 2:
                if i[1] in lru:
                    lru.remove(i[1])
                    lru.append(i[1])
                    result.append(lrud[i[1]])
                else:
                    result.append(-1)
        return result

发表于 2021-07-29 21:09:14 回复(1)

设计LRU缓存结构

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题