最近使用的放在链表尾部

哈希表 + 双向链表

class DListNode:
    def __init__(self, x=0, y=0):
        self.key = x
        self.value = y
        self.pre = None
        self.next = None

class Solution:
    def __init__(self):
        self.head = DListNode()
        self.tail = DListNode()
        self.head.next = self.tail
        self.tail.pre = self.head
        self.cache = dict()

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.move_to_end(node)
        return node.value

    def set(self, key, value, k):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_end(node)
        else:
            node = DListNode(key, value)
            self.cache[key] = node
            self.add_to_end(node)
            if len(self.cache) > k:
                removed = self.head.next
                self.remove(removed)
                del self.cache[removed.key]

    def remove(self, node):
        node.pre.next = node.next
        node.next.pre = node.pre

    def add_to_end(self, node):
        node.pre = self.tail.pre
        node.next = self.tail
        self.tail.pre.next = node
        self.tail.pre = node

    def move_to_end(self, node):
        self.remove(node)
        self.add_to_end(node)

    def LRU(self, operators, k):
        res = []
        for opt in operators:
            if opt[0] == 1:
                self.set(opt[1], opt[2], k)
            elif opt[0] == 2:
                res.append(self.get(opt[1]))
        return res

有序字典

from collections import OrderedDict
class Solution:
    def __init__(self):
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def set(self, key, value, k):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > k:
            self.cache.popitem(last=False)

    def LRU(self, operators, k):
        res = []
        for opt in operators:
            if opt[0] == 1:
                self.set(opt[1], opt[2], k)
            elif opt[0] == 2:
                res.append(self.get(opt[1]))
        return res