力扣146.LRU 缓存机制

才浅Coding攻略

发布于 2022-12-12 17:03:32

2160

发布于 2022-12-12 17:03:32

文章被收录于专栏：才浅coding攻略

阿巩

五一假期快乐~

小长假来了，你有没有计划趁这个时间去做点什么呢？这里阿巩分享一个治疗拖延症自用的方法，我叫它“5分钟治疗法”，当你将要决定拖延时告诉自己现在开始做只要5分钟就好，你会发现一旦你投入到这件事的研究中就远不止5分钟了，会越来越欲罢不能~

就5分钟，快去试试！好了，日拱一卒，让我们开始吧！

首先O(1)时间复杂度的查询第一时间想到哈希表，在Python中Dict字典底层是由Hash表实现，那如果我要进行lRUcache.put(2, 2)的操作，2已经存在在哈希表中，如何在常数时间内把它挑出来移到队尾呢？这时需要用到双向链表，Python中的Collections包中的有序字典OrderedDict就是基于哈希表和双向链表实现的，我们用它来实现LRU，OrderedDict可以按数据插入字典的顺序快速访问。

动手试试，代码如下：

from collections import OrderedDict


class LRUCache:

    def __init__(self, capacity):
        self.maxsize = capacity
        self.lrucache = OrderedDict()

    def get(self, key):
        # key在缓存中，返回key的值，并将key对应的item移至有序字典尾部,否则返回-1
        if key in self.lrucache:
            self.lrucache.move_to_end(key)
        else:
            return -1
        return self.lrucache[key]

    def put(self, key, value):
        # 如果存在,将key对应的item移至有序字典尾部，并重新赋值
        if key in self.lrucache:
            self.lrucache.move_to_end(key)
        self.lrucache[key] = value
        if len(self.lrucache) > self.maxsize:
            # 如果缓存区已满，弹出有序字典头部最久未使用的item
            self.lrucache.popitem(last=False)


lRUCache = LRUCache(2)
lRUCache.put(1, 1)
lRUCache.put(2, 2)
print(lRUCache.get(1))
lRUCache.put(3, 3)
print(lRUCache.get(2))
lRUCache.put(4, 4)
print(lRUCache.get(1))
print(lRUCache.get(3))
print(lRUCache.get(4))
# 输出：
# 1
# -1
# -1
# 3
# 4

END

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-04-30，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法