题解 | #设计LFU缓存结构#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 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;
}