首页 > 试题广场 >

LRU Cache

[编程题]LRU Cache

热度指数：6018 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解


	设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作： get 和 put。

int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果key不存在，则返回-1。
void put(int key, int value) – 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。

请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。

限制：请在O(1)的时间复杂度内完成上述2个操作。

输入描述:

第一行读入一个整数n，表示LRU Cache的容量限制。 从第二行开始一直到文件末尾，每1行代表1个操作。

如果每行的第1个字符是p，则该字符后面会跟随2个整数，表示put操作的key和value。

如果每行的第1个字符是g，则该字符后面会跟随1个整数，表示get操作的key。

输出描述:

按照输入中get操作出现的顺序，按行输出get操作的返回结果。

示例1

输入

输出

说明

2        //Cache容量为2
p 1 1    //put(1, 1)
p 2 2    //put(2, 2)
g 1      //get(1), 返回1
p 2 102  //put(2, 102)，更新已存在的key，不算被使用
p 3 3    //put(3, 3)，容量超过限制，将最近最少使用的key=2清除
g 1      //get(1), 返回1
g 2      //get(2), 返回-1
g 3      //get(3), 返回3

算法知识视频讲解

Python

比杨德布鲁

思路: HashMap + 双向链表

关键:

1. 当 capacity 为 0 时, 需要让 put 操作无效, 而 get 操作返回 -1. 不能让 LRUCache 在遇到 < 1 的 capacity 时, 初始化失败

2. 为避免链表中增删时的边界判断条件, 可以建立head 和 tail 两个哑节点, 无论如何操作链表中至少有这两个节点存在

class ListNode:
    def __init__(self, key=None, val=None):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None
        
class LRUCache:
    
    def __init__(self, capacity):
        self.size = capacity 
        self.hashmap = {}
        # 建立 head 和 tail 两个哑节点, 可以有效减少边界判断
        self.head = ListNode()
        self.tail = ListNode()
        
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def add_node(self, node):
        """
        每次 append node 至链表尾
        """
        node.next = self.tail
        node.prev = self.tail.prev
        self.tail.prev.next = node
        self.tail.prev = node
        
    def remove_most_unused_node(self):
        self.hashmap.pop(self.head.next.key)
        self.head.next = self.head.next.next
        self.head.next.prev = self.head 
        
    def move_node_to_tail(self, node):
        # 断开当前 node
        node.prev.next = node.next
        node.next.prev = node.prev
        
        self.add_node(node)
    
    def get(self, key):
        if key in self.hashmap:
            node = self.hashmap[key]
            self.move_node_to_tail(node)
            return node.val
        return -1
    
    def put(self, key, val):
        if key in self.hashmap:
            self.hashmap[key].val = val
        else:
            if self.size == len(self.hashmap):
                self.remove_most_unused_node()

            newNode = ListNode(key, val)
            self.hashmap[key] = newNode
            self.add_node(newNode)
        


if __name__ == "__main__":
    n = int(input())
    lru = LRUCache(n)
    while True:
        try:
            line = input().split()
        except: # 遇到 EOF, break
            break
        if line[0] == 'p':
            if lru.size <= 0: continue
            lru.put(int(line[1]), int(line[2]))
        if line[0] == 'g':
            ret = lru.get(int(line[1]))
            print(ret)

发表于 2020-11-14 11:54:30 回复(0)

Python

杀生院

#整体思路是利用双链表和python的dict来完成
#dict的value纪录链表对应的节点
#链表的节点每被get一次就从链表里删除再插入到链表头，确保链表尾是最不常用的
#当链表的长度到达阈值，在put新的key值的节点前先把链表尾的节点出去即可
#get和put的时间复杂度都是O(1)
class Node(object):
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None
class LRU(object):
    def __init__(self,capacity):
        self.head = Node(0,0)
        self.tail = Node(0,0)
        self.head.next = self.tail
        self.tail.pre = self.head
        self.capacity = capacity
        self.count = 0
        self.map = dict()
        
    def add_node(self,node):
        node.next = self.head.next
        self.head.next = node
        node.pre = self.head
        node.next.pre = node
        return node
        
    def remove_node(self,node):
        node.pre.next = node.next
        node.next.pre = node.pre
        
    def pop_node(self):
        pop_node = self.tail.pre
        self.tail.pre.pre.next = self.tail
        self.tail.pre = self.tail.pre.pre
        return pop_node
    
    def get(self,key):
        res = self.map.get(key)
        if res:
            self.remove_node(res)
            self.add_node(res)
            return res.value
        else:
            return -1
        
    def put(self,key,value):
        if self.capacity == 0:
            return None
        res = self.map.get(key)
        if res:
            res.value = value
            
        else:
            if self.count>= self.capacity:
                pop_node = self.pop_node()
                self.map.pop(pop_node.key)
                self.count-=1
            node = Node(key,value)
            self.add_node(node)
            self.map[key] = node
            self.count+=1
            
def main():
    n = int(input())
    l = LRU(n)
    try:
        while True:
            line = input().split()
            if line == []:
                break
            if line[0] == 'p':
                l.put(int(line[1]),int(line[2]))
            elif line[0] == 'g':
                res = l.get(int(line[1]))
                print(res)
    except:
        pass

main()

发表于 2019-12-09 15:55:08 回复(0)