力扣第49题C语言
时间: 2025-05-01 20:15:06 浏览: 38
### 力扣(LeetCode)第49题C语言解决方案
对于力扣(LeetCode)上的第49题,即《字母异位词分组》,此题目要求编写一种方法来解决给定字符串列表按字母异位词组合的问题。下面提供了一种基于哈希表的方法实现这一功能,在C语言中的具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 10007 /* 哈希表大小 */
typedef struct Node {
char *key;
int val[10];
int cnt; // 数组val中有效元素数量
struct Node *next;
} HashItem;
/* 创建新的节点 */
HashItem *hashCreateNode(char *key, int idx) {
HashItem *obj = (HashItem *)malloc(sizeof(HashItem));
obj->key = key;
obj->cnt = 1;
obj->val[obj->cnt - 1] = idx;
obj->next = NULL;
return obj;
}
unsigned long hashFunc(char *str) {
unsigned long h = 0;
while (*str != '\0') {
h = h * 31 + *str++;
}
return h % MAX_SIZE;
}
void insertIntoBucket(HashItem **bucket, char *s, int sSize, int pos) {
char temp[sSize + 1];
strcpy(temp,s);
qsort(temp,strlen(temp),sizeof(char),strcmp);
HashItem *item = NULL;
unsigned long index = hashFunc(temp);
item = bucket[index];
if (!item){
char* newKey=(char*)calloc(sSize+1,sizeof(char));
strcpy(newKey,temp);
bucket[index]=hashCreateNode(newKey,pos);
return ;
}
while(item){
if(strcmp(item->key,temp)==0){
item->val[item->cnt++]=pos;
free(temp);
return ;
}else{
if(!item->next){
char* newKey=(char*)calloc(strlen(temp)+1,sizeof(char));
strcpy(newKey,temp);
item->next=hashCreateNode(newKey,pos);
return ;
}
item=item->next;
}
}
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** groupAnagrams(char ** strs, int strsSize, int* retSize, int** colSize){
HashItem *hashtable[MAX_SIZE] = {NULL};
memset(hashtable, 0 , sizeof hashtable);
for(int i=0;i<strsSize;++i){
insertIntoBucket(hashtable,strs[i],strlen(strs[i]),i);
}
int count = 0;
for(int i=0;i<MAX_SIZE;++i){
HashItem *pEntry = hashtable[i];
while(pEntry!=NULL){
++count;
pEntry=pEntry->next;
}
}
int **retArr =(int**)malloc(count*sizeof(int *));
*colSize = (int*)malloc(count * sizeof(int));
int k = 0;
for(int j=0;j<MAX_SIZE;++j){
HashItem *entry = hashtable[j];
while(entry!=NULL){
retArr[k]=(int*)malloc(entry->cnt * sizeof(int));
memcpy(retArr[k++], entry->val, entry->cnt * sizeof(int));
entry=entry->next;
}
}
*retSize=count;
return retArr;
}
```
上述代码实现了对输入字符串数组按照字母异位词进行分类的功能[^1]。
阅读全文
相关推荐


















