LeetCode 146. LRU缓存机制

LeetCode 146. LRU缓存机制

Comments 0 Comment

题目描述

运用你所掌握的数据结构，设计和实现一个  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

题目的地址

中文版

英文版

 

 

用库函数实现

Java中的LinkedHashMap
Python中的OrderedDict
都是属于有“顺序”的map，他们有散列表的特点，同时元素的顺序是按照先进来的在前面，后进来的在后面这样存放的。
下图是一个有“顺序”的map内部存储结构
1:100，表示key为1，value为100
key=1 是最先放入的，key=4是最后放入的

当访问一个元素时
1.如果这个元素不在容器中，返回-1
2.如果在容器中，就返回这个值，同时还要将这个元素从容器中删除，再插入最后最后(最后一个位置代表是最新的)

当新插入一个元素
1.如果key在容器中，这时候还分为两种情况
容器满了，或者容器没满
我们可以统一处理这种情况，直接将这个元素删除就行了，之后再插入一次就行了
2.如果key不在容器中，这时候也分两种情况
容器满了，这时候我们要删除一个元素，直接删除容器最左边的元素就可以了
如果容器没满，啥也不用做
最后，将这个新元素插入即可

实现代码如下

                                                                                       
class LRUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        import collections
        # 我们创建一个self.d的变量，用来表示OrderedDict
        self.d = collections.OrderedDict()
        # 同时，还要记录容器的大小，当容器满的时候会用到这个变量做判断
        self.size = capacity
        
    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        # 当key在容器中时，首先获取这个元素，然后删除这个元素，再重新插入(重新插入到最右端)
        if(key in self.d):
            value = self.d[key]
            del self.d[key]
            self.d[key] = value
            return value
        # 如果key不在容器中，直接返回-1即可
        return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        # 如果key在容器中，这时候有两种情况，容器满了/或者没满，我们就将这个元素删除就行了
        # 因为删除完了就肯定会多出一个空位了，这样就可以插入元素了，然后最后收尾的时候将元素
        # 插入到容器右端就可以了
        if(key in self.d):
            del self.d[key]
            self.d[key] = value
        # 如果key不在容器中，同样也有两种情况，容器满了/或者没满，满的判断方式是
        # 容器的长度==self.size，如果没满就啥也不做直接添加，等加的元素足够多时，
        # 就会触发else里面的那个if判断了。
        # 之后删除容器最左边的元素(最老的元素)
        else:
            if(len(self.d)==self.size):
                self.d.popitem(False)
        # 统一处理，不管上面怎么操作，最后都将新元素插入到容器右端，页就是最新的位置
        self.d[key] = value

 

用双链表实现

LRU缓存需要两种数据结构，map和双链表
这里我们就自己手动构造一个双链表
map的key指向的value就是双链表中的一个节点(下面代码实现中的Node类)
双链表中的每个元素都是有pre(前驱)指针，next(后继)指针，我们通过tail尾节点就可以很快定位到最后一个元素，然后将这个元素删除(删除最久没有使用的元素)
同样，根据map中的key也可以快速定位到一个Node，然后找到这个Node的值并返回
双链表实现的数据结构如下

再看下面这个图，假设LRU现在有四个元素，key分别是3,1,5,2
当2这个元素被访问时，就要从双链表中删除，然后插入到双链表的最开头，至于map中的key不同
当插入一个元素，比如还是2:200(key和value跟以前一样)，此时要从双链表的最后删除一个元素，然后再新插入一个元素到双链表的最开头，当然map中的key也要删除，因为散列规则的原因，map中的2最后看起来还是放到了map中最后一个

代码实现如下：


# 增加一个Node类，用来表示双链表中的一个节点，其中每个节点有pre指针(指向上一个元素)，还有next
# 指针(指向下一个元素)，以及key和value，注意这里的key实际上是冗余了。当LRU缓存满了，我们要
# 删除双链表中最后一个元素，之后还要删除map中对应的元素，此时删除链表中的元素很容器，但删除
# map中的元素就不知道怎么办了，原因是map和双链表之间没有任何关联，所以这里冗余了一份key，用来
# 再删除map中对应的元素
class Node(object):
    def __init__(self,key=None,val=None):
        self.pre = None
        self.next = None
        self.key = key
        self.val = val
    
        
class LinkList(object):
    # 创建两个节点，head和tail，初始的时候 head <--> tail
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.pre = self.tail
        self.head.next = self.tail
        self.tail.pre = self.head
        self.tail.next = self.head
        
    # 将一个节点插入到双链表的最开头，这个操作用来表示Node节点是最新的
    def add_to_first(self,node):
        node.next = self.head.next
        self.head.next.pre = node
        node.pre = self.head
        self.head.next = node
    
    # 根据传入的node，删除双链表中的节点
    def delete(self,node):
        pre_node = node.pre
        next_node = node.next
        pre_node.next = next_node
        next_node.pre = pre_node
        node.pre = None
        node.next = None
    
    # 获取最后一个元素，当LRU缓存满时，就需要拿到最后一个元素然后删除       
    def get_last(self):
        return self.tail.pre

class LRUCache(object):
    # 创建三个变量，remian用于记录当前还有多少空闲位置，d是python内置的map
    # 还有一个link_list表示自定义的双链表
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.remain = capacity
        self.d = dict()
        self.link_list = LinkList()

    # 这个get()函数跟 用库函数实现的那个一样，也是key不再就直接返回-1
    # key存在了就获取这个元素，然后从self.d(也就是内置的map中)删除，再从双链表中删除
    # 最后将这个元素插入到双链表的最开头
    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if(key not in self.d):
            return -1
        node = self.d[key]
        self.link_list.delete(node)
        self.link_list.add_to_first(node)
        return node.val
  
    # put函数的逻辑其实跟 库函数实现的那一套类似，只是因为很多事情库函数帮我们去做了，所以
    # 自定义双链表去实现就需要多一些步骤        
    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        # 首先是key如果在LRU中，也就是self.d中，那就直接删除这个元素，最后再统一插入就可以
        if(key in self.d):
            tmp = self.d[key]
            self.link_list.delete(tmp)
            del self.d[tmp.key]
        # 如果key不在LRU中，这里也分为两种情况，LRU满了/或者LRU没满
        else:
            # 如果remain>0 就说明没满，remain--就可以了，最后收尾的时候会插入一个新元素
            if(self.remain > 0):
                if(key not in self.d):
                    self.remain -=1
            # 如果LRU满了，就需要从双链表中获取最后一个元素，然后删除
            # 这里可以将if-else直接改成一个if，类似上面用库函数的那种方式
            # if(len(slef.d)==self.remain) 就可以了
            else:
                tmp = self.link_list.get_last_node()
                del self.d[tmp.key]
                self.link_list.delete(tmp)
        # 最后统一插入新元素
        node = Node(key,value)
        self.d[key] = node
        self.link_list.add_to_first(node)

 

19 次阅读

发表评论

电子邮件地址不会被公开。