C语言 | Leetcode C语言题解之第460题LFU缓存

题目：

题解：

/*
数值链表的节点定义。
*/
typedef struct ValueListNode_s
{
    int key;
    int value;
    int counter;
    struct ValueListNode_s *prev;
    struct ValueListNode_s *next;
}
ValueListNode;

/*
计数链表的节点定义。
其中，head是数值链表的头节点，对应的是最新的数值节点。
环形链表，head->prev实际就是tail，对应的就是最久未使用的节点。
*/
typedef struct CounterListNode_s
{
    ValueListNode *head;
    struct CounterListNode_s *prev;
    struct CounterListNode_s *next;
}
CounterListNode;

/*
对象结构定义。
capacity:           总的容量。
currentCounter:     当前已有的key的数量。
keyHash:            key的哈希数组，为空表示这个key对应数值不存在。
counterHash:        counter的哈希数组，为空表示这个counter对应的链表不存在。
head:               计数链表的头节点。
*/
typedef struct
{
    int capacity;
    int currentCounter;
    ValueListNode **keyHash;
    CounterListNode **counterHash;
    CounterListNode *head;
}
LFUCache;

/*
几个自定义函数的声明，具体实现见下。
*/
extern void removeValueNode(CounterListNode *counterNode, ValueListNode *valueNode);
extern void insertValueNode(CounterListNode *counterNode, ValueListNode *valueNode);
extern void removeCounterNode(LFUCache *obj, CounterListNode *counterNode);
extern void insertCounterNode(LFUCache *obj, CounterListNode *counterPrev, CounterListNode *counterNode);

/*
创建对象。
*/
LFUCache *lFUCacheCreate(int capacity)
{
    LFUCache *obj = (LFUCache *)malloc(sizeof(LFUCache));
    /* 总容量就等于入参capacity，当前已有的key的数量初始化为0。 */
    obj->capacity = capacity;
    obj->currentCounter = 0;
    /* key的取值范围是[0, 10^5]，共100001个。用calloc代替malloc，即包含了初始化为空的步骤。 */
    obj->keyHash = (ValueListNode **)calloc(100001, sizeof(ValueListNode *));
    /* 题目给的操作次数上限是2*10^5。同上，用calloc代替malloc，包含了初始化为空的步骤。 */
    obj->counterHash = (CounterListNode **)calloc(200001, sizeof(CounterListNode *));
    /* 刚开始时，计数链表为空。 */
    obj->head = NULL;
    return obj;
}

/*
获取指定key的数值。
value:          想要获取key对应的数值，初始化为-1，假如获取不到，就返回这个-1。
valueNode:      从keyHash中直接获取的数值链表节点。
counterNode:    在计数加一之前，这个数值节点当前所处的计数链表。
counterNew:     在计数加一之后，这个数值节点想要加入的新计数链表。
*/
int lFUCacheGet(LFUCache *obj, int key)
{
    int value = -1;
    ValueListNode *valueNode = obj->keyHash[key];
    CounterListNode *counterNode = NULL, *counterNew = NULL;
    /* 对应的key存在数值时，才需要返回其数值，否则返回-1。 */
    if(NULL != valueNode)
    {
        /* 要返回的数值。 */
        value = valueNode->value;
        /* 这个节点当前在哪一个计数链表节点中。 */
        counterNode = obj->counterHash[valueNode->counter];
        /* 数值的计数加一。以及计数加一之后，它想要加入的新的计数链表节点。 */
        valueNode->counter++;
        counterNew = obj->counterHash[valueNode->counter];
        /* 把数值节点从旧的链表中移除。 */
        removeValueNode(counterNode, valueNode);
        /* 如果这个新的计数节点还不存在，则新建一个节点。 */
        if(NULL == counterNew)
        {
            counterNew = (CounterListNode *)calloc(1, sizeof(CounterListNode));
            obj->counterHash[valueNode->counter] = counterNew;
            /* 新建计数节点，加到counterNode的后方。 */
            insertCounterNode(obj, counterNode, counterNew);
        }
        /* 如果旧的计数节点中的数值链表变为空，则旧的计数节点也需要从计数链表中移除。 */
        if(NULL == counterNode->head)
        {
            removeCounterNode(obj, counterNode);
            free(counterNode);
            obj->counterHash[valueNode->counter - 1] = NULL;
        }
        /* 把数值节点加入到新的链表中。 */
        insertValueNode(counterNew, valueNode);
    }
    return value;
}

