LRU Cache
Intuition
Solution
#!/usr/bin/python
# coding=utf-8
#
# Title: 146, LRU Cache
# Author: Lucas
# Date: 2018-04-30 11:47:42
#
class Node(object):
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
self.prev = None
def __repr__(self):
return "<Node %d: %d>" % (self.key, self.val)
class LRUCache:
def __init__(self, capacity):
"""
:type capacity: int
"""
self.newest = Node(-2, -2)
self.oldest = Node(-3, -3)
self.newest.next = self.oldest
self.oldest.prev = self.newest
self.len = 0
self.cap = capacity
self.location = {}
def _remove(self, node):
"""Remove from list"""
node.prev.next = node.next
node.next.prev = node.prev
node.prev = None
node.next = None
def _add(self, node):
node.next = self.newest.next
node.prev = self.newest
self.newest.next.prev = node
self.newest.next = node
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.location:
return -1
node = self.location[key]
self._remove(node)
self._add(node)
return node.val
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if key in self.location:
self.location[key].val = value
self.get(key)
return
if self.cap == 0:
return
if self.len >= self.cap:
del self.location[self.oldest.prev.key]
self._remove(self.oldest.prev)
self.len -= 1
node = Node(key, value)
self._add(node)
self.location[key] = node
self.len += 1
if __name__ == '__main__':
obj = LRUCache(2)
obj.put(2, 1)
obj.put(2, 2)
print(obj.get(2))
obj.put(1, 1)
obj.put(4, 1)
print(obj.get(2))