146. LRU Cache

[huimeich]

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up: Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 / capacity / );

cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4

[huimeich]

def __init__(self, capacity: int):
    self.cap = capacity
    self.dic = collections.OrderedDict()

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

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

[huimeich]

class DlinkedNode: def init(self): self.key = 0 self.value = 0 self.prev = None self.next = None

class LRUCache:

def __init__(self, capacity: int):
    self.head = DlinkedNode()
    self.tail = DlinkedNode()
    self.head.next = self.tail
    self.tail.prev = self.head
    self.cap = capacity
    self.size = 0
    self.dic = {}

def move_to_end(self, node):
    p = node.prev
    n = node.next
    p.next = n
    n.prev = p
    self.insert_to_end(node)

def insert_to_end(self, node):
    p = self.tail.prev
    n = self.tail
    node.prev = p
    node.next = n
    p.next = node
    n.prev = node

def remove_head(self):
    p = self.head
    n = self.head.next.next
    node = self.head.next
    del self.dic[node.key]
    p.next = n
    n.prev = self.head

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

def put(self, key: int, value: int) -> None:
    if key in self.dic:
        node = self.dic[key]
        node.value = value
        self.move_to_end(node)
    else:
        node = DlinkedNode()
        node.key = key
        node.value = value
        self.insert_to_end(node)
        self.size += 1
        self.dic[key] = node
        if self.size > self.cap:
            self.remove_head()