typedef struct {
int key;
int val;
UT_hash_handle hh;
} LRUCache;
LRUCache* usr = NULL;
int size = 0;
LRUCache* lRUCacheCreate(int capacity) {
size = capacity;
return usr;
}
int lRUCacheGet(LRUCache* obj, int key) {
LRUCache *tmp = NULL;
HASH_FIND_INT(usr,&key,tmp);
if(tmp){
HASH_DEL(usr,tmp);
HASH_ADD_INT(usr,key,tmp);
return tmp->val;
}
return -1;
}
void lRUCachePut(LRUCache* obj, int key, int value) {
LRUCache *tmp = NULL;
HASH_FIND_INT(usr,&key,tmp);
if(tmp){
HASH_DEL(usr,tmp);
tmp->val = value;
HASH_ADD_INT(usr,key,tmp);
}
else{
int count = HASH_COUNT(usr);
LRUCache* tmp,*next;
if(size==count){
HASH_ITER(hh,usr,tmp,next){
HASH_DEL(usr,tmp);
free(tmp);
break;
}
}
LRUCache* newtmp = (LRUCache*)malloc(sizeof(LRUCache));
newtmp->key = key;
newtmp->val =value;
HASH_ADD_INT(usr,key,newtmp);
}
}
void lRUCacheFree(LRUCache* obj) {
LRUCache* tmp,*next;
HASH_ITER(hh,usr,tmp,next){
HASH_DEL(usr,tmp);
free(tmp);
}
}
/**
* Your LRUCache struct will be instantiated and called as such:
* LRUCache* obj = lRUCacheCreate(capacity);
* int param_1 = lRUCacheGet(obj, key);
* lRUCachePut(obj, key, value);
* lRUCacheFree(obj);
*/
class LRUCache {
public:
struct Node{
int key;
int val;
Node* left,*right;
Node():key(0), val(0), left(NULL), right(NULL) {}
};
Node* head = NULL;
Node* tail = NULL;
unordered_map<int,Node*> hash;
int n = 0;
LRUCache(int capacity) {
n = capacity;
head = new Node();
tail = new Node();
head->right = tail;
tail->left = head;
}
int get(int key) {
if(hash.count(key)){
hash[key]->right->left = hash[key]->left;
hash[key]->left->right = hash[key]->right;
hash[key]->left = tail->left;
tail->left->right = hash[key];
hash[key]->right = tail;
tail->left = hash[key];
return hash[key]->val;
}
return -1;
}
void put(int key, int value) {
if(hash.count(key)){
hash[key]->right->left = hash[key]->left;
hash[key]->left->right = hash[key]->right;
hash[key]->val = value;
hash[key]->left = tail->left;
tail->left->right = hash[key];
hash[key]->right = tail;
tail->left = hash[key];
}
else{
if(hash.size()==n){
Node * tmp = head->right;
tmp->right->left = tmp->left;
tmp->left->right = tmp->right;
hash.erase(tmp->key);
delete tmp;
}
Node *tempNode = new Node();
tempNode->val = value;
tempNode->key = key;
tempNode->left = tail->left;
tail->left->right = tempNode;
tempNode->right = tail;
tail->left = tempNode;
hash[key] = tempNode;
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
class LRUCache {
class Node{
int key;
int val;
Node left;
Node right;
Node(){
key = -1;
val = -1;
left = null;
right = null;
}
}
int n = 0;
Node head = null;
Node tail = null;
Map<Integer,Node> map = new HashMap<Integer,Node>();
public LRUCache(int capacity) {
n = capacity;
head = new Node();
tail = new Node();
head.right = tail;
tail.left = head;
}
public int get(int key) {
if(map.containsKey(key)){
Node tmp = map.get(key);
tmp.left.right = tmp.right;
tmp.right.left = tmp.left;
tmp.left = tail.left;
tmp.left.right = tmp;
tail.left = tmp;
tmp.right = tail;
return tmp.val;
}
return -1;
}
public void put(int key, int value) {
if(map.containsKey(key)){
Node tmp = map.get(key);
tmp.left.right = tmp.right;
tmp.right.left = tmp.left;
map.get(key).val = value;
tmp.left = tail.left;
tmp.left.right = tmp;
tail.left = tmp;
tmp.right = tail;
}
else{
if(n==map.size()){
Node tmp = head.right;
tmp.left.right = tmp.right;
tmp.right.left = tmp.left;
map.remove(tmp.key);
}
Node tmp = new Node();
tmp.key = key;
tmp.val = value;
map.put(key,tmp);
tmp.left = tail.left;
tmp.left.right = tmp;
tmp.right = tail;
tail.left = tmp;
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
class Node(object):
def __init__(self,key,value,left=None,right=None):
self.key = key
self.val = value
self.left = left
self.right = right
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.m = {}
self.n = capacity
self.head = Node(-1,-1)
self.tail = Node(-1,-1)
self.head.right = self.tail
self.tail.left = self.head
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key in self.m:
tmp = self.m[key]
tmp.left.right = tmp.right
tmp.right.left = tmp.left
tmp.left = self.tail.left
self.tail.left.right = tmp
tmp.right = self.tail
self.tail.left = tmp
return self.m[key].val
return -1
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in self.m:
tmp = self.m[key]
tmp.left.right = tmp.right
tmp.right.left = tmp.left
tmp.val = value
tmp.left = self.tail.left
self.tail.left.right = tmp
tmp.right = self.tail
self.tail.left = tmp
else:
if self.n==len(self.m):
tmp = self.head.right
tmp.left.right = tmp.right
tmp.right.left = tmp.left
del self.m[tmp.key]
tmp = Node(key,value)
tmp.left = self.tail.left
self.tail.left.right = tmp
tmp.right = self.tail
self.tail.left = tmp
self.m[key] = tmp
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)