首页 > 试题广场 >

设计LRU缓存结构

[编程题]设计LRU缓存结构
  • 热度指数：144640 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，操作次数是 n ，并有如下两个功能
1. set(key, value)：将记录(key, value)插入该结构
2. get(key)：返回key对应的value值

提示:
1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过k时，移除最不经常使用的记录。
3.输入一个二维数组与k，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value
若opt=1，接下来两个整数key, value，表示set(key, value)
若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
对于每个opt=2，输出一个答案
4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

要求：set和get操作复杂度均为
数据范围： ，
示例1

输入

[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

输出

[1,-1]

说明

[1,1,1]，第一个1表示opt=1，要set(1,1)，即将(1,1)插入缓存，缓存是{"1"=1}
[1,2,2]，第一个1表示opt=1，要set(2,2)，即将(2,2)插入缓存，缓存是{"1"=1,"2"=2}
[1,3,2]，第一个1表示opt=1，要set(3,2)，即将(3,2)插入缓存，缓存是{"1"=1,"2"=2,"3"=2}
[2,1]，第一个2表示opt=2，要get(1)，返回是[1]，因为get(1)操作，缓存更新，缓存是{"2"=2,"3"=2,"1"=1}
[1,4,4]，第一个1表示opt=1，要set(4,4)，即将(4,4)插入缓存，但是缓存已经达到最大容量3，移除最不经常使用的{"2"=2}，插入{"4"=4}，缓存是{"3"=2,"1"=1,"4"=4}
[2,2]，第一个2表示opt=2，要get(2)，查找不到，返回是[1,-1]
示例2

输入

[[1,1,1],[1,2,2],[2,1],[1,3,3],[2,2],[1,4,4],[2,1],[2,3],[2,4]],2

输出

[1,-1,-1,3,4]
算法知识视频讲解
添加回答
Python 3
想起来就做两道（JihongRen）头像 想起来就做两道（JihongRen） 
from typing import List


class Solution:
    def LRU(self, operators: List[List[int]], k: int) -> List[int]:
        # STEP 1: 准备用于存取数据的数据结构
        hashmap = dict()
        dlinkedlist = self.DoubleLinkedList()

        # STEP 2: 定义存取方法
        def _put(key, val):
            dnode = self.DoubleLinkedNode(key, val)
            if key in hashmap:
                dlinkedlist.remove(hashmap[key])
                dlinkedlist.push(dnode)
                hashmap[key] = dnode
            else:
                if len(dlinkedlist) == k:
                    tail = dlinkedlist.pop()
                    hashmap.pop(tail.key)
                dlinkedlist.push(dnode)
                hashmap[key] = dnode

        def _get(key):
            dnode = hashmap.get(key, None)
            if dnode is None:
                return -1
            val = dnode.val
            _put(key, val)
            return val

        # STEP 3: 记录索引查找返回值
        val_list = []
        for op in operators:
            if op[0] == 1:
                key, val = op[1:]
                _put(key, val)
            if op[0] == 2:
                key = op[1]
                val = _get(key)
                val_list.append(val)
            # print("set" if op[0] == 1 else "get", op[1:])
            # print(dlinkedlist, hashmap, sep="\n", end="\n\n")
        return val_list

    class DoubleLinkedNode:
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.prev = None
            self.next = None

        def __repr__(self):
            return f"({self.key}, {self.val})"

    class DoubleLinkedList:
        def __init__(self):
            self.head = None
            self.tail = None
            self._len = 0

        def __len__(self):
            return self._len

        def __str__(self):
            if self.head is self.tail:
                return f"{self.head} (head, tail)"

            nodes = []
            node = self.head
            while node is not None:
                nodes.append(
                    f"{node} (head)" if node is self.head else (f"{node} (tail)" if node is self.tail else str(node))
                )
                node = node.next
            return " -> ".join(nodes)

        def push(self, dnode):
            if self.head is None:
                self.head = self.tail = dnode
            else:
                dnode.next = self.head
                self.head.prev = dnode
                self.head = dnode
            self._len += 1

        def pop(self):
            if self.tail is None:
                return None
            elif self.tail is self.head:
                tail = self.tail
                self.__init__()
                return tail
            else:
                tail = self.tail
                self.tail = self.tail.prev
                self.tail.next = None
                self._len -= 1
                tail.prev = None
                return tail

        def remove(self, dnode):
            if dnode is self.head and dnode is self.tail:
                self.__init__()
            else:
                if dnode is self.head:
                    dnode.next.prev = None
                    self.head = dnode.next
                    dnode.next = None
                elif dnode is self.tail:
                    self.tail = dnode.prev
                    dnode.prev.next = None
                    dnode.prev = None
                else:
                    prev = dnode.prev
                    prev.next = dnode.next
                    prev.next.prev = prev
                    dnode.prev = dnode.next = None
                self._len -= 1
            return dnode

发表于 2022-03-15 22:39:17 回复(0)
Python 3
JSFaner头像 JSFaner 
class Solution:
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        stack = [] #有序
        div_kv = {} #无序
        res = []  #结果
        for op in operators:
            if op[0] == 1:#set操作
                if len(stack) >= k: 
                    del div_kv[stack.pop(0)]
                if op[1] in div_kv: 
                    stack.remove(op[1])
                stack.append(op[1])
                div_kv[op[1]] = op[2] 
            elif op[0] == 2:#get操作
                if op[1] not in div_kv:
                    res.append(-1)
                else:
                    stack.remove(op[1])
                    stack.append(op[1])
                    res.append(div_kv[op[1]])
        return res

发表于 2022-02-13 16:22:07 回复(0)
Python 3
yong.z头像 yong.z
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        def set(key=1,value=1,lru=[],k=1):
            inde = None
            for item in lru:
                if key == item[0]:
                    inde = lru.index(item)
            if inde is not None:
                end = lru.pop(inde)
                lru = lru + [end]
                lru[-1][1] = value
            else:
                lru.append([key,value])
                if len(lru) > k:
                    lru = lru[1:]
            return lru
        def get(key,lru):
            for item in lru:
                inde = None
                if key == item[0]:
                    out = item[1]
                    inde = lru.index(item)
                    end = lru.pop(inde)
                    lru = lru + [end]
                    return out,lru
            return -1,lru
        self.out = []
        lru = []
        for item in operators:
            if item[0] == 1 and len(item) == 3:
                lru = set(item[1],item[2],lru,k)
            elif  item[0] == 2 and len(item) == 2:
                value,lru = get(item[1],lru)
                self.out.append(value)
        return self.out
                
            
            
            
            
            
            
            
            
            
            
发表于 2022-01-05 20:46:56 回复(0)
Python 3
牛客296529746号头像 牛客296529746号 
#
class Solution:
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        result=[]
        lrud={}
        for i in operators:
            if i[0]==1:
                lrud[i[1]]=i[2]
                if len(lrud) > k:
                    lrud.pop(list(lrud)[0])
            else:
                if i[1] in list(lrud):
                    result.append(lrud[i[1]])
                    lrud[i[1]]=lrud.pop(i[1])
                else:
                    result.append(-1)
        return result

发表于 2021-12-19 19:15:11 回复(0)
Python 3
苏堤头像 苏堤
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        lru_d=dict()
        order_list=[]
        def get(key):
            val=-2
            if(key in lru_d.keys()):
                order_list.remove(key)
                order_list.append(key)
                val= lru_d[key]
            else:
                val =-1
            return val
        def set(key,val):
            if(len(order_list) <k):
                order_list.append(key)
                lru_d[key]=val
            else:
                old_key=order_list.pop(0)
                lru_d.pop(old_key)
                order_list.append(key)
                lru_d[key]=val
                
            
        res=[]
        for oper in operators:
            if  oper[0]==1:
                set(oper[1],oper[2])
            elif  oper[0]==2:
                tmp=get(oper[1])
                res.append(tmp)
        return res
            
            
             
发表于 2021-12-18 01:02:29 回复(0)
Python 3
tangjunjun头像 tangjunjun 
class Solution:
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        import collections
        dict_cache=collections.OrderedDict()#有序字典
        def get(key):
            if key not in dict_cache:
                return -1
            else:
                v=dict_cache[key]
                dict_cache.move_to_end(key)
                return v
        def set(key,value):
            if len(dict_cache.keys())<k:
                dict_cache[key]=value
            else:
                dict_cache.popitem(last=False)
                dict_cache[key]=value
        v_lst=[]
        for lst in operators:
            if lst[0]==1:set(lst[1],lst[2])
            if lst[0]==2:
                v_lst.append(get(lst[1]))
        return v_lst

发表于 2021-11-27 00:36:01 回复(0)
Python 3
长琴搞事头像 长琴搞事 
from collections import OrderedDict
class Solution:
    
    def __init__(self):
        self.que = OrderedDict()
    
    def _check(self, k):
        if len(self.que) > k:
            first = list(self.que.keys())[0]
            self.que.pop(first)
        
    def _get(self, key):
        if key in self.que:
            self.que.move_to_end(key)
            return self.que.get(key)
        return -1
    
    def _set(self, key, val, k):
        self.que[key] = val
        self._check(k)
    
    def LRU(self , operators , k ):
        # write code here
        ret = []
        for tup in operators:
            if tup[0] == 2:
                ret.append(self._get(tup[1]))
            elif tup[0] == 1:
                self._set(tup[1], tup[2], k)
        return ret

发表于 2021-09-15 23:57:44 回复(0)
Python 3
sq6734头像 sq6734 
#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LRU(self , operators , k ):
        # write code here
        self.cache = {}
        self.cache_list = []
        self.capacity = k
        value_list=[]
        for i in operators:
            #print(i)
            if i[0] == 1:
                self.set(i[1], i[2])
            elif i[0] == 2:
                value_list.append(self.get(i[1]))
        return value_list
        
    def set(self, key, value):
        #如果缓存已存在，则删掉
        if key in self.cache_list:
            self.cache_list.remove(key)
            self.cache.pop(key)
        #如果缓存不存在，且缓存区满了，则删掉最早的一个
        elif len(self.cache_list) == self.capacity:
            self.cache.pop(self.cache_list.pop(0))
        #写入缓存
        self.cache_list.append(key)
        self.cache[key] = value

    def get(self, key):
        #命中缓存，则更新缓存位置
        if key in self.cache_list:
            self.cache_list.remove(key)
            self.cache_list.append(key)
            value = self.cache.pop(key)
            self.cache[key] = value
        #没有命中缓存，返回-1
        else:
            value = -1
        return value

发表于 2021-09-13 22:41:00 回复(0)
Python 3
sjqg头像 sjqg 
class Solution:
    def LRU(self , operators , k ):
        # write code here
        def find_corrsponding(l,n):
            temp=0
            l=l[::-1];length=len(l)
            for index,i in enumerate(l):
                if i[0]==n:
                    temp=1
                    return i[1],length-1-index
                else:
                    continue
            if temp==0:
                return -1,-1
            
            
        l=[];ans=[]
        for i in operators:
            if i[0]==1:
                l.append(i[1:])
            else:
                num,index=find_corrsponding(l,i[1])
                ans.append(num)
                if index!=-1:
                    pop_=l.pop(index)
                    l.append(pop_)
            if len(l)>k:
                l.pop(0)
        return ans

发表于 2021-09-04 16:41:51 回复(0)
Python 3
牛客329247131号头像 牛客329247131号 
# 采用hash表查找key，双向链表存储key,value，使get,set操作的时间复杂度都是O（1）。
class ListNode():
    def __init__(self, key=None, val=None):
        self.key = key
        self.val = val
        self.pre = None
        self.next = None

class LRUcache():
    def __init__(self, space):
        self.rest_space = space
        self.head = ListNode()
        self.tail = self.head
        self.memo = dict()

    def update(self, cur):
        if cur == self.tail:
            pass
        else:
            prenode = cur.pre
            nextnode = cur.next
            prenode.next = nextnode
            nextnode.pre = prenode
            # 更新到tail
            self.tail.next = cur
            cur.pre = self.tail
            self.tail = cur

    def set(self, key, value):
        if key not in self.memo:
            if self.rest_space == 0:
                del_node = self.head.next
                self.head.next = del_node.next
                if del_node.next == None:
                    self.tail = self.head
                else:
                    self.head.next.pre = self.head
                del self.memo[del_node.key], del_node
                self.rest_space += 1
            cur = ListNode(key, value)
            self.tail.next = cur
            cur.pre = self.tail
            self.tail = cur
            self.rest_space -= 1
            self.memo[key] = cur
        else:
            cur = self.memo[key]
            cur.val = value
            self.update(cur)

    def get(self, key):
        output = -1
        if key in self.memo:
            output = self.memo[key].val
            self.update(self.memo[key])
        return output

class Solution:
    def LRU(self , operators , k ):
        # write code here
        output = []
        lru = LRUcache(k)
        for elem in operators:
            if elem[0] == 1:
                lru.set(elem[1], elem[2])
            elif elem[0] == 2:
                temp = lru.get(elem[1])
                output.append(temp)
        return output

发表于 2021-09-04 15:30:50 回复(0)
Python 3
牛客874914440号头像 牛客874914440号
#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#

class node():
    def __init__(self,key,v):
        self.key=key
        self.value=v
    def getstr(self):
        stre=''+str(self.key)+ ','+ str(self.value)
        return stre
class Solution:
    def __init__(self):
        self.K=0
        self.size=0
        self.node=[]
    def LRU(self , operators , k ):
        self.K=int(k)
        res='['
        for o in operators:
            if o[0]==2:
                res+=str(self.get(o[1]))
                res+=','
            elif o[0]==1:
                self.set(o[1], o[2])
        res=res[:-1]
        res+=']'
        print(res)
    def set(self,key, value):
        n=node(key, value)
        self.node.insert(0,n)
        self.size+=1
        if self.size>self.K:
            self.node.pop()
    def get(self,key):
        i=0
        #print('ggggg')
        #for i in self.node:
         #   print(i.getstr())
        for n in self.node:
            if key==n.key:
                nm=n
                self.node.remove(n)
                self.node.insert(0,nm)
                return n.value
            elif n==self.node[-1]:
                return '-1'
            
        # write code here
a=input()
K=a[-1]
a=eval(a[:-2])
s=Solution()
s.LRU(a,K)
发表于 2021-08-10 17:13:26 回复(0)
Python 3
Love华为头像 Love华为
#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    
    def __init__(self):
        self.step_count = 0
        self.record = dict()
        self.step_record = dict()
    
    def set(self, key, val):
        self.record[key] = val
        self.step(key)
    
    def get(self, key):
        if key in self.record:
            self.step(key)
            return self.record[key]
        else:
            return -1
    
    def step(self, key):
        self.step_record[key] = self.step_count
        self.step_count +=1
    
    def del_least(self):
        rev = {k:v for v,k in self.step_record.items()}
        key = sorted(rev)[0]
        del self.record[rev[key]]
        del self.step_record[rev[key]]
    
    def LRU(self , operators, k):
        # write code here
        get_val = []
        for i in operators:
            if i[0] == 1:
                if len(self.record) == k:
                    self.del_least()
                self.set(str(i[1]), i[2])
            else:
                get_val.append(self.get(str(i[1])))
        return get_val
发表于 2021-07-17 15:29:36 回复(0)
Python 3
羽舞苍痕头像 羽舞苍痕 


class Solution:
    def LRU(self , operators , k ):
        # write code here
        result = []
        d1={}
        l1 = [] # 记录键的名称
        for op in operators:
            if op[0] == 1 and len(l1) < k:
                d1[str(op[1])] = op[2]
                l1.append(str(op[1]))
            elif op[0] == 1 and len(l1) >= k:
                rem = l1.pop(0)
                d1.pop(str(rem))
                d1[str(op[1])] = op[2]
                l1.append(str(op[1]))  # 
            elif op[0] == 2:
                if str(op[1]) in d1:
                    result.append(d1[str(op[1])])
                    l1.remove(str(op[1]))
                    l1.append(str(op[1]))
                else:
                    result.append(-1)
        return result
发表于 2021-07-16 16:16:45 回复(0)
提交观点

问题信息

模拟
难度：
14条回答 15539浏览

热门推荐

通过挑战的用户

相关试题

设计LRU缓存结构

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号