/*
赋值指定key的数值。
keyRemove:          要被移除的键值。
valueNode:          指定的key对应的数值节点。
valueRemove:        可能被移除的数值节点。
counterNode:        在计数加一之前，这个数值节点当前所处的计数链表。
counterNew:         在计数加一之后，这个数值节点想要加入的新计数链表。
*/
void lFUCachePut(LFUCache *obj, int key, int value)
{
    int keyRemove = 0;
    ValueListNode *valueNode = obj->keyHash[key], *valueRemove = NULL;
    CounterListNode *counterNode = NULL, *counterNew = NULL;
    /* 总容量为0的话，什么都不需要做。 */
    if(0 == obj->capacity)
    {
        return;
    }
    /* 如果这个key值已经存在，则修改其数值。 */
    if(NULL != valueNode)
    {
        /* 修改新的数值。 */
        valueNode->value = value;
        /* 这个节点当前在哪一个计数链表节点中。 */
        counterNode = obj->counterHash[valueNode->counter];
        /* 数值的计数加一。以及计数加一之后，它想要加入的新的计数链表节点。 */
        valueNode->counter++;
        counterNew = obj->counterHash[valueNode->counter];
        /* 把数值节点从旧的链表中移除。 */
        removeValueNode(counterNode, valueNode);
        /* 如果这个新的计数节点还不存在，则新建一个节点。 */
        if(NULL == counterNew)
        {
            counterNew = (CounterListNode *)calloc(1, sizeof(CounterListNode));
            obj->counterHash[valueNode->counter] = counterNew;
            /* 新建计数节点，加到counterNode的后方。 */
            insertCounterNode(obj, counterNode, counterNew);
        }
        /* 如果旧的计数节点中的数值链表变为空，则旧的计数节点也需要从计数链表中移除。 */
        if(NULL == counterNode->head)
        {
            removeCounterNode(obj, counterNode);
            free(counterNode);
            obj->counterHash[valueNode->counter - 1] = NULL;
        }
        /* 把数值节点加入到新的链表中。 */
        insertValueNode(counterNew, valueNode);
    }
    /* 否则，新建一个键值。 */
    else
    {
        /* 如果没有满总量，则数量加一。 */
        if(obj->capacity > obj->currentCounter)
        {
            obj->currentCounter++;
        }
        /* 否则，先把最近最久未使用的键移除。 */
        else
        {
            /* 要删除的数值节点所在的计数节点，一定是计数最少的那个counterNode，即头节点。 */
            counterNode = obj->head;
            /* 要被移除的节点，是数值链表的尾节点。 */
            valueRemove = counterNode->head->prev;
            keyRemove = valueRemove->key;
            /* 把它从链表中移除。 */
            removeValueNode(counterNode, valueRemove);
            /* 如果计数节点中的数值链表变成空，则也移除这个计数节点。 */
            if(NULL == counterNode->head)
            {
                removeCounterNode(obj, counterNode);
                free(counterNode);
                obj->counterHash[valueRemove->counter] = NULL;
            }
            free(valueRemove);
            obj->keyHash[keyRemove] = NULL;
        }
        /* 新建一个数值节点。 */
        valueNode = (ValueListNode *)calloc(1, sizeof(ValueListNode));
        valueNode->key = key;
        valueNode->value = value;
        valueNode->counter = 1;
        obj->keyHash[key] = valueNode;
        /* 要新加入的链表。新出现的数值，计数肯定是1。 */
        counterNew = obj->counterHash[1];
        /* 如果这个计数节点还不存在，则新建一个。 */
        if(NULL == counterNew)
        {
            counterNew = (CounterListNode *)calloc(1, sizeof(CounterListNode));
            obj->counterHash[1] = counterNew;
            /* counter为1的计数节点，肯定是加到头部的。 */
            insertCounterNode(obj, NULL, counterNew);
        }
        /* 把数值节点加入到新的链表中。 */
        insertValueNode(counterNew, valueNode);
    }
    return;
}

