C语言 | Leetcode C语言题解之第432题全O(1)的数据结构

题目：

题解：

//哈希+队列
//哈希检查是否存在
//双编标维护次数顺序
#define MAXSIZE 769/* 选取一个质数即可 */
typedef struct hashNode
{
    char* string;     //字符串
    int                       count;       //次数
    struct doubleListNode* dList;
    struct hashNode* next;      //保存链表表头
} hashMapList;

typedef struct
{
    hashMapList* hashHead[MAXSIZE];//定义哈希数组的大小
} MyHashMap;

typedef struct doubleListNode
{
    hashMapList* pHashMap;
    struct doubleListNode* prev;  //前一个指针域
    struct doubleListNode* next;  //下一个指针域
}doubleList;

typedef struct
{
    doubleList* front;       //头部指针
    doubleList* rear;        //尾部指针
    int count;
} MyQueueList;

typedef struct
{
    MyQueueList* doublelist;
    MyHashMap* hashmap;
} AllOne;

AllOne* allOneCreate()
{
    AllOne* newAllone = (AllOne*)malloc(sizeof(AllOne));
    MyHashMap* newHash = (MyHashMap*)malloc(sizeof(MyHashMap));
    MyQueueList* newList = (MyQueueList*)malloc(sizeof(MyQueueList));
    //哈希初始化
    for (int i = 0; i < MAXSIZE; i++)
    {
        newHash->hashHead[i] = NULL;
    }
    //队列初始化
    newList->front = NULL;
    newList->rear = NULL;
    newAllone->hashmap = newHash;
    newAllone->doublelist = newList;
    newAllone->doublelist->count = 0;
    return newAllone;
}

//哈希代码
hashMapList* isInHash(hashMapList* list, char* stringKey)
{
    hashMapList* nodeIt = list;
    //通过链表下遍历
    while (nodeIt != NULL)
    {
        if (strcmp(stringKey, nodeIt->string) == 0)
        {
            return nodeIt;
        }
        nodeIt = nodeIt->next;
    }
    return NULL;
}

hashMapList* myHashMapPut(MyHashMap* obj, char* stringKey, int count)
{
    hashMapList* newNode = (hashMapList*)malloc(sizeof(hashMapList));
    newNode->string = stringKey;
    newNode->next = NULL;
    newNode->count = count;
    if (obj->hashHead[stringKey[0] % MAXSIZE] != NULL)
    {
        //当前头链表不为空，则需要将后续的链表接上
        //需要主要这里表头也代表一个数据的值
        newNode->next = obj->hashHead[stringKey[0] % MAXSIZE];
    }
    //修改头链表
    obj->hashHead[stringKey[0] % MAXSIZE] = newNode;
    return newNode;
}

hashMapList* myHashMapGet(MyHashMap* obj, char* stringKey)
{
    hashMapList* hashMapIt = isInHash(obj->hashHead[stringKey[0] % MAXSIZE], stringKey);
    if (hashMapIt != NULL)
    {
        return hashMapIt;
    }
    return NULL;
}

void myHashMapRemove(MyHashMap* obj, char* key)
{
    hashMapList* nodePre = NULL;
    hashMapList* nodeIt = obj->hashHead[key[0] % MAXSIZE];

    //通过链表下遍历
    while (nodeIt != NULL)
    {
        if (strcmp(key, nodeIt->string) == 0)
        {
            break;
        }
        nodePre = nodeIt;
        nodeIt = nodeIt->next;
    }

    //找到了
    if (nodePre == NULL)
    {
        //等于表头
        obj->hashHead[key[0] % MAXSIZE] = nodeIt->next;
    }
    else
    {
        nodePre->next = nodeIt->next;
    }
    free(nodeIt);
}

