M-146. LRU Cache

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

# 其实思路很简单
# 首先, 两个类, 
# 1. 一个Node类, 存k, v, prev和next
# 2. 一个cache类, 维护一个doublely链表(初始化是一个head一个tail相连), 
# 一个cache字典, 装所有的{key: node} pair. 和一个cpacity变量存最大长度, 和一个size存当前长度.
#     1. put操作, 直接读cache, 如果有key存在, 更新node, 然后把node移到双列表head后面.
#    如果不存在, new一个, 然后写入cache字典, 并把它移动到双列表head后面. size+1, 
#    如果此时size超过capacity, pop(tail.prev), 然后size-1. 然后cache字典里面的pair也要移除.
#     2. get操作, 直接读cache, 如果有key存在, 获取node.val, 然后把它移动到head后面; 如果
#    不存在, 返回-1.

# 所以我们需要的函数有:
# 1. 在head后增加该node
# 2. 在node处删除该node
# 3. 从链表尾部pop一个node然后返回(可以复用2)
# 4. 把已经存在的一个node移动到head后面(可以复用2和1)
# 5. 获取node
# 6. put node

class DLinkedNode(): 
    def __init__(self, k = 0, v= 0):
        self.key = k
        self.value = v
        self.prev = None
        self.next = None
            
class LRUCache():
    def _add_node(self, node):
        """
        Always add the new node right after head.
        """
        self.head.next, node.next = node, self.head.next
        node.prev, node.next.prev = self.head, node 

    def _remove_node(self, node):
        """
        Remove an existing node from the linked list.
        """
        node.next.prev, node.prev.next  = node.prev, node.next
        
    def _move_to_head(self, node):
        """
        Move certain node in between to the head.
        """
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        """
        Pop the current tail.
        """
        res = self.tail.prev
        self._remove_node(res)
        return res

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = {}
        self.size = 0
        self.capacity = capacity
        self.head, self.tail = DLinkedNode(), DLinkedNode()

        self.head.next = self.tail
        self.tail.prev = self.head
        

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        node = self.cache.get(key)
        if not node:
            return -1

        # move the accessed node to the head;
        self._move_to_head(node)

        return node.value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        node = self.cache.get(key)

        if not node: 
            newNode = DLinkedNode(key, value)

            self.cache[key] = newNode
            self._add_node(newNode)

            self.size += 1

            if self.size > self.capacity:
                # pop the tail
                tail = self._pop_tail()
                self.cache.pop(tail.key)
                self.size -= 1
        else:
            # update the value.
            node.value = value
            self._move_to_head(node)