Leetcode[146] LRU Cache
11 Nov 2015###Task1 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.
###Python ####DNode
class DNode(object):
def __init__(self, x, k):
self.val = x
self.key = k
self.prev = None
self.next = None
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.size = capacity
self.head = DNode(-1, -1)
self.tail = DNode(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
self.dic = dict()
def get(self, key):
"""
:rtype: int
"""
if key not in self.dic:
return -1
node = self.dic[key]
node.prev.next = node.next
node.next.prev = node.prev
self.move2Tail(node)
return node.val
def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: nothing
"""
if self.get(key) != -1:
self.dic[key].val = value
return
if len(self.dic) >= self.size:
del self.dic[self.head.next.key]
self.head.next = self.head.next.next
self.head.next.prev = self.head
node = DNode(value, key)
self.dic[key] = node
self.move2Tail(node)
def move2Tail(self, node):
self.tail.prev.next = node
node.prev = self.tail.prev
self.tail.prev = node
node.next = self.tail
####collections.OrderedDict()
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.size = capacity
self.dic = collections.OrderedDict()
def get(self, key):
"""
:rtype: int
"""
if key not in self.dic:
return -1
value = self.dic[key]
del self.dic[key]
self.dic[key] = value
return value
def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: nothing
"""
if key in self.dic:
del self.dic[key]
self.dic[key] = value
return
if len(self.dic) == self.size:
self.dic.popitem(last = False)
self.dic[key] = value
###Java
public class LRUCache {
class DNode {
DNode prev;
DNode next;
int val;
int key;
public DNode(int key, int val) {
this.key = key;
this.val = val;
}
}
HashMap<Integer, DNode> map = new HashMap<Integer, DNode>();
int capacity;
DNode head = new DNode(-1, -1);
DNode tail = new DNode(-1, -1);
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
DNode res = map.get(key);
res.prev.next = res.next;
res.next.prev = res.prev;
move2Tail(res);
return res.val;
}
public void set(int key, int value) {
if (get(key) != -1) {
map.get(key).val = value;
return;
}
if (map.size() == capacity) {
map.remove(head.next.key);
head.next = head.next.next;
head.next.prev = head;
}
DNode cur = new DNode(key, value);
map.put(key, cur);
move2Tail(cur);
return;
}
public void move2Tail(DNode node) {
tail.prev.next = node;
node.prev = tail.prev;
tail.prev = node;
node.next = tail;
}
}
###Points
- PAT: every set() will call get() instead of search in dict.key. Cause get() will re-order the structure.
- python black magic: ordered dict