美文网首页
[leetcode] LRU缓存机制

[leetcode] LRU缓存机制

作者: 菜鸟瞎编 | 来源:发表于2019-06-15 21:23 被阅读0次

    https://leetcode-cn.com/problems/lru-cache/

    思路:
    这道题的关键是最近最少使用。“最少使用”就是说使用的次数越少越有可能被清除,“最近最少使用”说明,长时间没有使用的变量,即使使用次数很多也有可能被清除,因为最近没有被使用。

    给每个 key 记录一个 cnt 值。每发生一次对这个key的操作(get 或 put),这个 cnt 就加1(新 key ,cnt初始化为1)。每发生一次 get 或 put 操作,将其他无关的 key 的值减去 1 (时间衰减),但是这样操作太没有效率, 所以维护一个时间变量time,每次有get或者put操作就给time 加1,同时对每个 key 加一个变量 latest_time记录最后使用时间。
    当空间不够需要删除变量时,就将每个变量的 cnt-(time - latest_time)值进行排序,删除值最小的那个。为了使删除操作更有效率,可以使用堆排序算法。

    进阶
    题目要求 O(1)时间复杂度。上面的思路行不通。

    get操作的时间要为O(1),考虑用哈希表查找,但不能用哈希表本身去存储,否则就失去了缓存机制本身的意义。put操作为O(1),考虑用链表。
    所以整体的思路大概是这样的,在哈希表中存储链表指针,在链表中存储value。每次访问一个key之后,就将对应的链表节点移动到最末端。这样能保证最近访问的在末端,长时间没访问的在链表头部,删除节点时从头部删除,从尾部插入。
    为了避免反复新建新节点,可以使用循环链表,首尾相连,这样在删除节点时只需要移动头部节点的位置即可。
    为了提高链表的访问速度,可以分配连续的内存,用数组构造链表。
    从这道题具体来看int get(int key) key是int型 ,因为链表指针占据空间很小,因此可以使用 直接寻址表 建哈希表。其他建哈希表的方法还有散列法、链接法。

    相关文章

      网友评论

          本文标题:[leetcode] LRU缓存机制

          本文链接:https://www.haomeiwen.com/subject/elsifctx.html