力扣146. LRU 缓存
1、C
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); */
2、C++
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); */
3、JAVA
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); */
4、Python
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)标签:tmp,缓存,self,tail,算法,right,LRU,key,left From: https://www.cnblogs.com/cmkbk/p/17393408.html