塔子哥有一门专业课,叫做操作系统,简称OS。操作系统的页式存储管理中,当主存满并且需要的存储页不在主存中,需要对主存中的页面进行置换,其中有一个非常重要的算法,即LRU置换算法。
LRU (Least Recently Used)缓存算法理一种常用于管理缓存的策略,其目标是保留最近使用过的数据,而淘汰最久未被使用的数据。实现简单的LRU缓存算法,支持查询、插入、删除操作。
给定一个缓存最多存放N页,输入K次操作,操作包括插入(A)、查询(Q)和删除(D)。插入时如果页面已存在则刷新访问时间,否则插入新页面,若超过容量N则淘汰最久未使用页面。查询和删除操作也会刷新页面的访问时间。最后输出缓存内页面编号,按LRU(最近最少使用)顺序排列。
双向链表 + 哈希表
这是一道经典原题146. LRU缓存 。