题解 | #设计LFU缓存结构#
设计LFU缓存结构
https://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * lfu design * @param operators int整型二维数组 ops * @param operatorsRowLen int operators数组行数 * @param operatorsColLen int* operators数组列数 * @param k int整型 the k * @return int整型一维数组 * @return int* returnSize 返回数组行数 */ #include <stdio.h> #include <string.h> struct ListTable{ int key; int value; struct ListTable *last; struct ListTable *next; int count; }; typedef struct List{ int capacity; int NodeNum; //struct ListTable *HashTable[2000000001]; struct ListTable *head,*end; } Solution; struct ListTable* searchMinCountNode(Solution* obj) { struct ListTable* p; int Min=100001; p = obj->head; while(p!=NULL) { if(Min > p->count) Min = p->count; p = p->next; } p = obj->head; while(p->next!=NULL) { if(Min == p->count) return p; p = p->next; } return obj->head; } struct ListTable* searchNode(Solution* obj, int key) { struct ListTable* p = obj->head; while(p!=NULL) { if(p->key == key) return p; p = p->next; } return NULL; } void SubNode(Solution* obj, int key, struct ListTable* HashTable) { if(HashTable==obj->head){ obj->head = obj->head->next; obj->head->last = NULL; } else if(HashTable==obj->end) { obj->end = HashTable->last; obj->end->next = NULL; } else { HashTable->last->next = HashTable->next; HashTable->next->last = HashTable->last; } HashTable->next = NULL; HashTable->last = NULL; } void AddEndNode(Solution* obj, int key, int value, struct ListTable* HashTable) { obj->end->next = HashTable; HashTable->last = obj->end; HashTable->next = NULL; obj->end = HashTable; HashTable->key = key; HashTable->value = value; } Solution* SolutionCreate(int capacity) { int i; Solution *res; res = (Solution*)malloc(sizeof(Solution)); res->capacity = capacity; res->NodeNum = 0; res->head = NULL; res->end = NULL; return res; } int SolutionGet(Solution* obj, int key) { struct ListTable* HashTable = searchNode(obj, key); if(HashTable == NULL) return -1; if(HashTable!=obj->end) { SubNode(obj, key, HashTable); AddEndNode(obj, key, HashTable->value, HashTable); } HashTable->count++; return HashTable->value; } void SolutionPut(Solution* obj, int key, int value) { struct ListTable* HashTable = searchNode(obj, key); if(obj->head == NULL) { obj->head = (struct ListTable*)malloc(sizeof(struct ListTable)); obj->end = obj->head; obj->head->key = key; obj->head->value = value; obj->head->last = NULL; obj->head->next = NULL; obj->head->count = 1; obj->NodeNum = 1; } else { if(HashTable == NULL) { struct ListTable* NewNode; NewNode = (struct ListTable*)malloc(sizeof(struct ListTable)); obj->NodeNum++; NewNode->count = 1; AddEndNode(obj, key, value, NewNode); } else { if(HashTable == obj->end){ HashTable->value = value; HashTable->count++; } else { SubNode(obj, key, HashTable); AddEndNode(obj, key, value, HashTable); HashTable->count++; } } if(obj->NodeNum > obj->capacity) { struct ListTable* p = obj->head; p = searchMinCountNode(obj); SubNode(obj, p->key, p); free(p); obj->NodeNum--; } } } void SolutionFree(Solution* obj) { int i; struct ListTable* p = obj->head; for(i=0; i<obj->NodeNum-1; i++) { struct ListTable* last=p; p = p->next; free(last); } free(obj); } int* LFU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) { Solution *obj = SolutionCreate(k); int i, *res; res = (int*)malloc(100000*sizeof(int)); (*returnSize) = 0; for(i=0; i<operatorsRowLen; i++) { if(operators[i][0]==1) SolutionPut(obj, operators[i][1], operators[i][2]); else res[(*returnSize)++] = SolutionGet(obj, operators[i][1]); } SolutionFree(obj); return res; }