LeetCode 146. LRU缓存机制

LeetCode 146. 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

题目的地址

中文版

英文版

 

 

用库函数实现

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 次阅读

发表评论

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