/*
释放对象。
*/
void lFUCacheFree(LFUCache *obj)
{
    CounterListNode *counterNode = obj->head, *counterNext = NULL;
    ValueListNode *valueNode = NULL, *valueNext = NULL;
    /* 逐个释放计数链表的每个节点。 */
    while(NULL != counterNode)
    {
        counterNext = counterNode->next;
        /* 释放每个计数链表节点下面的数值链表。
        环形链表的循环，使用do、while语句。 */
        valueNode = counterNode->head;
        do
        {
            valueNext = valueNode->next;
            free(valueNode);
            valueNode = valueNext;
        }
        while(counterNode->head != valueNode);
        free(counterNode);
        counterNode = counterNext;
    }
    /* 释放key的哈希数组。 */
    free(obj->keyHash);
    /* 释放counter的哈希数组。 */
    free(obj->counterHash);
    /* 释放对象。 */
    free(obj);
    return;
}

/*
几个自定义函数的具体实现。
主要是双向链表、双向循环链表的节点添加、删除的操作，保证操作前后仍然是双向链表、双向循环链表。
*/

/*
把数值节点从数值链表中删除。
*/
void removeValueNode(CounterListNode *counterNode, ValueListNode *valueNode)
{
    /* 如果这个被删除节点是链表中的唯一一个，则删除之后直接为空链表。 */
    if(valueNode->next == valueNode)
    {
        counterNode->head = NULL;
    }
    /* 否则把它的前后两个节点连接起来。 */
    else
    {
        valueNode->prev->next = valueNode->next;
        valueNode->next->prev = valueNode->prev;
        /* 如果删掉的就是头节点，则新的头节点的位置往后挪一位。 */
        if(counterNode->head == valueNode)
        {
            counterNode->head = valueNode->next;
        }
    }
    return;
}

/*
把数值节点加入到数值链表头部。
*/
void insertValueNode(CounterListNode *counterNode, ValueListNode *valueNode)
{
    ValueListNode *tail = NULL;
    /* 如果本身是空链表，则它是其中唯一节点。 */
    if(NULL == counterNode->head)
    {
        valueNode->prev = valueNode;
        valueNode->next = valueNode;
    }
    /* 否则就把它插入到原来的头尾之间。 */
    else
    {
        tail = counterNode->head->prev;
        valueNode->prev = tail;
        valueNode->next = counterNode->head;
        counterNode->head->prev = valueNode;
        tail->next = valueNode;
    }
    /* 它成为新的头节点。 */
    counterNode->head = valueNode;
    return;
}

/*
把计数节点从计数链表中删除。
*/
void removeCounterNode(LFUCache *obj, CounterListNode *counterNode)
{
    /* 如果删除的本身是头节点，则头节点将变为下一个。 */
    if(obj->head == counterNode)
    {
        obj->head = counterNode->next;
        if(NULL != obj->head)
        {
            obj->head->prev = NULL;
        }
    }
    /* 否则，把它的前后两个节点连起来。
    不是头节点的话，prev肯定存在，next可能为空。 */
    else
    {
        counterNode->prev->next = counterNode->next;
        if(NULL != counterNode->next)
        {
            counterNode->next->prev = counterNode->prev;
        }
    }
    return;
}

/*
把一个新的计数节点加入到计数链表指定节点counterPrev的后方。
如果counterPrev为空，则表示加到链表头。
*/
void insertCounterNode(LFUCache *obj, CounterListNode *counterPrev, CounterListNode *counterNode)
{
    /* 如果counterPrev为空，说明是加入到头节点的位置。 */
    if(NULL == counterPrev)
    {
        counterNode->prev = NULL;
        counterNode->next = obj->head;
        if(NULL != obj->head)
        {
            obj->head->prev = counterNode;
        }
        obj->head = counterNode;
    }
    /* 否则插入到counterPrev和counterPrev->next之间。 */
    else
    {
        counterNode->prev = counterPrev;
        counterNode->next = counterPrev->next;
        if(NULL != counterPrev->next)
        {
            counterPrev->next->prev = counterNode;
        }
        counterPrev->next = counterNode;
    }
    return;
}