P4 LRU缓存机制 LeetCode146

字数统计: 973字 | 阅读时长: 4分

2019-09-07

P4 LRU缓存机制，难度中等，主要标签为LRU设计。

题目

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

LeetCode题目链接https://leetcode-cn.com/problems/lru-cache/

解题思路

20190907记录

主要思想为，维护一个有序字典，最近最久未使用的处于字典首部。

获取数据get(self, key)判断key是否存在，如存在，在字典中弹出已存在的key-value，再向字典中重新添加key-value，并返回value。（此时，key-value最近被使用，处在字典尾部）。

写入数据put(self, key, value)判断key是否存在，如存在，在字典中弹出已存在的key-value，如果key不在缓存字典中，且字典达到上限，弹出最近最久未使用字典首元素。最后向字典中添加新提供的key-value。（此时，新提供的key-value新加入字典，属于最近被使用，处于字典尾部）。

解题代码：

import collections
class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.dict = collections.OrderedDict()  # 有序字典

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.dict:  # 如果key在缓存字典中
            value = self.dict.pop(key)  # 弹出key-value对
            self.dict[key] = value  # 重新加入key-value对，此时处于有序字典尾部
            return value
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        # 如果key在缓存字典中，弹出
        if key in self.dict:
            self.dict.pop(key)
        else:
            # 如果key不在缓存字典中，且字典达到上限，弹出最近最久未使用字典首元素
            if len(self.dict) >= self.capacity:
                self.dict.popitem(last=False)
        # 加入key-value
        self.dict[key] = value

测试方法：

# Your LRUCache object will be instantiated and called as such:
obj = LRUCache(2)
obj.put(2,1)
obj.put(2,2)
print(obj.get(2))

输出：

积累

Python collections有序字典（OrderedDict）

OrderedDict记录了字典元素的添加顺序。

def clear(self): # real signature unknown; restored from __doc__
    """ 
　　　　od.clear() -> None.  Remove all items from od. 
　　　　清除有序字典中的元素
　　"""
    pass

def copy(self): # real signature unknown; restored from __doc__
    """ 
　　　　od.copy() -> a shallow copy of od 
　　　　有序字典的浅拷贝
　　"""
    pass

def items(self, *args, **kwargs): # real signature unknown
    # 取有序字典的元素
　　 pass

def keys(self, *args, **kwargs): # real signature unknown
　　# 取key
    pass

def move_to_end(self, *args, **kwargs): # real signature unknown
    """
    Move an existing element to the end (or beginning if last==False).
    
            Raises KeyError if the element does not exist.
            When last=True, acts like a fast version of self[key]=self.pop(key).
　　把指定的元素放到尾部
    """
    pass

def pop(self, k, d=None): # real signature unknown; restored from __doc__
    """
    od.pop(k[,d]) -> v, remove specified key and return the corresponding
            value.  If key is not found, d is returned if given, otherwise KeyError
            is raised.
　　弹出指定的key
    """
    pass

def popitem(self): # real signature unknown; restored from __doc__
    """
    od.popitem() -> (k, v), return and remove a (key, value) pair.
            Pairs are returned in LIFO order if last is true or FIFO order if false.
　　从尾部开始弹出
    """
    pass

本文作者： Yao Zhu
发布时间： 2019-09-07
最后更新： 2019-09-22
本文链接： https://juoyo.github.io/posts/a89a7d98.html
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！