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

题目来源于力扣

理论基础

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
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!