首页 > 代码库 > #Leet Code# LRU Cache
#Leet Code# LRU Cache
语言:C++
描述:使用单链表实现,HeadNode是key=-1,value=http://www.mamicode.com/-1,next=NULL的结点。距离HeadNode近的结点是使用频度最小的Node。
1 struct Node { 2 int key; 3 int value; 4 Node* next; 5 }; 6 7 class LRUCache { 8 public: 9 LRUCache(int capacity) {10 this->capacity = capacity;11 this->curLength = 0;12 13 this->headNode = new Node();14 this->headNode->key = -1;15 this->headNode->value = http://www.mamicode.com/-1;16 this->headNode->next = NULL;17 18 this->lastNode = this->headNode;19 }20 21 int get(int key) {22 if (this->curLength == 0)23 return -1;24 25 Node* tmpNode = reSequencing(key, -1); 26 if (tmpNode != NULL) {27 return tmpNode->value;28 } else {29 return -1;30 }31 }32 33 void set(int key, int value) {34 if (this->capacity == 0) return;35 36 Node* tmpNode = reSequencing(key, value); 37 if (tmpNode != NULL) {38 tmpNode->value =http://www.mamicode.com/ value;39 return;40 } 41 42 if (this->curLength + 1 > this->capacity) {43 if (this->headNode->next == this->lastNode) {44 delete this->lastNode;45 this->lastNode = this->headNode;46 } else {47 Node* t = this->headNode->next->next;48 delete this->headNode->next;49 this->headNode->next = t;50 }51 }52 53 Node* newNode = new Node();54 newNode->key = key;55 newNode->value =http://www.mamicode.com/ value;56 newNode->next = NULL;57 58 this->lastNode->next = newNode;59 this->lastNode = newNode;60 61 curLength += 1;62 }63 64 Node* reSequencing(int key, int value) {65 Node* tmpNode = this->headNode;66 Node* preNode;67 68 while (tmpNode != NULL) {69 if (tmpNode->key == key) {70 break;71 }72 73 preNode = tmpNode;74 tmpNode = tmpNode->next;75 }76 77 if (tmpNode != NULL && this->lastNode->key != key) {78 preNode->next = tmpNode->next;79 80 this->lastNode->next = tmpNode;81 this->lastNode = tmpNode;82 tmpNode->next = NULL;83 } 84 85 return tmpNode;86 }87 88 private:89 int capacity;90 int curLength;91 92 Node* headNode;93 Node* lastNode;94 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。