题解 | #设计LRU缓存结构#

思路

题目分析

题目希望我们设计一个LRU规则来处理<key，value>数据
对于一个数据结构，LRU规则在该结构上的要求是：

该数据结构有一个最大的容量值，可储存的数据不超过这个值
对于set操作，该数据结构目的就是将<key,value>存入数据结构中，并标记其为最近最新访问
对于get操作，该数据结构目的就是对其要求访问的key返回对应的value值

题目中给出了二维数组，其中对于每一个子数组opt[]，opt[0] == 1表示要执行set操作，opt[0] == 2表示要执行get操作。
在设计结构的时候还要兼顾是否越界、是否有同key不同value等细节问题

首先python中集成了结合哈希表和双向链表的数据结构OrderedDict，在Java中同样有类似的结构LinkedHashMap，有很多方便的接口可以让我们使用。Python的用例方案见方法一。
然后该题具体分析就要求我们采用自己建立这种数据结构的方式。
- 我们当遇到操作是set时：
  - 首先判断key是否在哈希表中
    - 如果在哈希表中则根据哈希表读取结点，然后将结点的val值更新并移动到双向链表首位
    - 如果不在哈希表中则新建一个节点插入到双向链表首位，更新当前size，然后判断是否超过了最大容量，超过容量则退出末尾的结点，并在哈希表中删除它。
- 我们当遇到操作是get时：
  - 首先判断key是否在哈希表中
    - 如果key在哈希表中则读取其val值到返回列表中，并且更新其位置到双向链表首位
    - 如果key不在哈希表中则返回-1到返回列表中

图片说明

方法一：使用python内置数据结构

#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
import collections
class Solution:
    def LRU(self , operators , k ):
        # write code here
        res = []
        d = collections.OrderedDict()
        d.capacity = k
        for op in operators:
            if op[0] == 1:                        # 表示要set
                if op[1] in d:                    # 如果当前key在d中
                    d.move_to_end(op[1])          # 则移到末尾
                d[op[1]] = op[2]                  # 更新key,value的值
                if len(d) > k:                    # 如果数量超过了上界则踢出队首的
                    d.popitem(last = False)       # 则踢出最前面的key,value
            else :                                # 表示要get
                if op[1] not in d:                # 如果key不存在
                    res.append(-1)                # 则输出-1
                else:                             # 如果key存在
                    res.append(d[op[1]])          # 输出value
                    d.move_to_end(op[1])          # 并移到末尾
        return res

复杂度分析

时间复杂度：对于哈希+双向链表的内置数据结构，时间复杂度为 $O(1)$
空间复杂度：空间上借助了哈希表和双向链表结构，空间复杂度取决于链表长，则为 $O(n)$

方法二：手动打造双向列表的结构，配合哈希表使用

#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
# 结点
class DLinkedNode:
    def __init__(self, key = 0, val = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

# 双向链表
class LRU:
    def __init__(self, capacity:int):
        self.cache = dict()
        # 头结点和尾结点都是伪结点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        # 先连接起来首尾
        self.head.next = self.tail
        self.tail.prev = self.head
        # 设定LRU的最大容量
        self.capacity = capacity
        self.size = 0

    # 当opt=2的时候调用get函数
    def get(self, key:int) -> int:
        if key not in self.cache:
            return -1
        # key存在的情况下，首先通过哈希表定位然后将结点移动到头部
        node = self.cache[key]
        # 将结点node取出
        node.prev.next = node.next
        node.next.prev = node.prev
        # 移到首位操作
        node.prev = self.head
        node.next = self.head.next
        node.next.prev = node
        node.prev.next = node
        return node.val

    # 当opt=1的时候调用put函数
    def put(self, key:int, val:int) -> None:
        # 如果key不存在
        if key not in self.cache:
            node = DLinkedNode(key, val)    # 新建一个节点
            self.cache[key] = node          # 放入哈希表中
            node.prev = self.head
            node.next = self.head.next
            node.next.prev = node
            node.prev.next = node            # 添加到双向链表头
            self.size += 1                  # 双向链表的结点数+1
            if self.size > self.capacity:
                # 双向链表的长度大于最大的容量
                node = self.tail.prev
                # 移除最后一个节点
                node.prev.next = node.next
                node.next.prev = node.prev
                self.cache.pop(node.key)
                self.size -= 1
        # key存在则首先通过哈希表找到key，然后修改val，并挪到头部
        else:
            node = self.cache[key]
            node.val = val
            # 将结点node取出
            node.prev.next = node.next
            node.next.prev = node.prev
            # 移动node到首位
            node.prev = self.head
            node.next = self.head.next
            node.next.prev = node
            node.prev.next = node

class Solution:
    def LRU(self , operators , k ):
        # write code here
        res = []
        linklist = LRU(k)
        for opt in operators:
            if opt[0] == 1:
                linklist.put(opt[1], opt[2])
            else:
                res.append(linklist.get(opt[1]))
        return res

复杂度分析

时间复杂度：对于哈希+双向链表的内置数据结构，put方法和get方法的时间复杂度为 $O(1)$
空间复杂度：空间上借助了哈希表和双向链表结构，空间复杂度取决于链表长，则为 $O(n)$