146. LRU Cache

link

The concept is about double linked list.

k1, k2, k3.... k10 -> k1, k2, k4, ..... k10, k3 -> k2 , k4 , k5 .... k10 , k3 , k11

Custom double linked list

class Node:
    def __init__(self, val):
        self.val = val
        self.pre = None
        self.nxt = None

class LRUCache:

    def __init__(self, capacity: int):
        self.M = defaultdict(int)
        self.cache = {}
        self.capacity = capacity
        self.head = Node(-1)
        self.tail = Node(-1)
        self.head.nxt = self.tail
        self.tail.pre = self.head

    def _remove(self, node):
        pre, nxt = node.pre, node.nxt
        pre.nxt, nxt.pre = nxt, pre
        # node.pre.nxt, node.nxt.pre = node.nxt, node.pre

    def get(self, key: int) -> int:
        if key not in self.M:
            return -1

        node = self.cache[key]

        self._remove(node)

        # put it to tail
        node.nxt = self.tail
        node.pre = self.tail.pre
        node.nxt.pre = node
        node.pre.nxt = node

        return self.M[key]

    def put(self, key: int, value: int) -> None:
        if key not in self.M:
            node = Node(key)
            self.cache[key] = node
        else:
            node = self.cache[key]
            self._remove(node)

        self.M[key] = value

        # put it to tail
        node.nxt = self.tail
        node.pre = self.tail.pre
        node.nxt.pre = node
        node.pre.nxt = node
        

        if len(self.M.keys()) > self.capacity:
            node = self.head.nxt
            self._remove(node)

            del self.M[node.val]
            del self.cache[node.val]

Use built-in function, see cheat sheet

class LRUCache:

    def __init__(self, capacity: int):
        self.od = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.od:
            return -1
        
        self.od.move_to_end(key)

        return self.od[key]

    def put(self, key: int, value: int) -> None:
        if key in self.od:
            self.od.move_to_end(key)
        elif len(self.od) == self.capacity:
            self.od.popitem(last=False)
        
        self.od[key] = value