菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
0
0

算法题:设计和实现一个 LRU Cache 缓存机制

原创
05/13 14:22
阅读数 468

理论基础

LRU 算法、Cache

实现 LRU Cache 缓存机制

题目描述

设计和实现一个 LRU Cache 缓存机制

解题思路

  1. least recently used 最近最少使用 (被淘汰)
  2. Double LinkedList (双向链表)
  3. O (1) 查询头部
  4. O (1) 修改、更新
  5. 实现读、写缓存的操作

Python 解法

class LRUCache(object):

    def __init__(self, capacity):
        self.dic = collection.OrderedDict()
        self.remain = capacity

    def get(self, key):
        if key not in self.dic:
            return -1
        v = self.dic.pop(key)
        self.dic[key] = v  # 把当前访问的key设置为最新
        return v

    def put(self, key, value):
        if key in self.dic:
            self.dic.pop(key)
        else:
            if self.remain > 0:
                self.remain -= 1
            else:  # 如果容量已满
                self.dic.popitem(last=False) # 删除最后一个键值对
        self.dic[key] = value

发表评论

0/200
0 点赞
0 评论
收藏
为你推荐 换一批