在C语言中确实是有哈希表这个结构体的,因而利用哈希表来解决这个问题
C:
/**
* 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().
*/
/*
定义了一个名为hashTable
的结构体,用于表示哈希表中的一个节点。这个结构体包含三个成员:
char* key
:存储经过排序后的字符串,作为哈希表的键。int index
:存储在结果数组中的索引。int cnt
:存储当前组中字符串的数量。UT_hash_handle hh
:是一个用于哈希表操作的句柄,通常由哈希库提供。
*/
struct hashTable {
char* key;
int index;
int cnt;
UT_hash_handle hh;
};
/*
定义了一个比较函数cmp
,用于qsort
排序。它比较两个字符的大小,如果第一个字符大于第二个字符,返回 1,否则返回 0。
*/
int cmp (const void* a, const void* b) {
return *(char*)a > *(char*)b ? 1 : 0;
}
/*
函数groupAnagrams:
这个函数的目的是将输入的字符串数组按照字母异位词进行分组,
Args:
一个字符指针的指针数组strs
、
数组的大小strsSize
、
一个指向整数的指针returnSize
一个指向整数指针的指针returnColumnSizes
。
Return:返回一个三维字符指针数组和一个整数数组,分别表示分组结果和每个分组的大小。
res
是一个三维字符指针数组,存储了按照字母异位词分组后的结果。每个元素res[i]
是一个二维字符指针数组,代表一个分组,其中存储了属于该分组的字符串指针。
*returnSize
表示最终分组的个数。在代码执行过程中,每当发现一个新的分组时,*returnSize
就会增加,最终反映了总的分组数量。
*returnColumnSizes
是一个整数指针数组,其中每个元素(*returnColumnSizes)[i]
表示对应分组res[i]
中字符串的个数。这样可以方便地知道每个分组中包含多少个字符串,以便在后续处理中进行正确的访问和操作。
*/
char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes){
if (strsSize == 0) return NULL;
char ***res = (char ***)malloc(sizeof(char **) * strsSize);
*returnColumnSizes = (int *)malloc(sizeof(int) * strsSize);
*returnSize = 0;
struct hashTable *set = NULL;
/*
这是一个循环,遍历输入的字符串数组。对于每个字符串,计算其长度,创建一个临时字符串并复制当前字符串到临时字符串中,然后对临时字符串进行排序。接着在哈希表中查找临时字符串。
*/
for(int i=0; i<strsSize; i++){
int len = strlen(strs[i]);
char strtmp[len+1];
/*
这一步将新分配的字符串空间初始化为 0。这是为了确保字符串的初始状态是干净的,避免出现未定义的值。
*/
memset(strtmp, 0, sizeof(char) * (len+1));
/*
将输入字符串数组strs
中的当前字符串strs[i]
复制到新分配的字符串空间中。
sizeof(char) * len
指定了要复制的字节数,即输入字符串的长度(以字节为单位)。
*/
memcpy(strtmp, strs[i], sizeof(char) * len);
// qsort tmp
/*
这段代码的目的是对临时字符串进行排序,然后在哈希表中查找是否已经存在具有相同排序后字符串的节点。如果找到了匹配的节点,说明当前字符串属于已有的分组;如果没有找到,需要创建一个新的分组并将当前字符串添加到新的分组中。
*/
qsort(strtmp, len, sizeof(char), cmp);
struct hashTable *tmp;
/*
这是一个宏调用,用于在哈希表 set
中查找键为 strtmp
的节点。
HASH_FIND_STR
是一个由哈希库提供的宏,用于在哈希表中进行字符串键的查找。
set
是一个指向哈希表的指针,它可能是一个全局变量或者在函数中已经初始化的变量。
strtmp
是要查找的键,在这里是经过排序后的临时字符串。
tmp
是一个输出参数,用于存储找到的节点的指针。如果在哈希表中找到了匹配的节点,tmp
将指向该节点;如果没有找到,tmp
将为 NULL
。
*/
HASH_FIND_STR(set, strtmp, tmp);
/*
如果在哈希表中没有找到临时字符串,说明这是一个新的分组,创建一个新的哈希表节点,将当前字符串添加到结果数组中,并更新返回的大小和当前分组的大小。如果在哈希表中已经有临时字符串,说明当前字符串属于已有的分组,将当前字符串添加到对应的分组中,并更新当前分组的大小。
*/
if(tmp == NULL) {
// HASH表中没有
tmp= (struct hashTable *)malloc(sizeof(struct hashTable));
tmp->key = (char*)calloc(len + 1, sizeof(char));
//使用 memset
函数将 strtmp
字符数组的内容初始化为 0。
memset(tmp->key, 0, sizeof(char) * (len + 1));
memcpy(tmp->key, strtmp, sizeof(char) * len);
/* 将新节点的 index
成员设置为当前的 returnSize
值。这表示新分组在结果数组中的索引。
将新节点的 cnt
成员设置为 1,表示当前分组中只有一个字符串(即当前正在处理的字符串)
*/
tmp->index = *returnSize;
tmp->cnt = 1;
//printf("%d",1);
/*
将新创建的节点添加到哈希表 set
中。这个宏可能是哈希库提供的用于添加节点到哈希表的操作。
*/
HASH_ADD_STR(set, key, tmp);
//HASH_ADD_KEYPTR( hh, set, tmp->key, strlen(tmp->key), tmp);
//HASH_ADD(hh, set, key[0], strlen(tmp->key), tmp);
/*
为新的分组在结果数组 res
中分配足够的内存空间,以存储该分组中的字符串指针。这里分配的空间大小是输入字符串数组的大小,假设每个分组最多可以包含与输入字符串数组相同数量的字符串。
res
是一个三维字符指针数组,用于存储最终的分组结果。这里为res
中的一个新的分组分配内存空间。
*returnSize
表示当前已经处理的分组数量。通过res[*returnSize]
,我们访问到这个新分配的分组位置。
malloc(sizeof(char*) * strsSize)
为这个分组分配足够的空间来存储指向字符串的指针,数量为输入字符串数组的大小strsSize
。这是假设每个分组可能最多包含与输入字符串数组相同数量的字符串。
*/
res[*returnSize] = (char **)malloc(sizeof(char*) * strsSize);
//printf("%d",2);
/*
为当前字符串在新分组中分配足够的内存空间来存储字符串内容。同样,len + 1
是为了包括 null 终止符。
res[*returnSize]
是刚才新分配的分组。现在为这个分组中的一个具体位置分配内存来存储一个字符串。
tmp->cnt - 1
表示当前正在处理的字符串在这个新分组中的位置索引。因为计数是从 1 开始的,所以这里减去 1 得到正确的数组索引。
malloc(sizeof(char) * (len + 1))
为这个字符串分配足够的空间,长度为输入字符串的长度len
加上一个字符用于存储字符串末尾的 null 终止符。
*/
res[*returnSize][tmp->cnt-1] = (char *)malloc(sizeof(char) * (len + 1));
memset(res[*returnSize][tmp->cnt-1], 0, sizeof(char) * (len + 1));
memcpy(res[*returnSize][tmp->cnt-1], strs[i], sizeof(char) * len);
/*
*returnColumnSizes
是一个整数指针数组,用于存储每个分组中字符串的数量。
(*returnColumnSizes)[*returnSize]
访问当前新分组对应的位置。
将tmp->cnt
赋值给这个位置,表示新分组中当前的字符串数量。
*/
(*returnColumnSizes)[*returnSize] = tmp->cnt;
/*
增加*returnSize
的值,表示已经处理的分组数量增加了一个。这是因为我们刚刚创建了一个新的分组并将一个字符串添加到了这个分组中。
*/
(*returnSize)++;
}
else {
// HASH表中有记录
res[tmp->index][tmp->cnt] = (char *)malloc(sizeof(char) * (len + 1));
memset(res[tmp->index][tmp->cnt], 0, sizeof(char) * (len + 1));
memcpy(res[tmp->index][tmp->cnt], strs[i], sizeof(char) * len);
tmp->cnt += 1;
(*returnColumnSizes)[tmp->index] = tmp->cnt;
}
}
return res;
}
/*
char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes){
if (strsSize == 0) {
return NULL;
}
char*** res = (char***)calloc(strsSize, sizeof(char**));
*returnSize = 0;
*returnColumnSizes = (int*)calloc(strsSize, sizeof(int));
struct hashTable* set = NULL;
for (int i = 0; i < strsSize; i++) {
int len = strlen(strs[i]);
char strtmp[len + 1];
memset(strtmp, 0, sizeof(char) * (len+1));
memcpy(strtmp, strs[i], sizeof(char) * strlen(strs[i]));
qsort(strtmp, len, sizeof(char), cmp);
struct hashTable* tmp;
//HASH_FIND(hh, set, strtmp, sizeof(char), tmp);
HASH_FIND_STR(set, strtmp, tmp);
if (tmp == NULL) {
tmp = (struct hashTable*)calloc(1, sizeof(struct hashTable));
tmp->key = (char*)calloc(len + 1, sizeof(char));
memset(tmp->key, 0, sizeof(char) * (len+1));
memcpy(tmp->key, strtmp, sizeof(char) * len);
tmp->index = *returnSize;
tmp->cnt = 1;
HASH_ADD(hh, set, key, sizeof(char), tmp);
//HASH_ADD_STR(set, key, tmp);
res[*returnSize] = (char**)calloc(strsSize, sizeof(char*));
res[*returnSize][tmp->cnt - 1] = (char*)calloc(len + 1, sizeof(char));
memset(res[*returnSize][tmp->cnt - 1], 0, sizeof(char) * (len+1));
memcpy(res[*returnSize][tmp->cnt - 1], strs[i], sizeof(char) * len);
(*returnColumnSizes)[*returnSize] = tmp->cnt;
(*returnSize)++;
}
else {
printf("%d",1);
res[tmp->index][tmp->cnt] = (char*)calloc(len + 1, sizeof(char));
memset(res[*returnSize][tmp->cnt - 1], 0, sizeof(char) * (len+1));
memcpy(res[tmp->index][tmp->cnt], strs[i], strlen(strs[i]));
tmp->cnt += 1;
(*returnColumnSizes)[tmp->index] = tmp->cnt;
}
}
return res;
}*/
代码来自力扣ICE大神,这里把代码基本都注释,让自己更明白一些,但是自己肯定敲不出来也想不到。ICE大神https://leetcode.cn/u/ice-751/
标签:tmp,49,随想录,len,char,分组,一刷,字符串,sizeof From: https://blog.csdn.net/weixin_50422106/article/details/143365718