void myHashMapFree(MyHashMap* obj)
{
    int i;
    hashMapList* freeIt;
    hashMapList* curIt;
    for (i = 0; i < MAXSIZE; i++)
    {
        if (obj->hashHead[i] != NULL)
        {
            freeIt = NULL;
            curIt = obj->hashHead[i];

            while (curIt != NULL)
            {
                freeIt = curIt;
                curIt = curIt->next;
                free(freeIt);
            }
            obj->hashHead[i] = NULL;
        }
    }
    free(obj);
}

//双链表代码
void myLinkedListFree(MyQueueList* obj)
{
    struct doubleListNode* nodeIt = obj->front;
    struct doubleListNode* nodeFree = obj->front;
    while (nodeIt != NULL)
    {
        nodeIt = nodeIt->next;
        free(nodeFree);
        nodeFree = nodeIt;
    }
    free(obj);
}

void doubleLsitMove(AllOne* obj, doubleList* targetlistIt, bool isUp)
{

    //数量等于2 直接比较双链表的头尾结点的值
    if (obj->doublelist->count == 2)
    {
        if (obj->doublelist->front->pHashMap->count >= obj->doublelist->rear->pHashMap->count)
        {
            return;
        }
        doubleList* temp = obj->doublelist->front;
        obj->doublelist->front = obj->doublelist->rear;
        obj->doublelist->rear  = temp;
        obj->doublelist->front->prev = NULL;
        obj->doublelist->front->next = obj->doublelist->rear;
        obj->doublelist->rear->prev  = obj->doublelist->front;
        obj->doublelist->rear->next  = NULL;
        return;
    }

    //至少3个结点才开始遍历
    if (isUp)
    {
        //递增 找到当前值 刚好比当前值大的位置
        if (targetlistIt != obj->doublelist->front)
        {
            doubleList* listItPre = targetlistIt->prev;
            //当前节点的cout大于 前一个结点的count值
            if(listItPre->pHashMap->count < targetlistIt->pHashMap->count)
            {
                //循环遍历查找
                while (listItPre != NULL && listItPre->pHashMap->count < targetlistIt->pHashMap->count)
                {
                    listItPre = listItPre->prev;
                }

                if (targetlistIt == obj->doublelist->rear)
                {
                    //特殊处理尾部特殊情况
                    obj->doublelist->rear       = targetlistIt->prev;
                    obj->doublelist->rear->next = NULL;
                }
                

                //插入位置是中间  listItPre > targetlistIt
                if (targetlistIt->prev != NULL)
                    targetlistIt->prev->next = targetlistIt->next;

                if (targetlistIt->next != NULL)
                    targetlistIt->next->prev = targetlistIt->prev;

                if (listItPre == NULL)
                {
                    //插入位置 是头部
                    targetlistIt->next              =    obj->doublelist->front;
                    obj->doublelist->front->prev    = targetlistIt;
                    obj->doublelist->front          = targetlistIt;
                    targetlistIt->prev              = NULL;
                }
                else
                {
                    targetlistIt->next          = listItPre->next;
                    targetlistIt->prev          = listItPre;
                    listItPre->next->prev       = targetlistIt;
                    listItPre->next             = targetlistIt;
                }
            }

        }
    }
    else
    {
        //递减 找到当前值 刚好比当前值小的位置
        if (targetlistIt != obj->doublelist->rear)
        {
            //向后移动
            doubleList* listItNxt = targetlistIt->next;
            //当前节点的cout大于 小于下一个结点的count值
            if (listItNxt->pHashMap->count > targetlistIt->pHashMap->count)
            {
                while (listItNxt != NULL && listItNxt->pHashMap->count > targetlistIt->pHashMap->count)
                {
                    listItNxt = listItNxt->next;
                }

                if (targetlistIt == obj->doublelist->front)
                {
                    //特殊处理头部特殊情况
                    obj->doublelist->front          = targetlistIt->next;
                    obj->doublelist->front->prev    = NULL;
                }

                //插入位置是中间  listItPre < targetlistIt
                if (targetlistIt->prev != NULL)
                    targetlistIt->prev->next = targetlistIt->next;

                if (targetlistIt->next != NULL)
                    targetlistIt->next->prev = targetlistIt->prev;

                if (listItNxt == NULL)
                {
                    //插入到队尾
                    obj->doublelist->rear->next     = targetlistIt;
                    targetlistIt->prev              = obj->doublelist->rear;
                    obj->doublelist->rear           = targetlistIt;
                    targetlistIt->next              = NULL;

                }
                else
                {
                    targetlistIt->prev = listItNxt->prev;
                    targetlistIt->next = listItNxt;
                    listItNxt->prev->next = targetlistIt;
                    
                }
            }
        }
    }
}

