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 > targetlistItif (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 < targetlistItif (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表到双链表  从双链表到hashnewlist->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);
}