void myDobleListRemove(MyQueueList* obj, doubleList* targetlistIt)
{
    if (targetlistIt == obj->front && targetlistIt == obj->rear)
    {
        obj->front = NULL;
        obj->rear = NULL;
    }
    else if (targetlistIt == obj->front)
    {
        obj->front = obj->front->next;
        obj->front->prev = NULL;
    }
    else if (targetlistIt == obj->rear)
    {
        obj->rear = obj->rear->prev;
        obj->rear->next = NULL;
    }
    else
    {
        targetlistIt->prev->next = targetlistIt->next;
        targetlistIt->next->prev = targetlistIt->prev;
    }
    free(targetlistIt);
}

void allOneInc(AllOne* obj, char* key)
{
    hashMapList* hashMapIt = myHashMapGet(obj->hashmap, key);
    if (hashMapIt == NULL)
    {

        doubleList* newlist = (doubleList*)malloc(sizeof(doubleList));
        newlist->next = NULL;
        newlist->prev = NULL;
        //指向对应的hashMap
        //存入hashmap中，保存字符串做key，以及记录次数为1
        //双向指针 从hash表到双链表  从双链表到hash
        newlist->pHashMap = myHashMapPut(obj->hashmap, key, 1);
        newlist->pHashMap->dList = newlist;

        //插入到队尾处
        if (obj->doublelist->rear == NULL)
        {
            obj->doublelist->front = newlist;
            obj->doublelist->rear = newlist;
        }
        else
        {
            obj->doublelist->rear->next = newlist;
            newlist->prev = obj->doublelist->rear;
            obj->doublelist->rear = newlist;
        }
        obj->doublelist->count++;
    }
    else
    {
        hashMapIt->count++; //次数增加
        if (obj->doublelist->count >= 2)
        {
            doubleList* targetlistIt = hashMapIt->dList;
            doubleLsitMove(obj, targetlistIt, true);
        }
    }
}

void allOneDec(AllOne* obj, char* key)
{
    hashMapList* hashMapIt = myHashMapGet(obj->hashmap, key);
    if ((hashMapIt->count - 1) == 0)
    {
        doubleList* targetlistIt = hashMapIt->dList;
        myHashMapRemove(obj->hashmap, key);
        myDobleListRemove(obj->doublelist, targetlistIt);
        obj->doublelist->count--;
    }
    else
    {
        hashMapIt->count--;
        if (obj->doublelist->count >= 2)
        {
            doubleList* targetlistIt = hashMapIt->dList;
            doubleLsitMove(obj, targetlistIt, false);
        }
    }
}

char* allOneGetMaxKey(AllOne* obj)
{
    if (obj->doublelist->front == NULL)
    {
        return  "";
    }
    return obj->doublelist->front->pHashMap->string;
}

char* allOneGetMinKey(AllOne* obj)
{
    if (obj->doublelist->rear == NULL)
    {
        return  "";
    }
    return obj->doublelist->rear->pHashMap->string;
}

void allOneFree(AllOne* obj)
{
    myHashMapFree(obj->hashmap);
    obj->hashmap = NULL;
   myLinkedListFree(obj->doublelist);
   obj->doublelist =NULL;
   free(obj);
}