首页 > 其他分享 >代码随想录一刷——49.字母异位词分组

代码随想录一刷——49.字母异位词分组

时间:2024-11-02 22:15:43浏览次数:3  
标签:tmp 49 随想录 len char 分组 一刷 字符串 sizeof

在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大神icon-default.png?t=O83Ahttps://leetcode.cn/u/ice-751/

标签:tmp,49,随想录,len,char,分组,一刷,字符串,sizeof
From: https://blog.csdn.net/weixin_50422106/article/details/143365718

相关文章

  • 代码随想录一刷——242.有效的字母异位词
    在考虑哈希表选择哪种结构的时候(数组,set,map),在大小和范围都比较小的情况下我们优先考虑数组。在本题中,我们构建一个哈希表,来统计在s中各个字母出现的频次,而后在t中对已统计好频次的哈希表进行自减操作,最后判断哈希表中每个索引是否是0,若不是则s和t不是有效地字母异位词,反之,则......
  • 代码随想录算法训练营第十天|leetcode232.用栈实现队列、leetcode225. 用队列实现栈、
    1leetcode232.用栈实现队列题目链接:232.用栈实现队列-力扣(LeetCode)文章链接:代码随想录视频链接:栈的基本操作!|LeetCode:232.用栈实现队列哔哩哔哩bilibili自己的思路:真的第一次接触这个概念,完全没有任何思路,甚至不知道从何下手1.1基本概念栈就是相当于砌墙的砖头,先......
  • 代码随想录算法训练营第九天|leetcode151.翻转字符串里的单词、卡码网55.右旋字符串、
    1leetcode151.翻转字符串里的单词题目链接:151.反转字符串中的单词-力扣(LeetCode)文章链接:代码随想录视频链接:字符串复杂操作拿捏了!|LeetCode:151.翻转字符串里的单词哔哩哔哩bilibili自己的思路:直接将空格去掉,然后分割字符串为列表,在列表中进行翻转,不在字符串内部操作......
  • 【GESP】C++一级练习BCQM3149,重复说话
    GESP一级知识点for循环语句和输出语句,非常简单。题目题解详见:https://www.coderli.com/gesp-1-bcqm3149/【GESP】C++一级练习BCQM3149,重复说话|OneCoderGESP一级知识点for循环语句和输出语句,非常简单。https://www.coderli.com/gesp-1-bcqm3149/C++GESP专项交流频道:GESP......
  • 数组篇-代码随想录
    数组篇跳-二分查找-704-力扣classSolution{publicintsearch(int[]nums,inttarget){if(nums==null||nums.length==0)return-1;if(target<nums[0]||target>nums[nums.length-1])return-1;intleft=0,......
  • 代码随想录一刷day6 (链表day2)(链表完结)
    24.两两交换链表中的节点分三步走;1.创建dummyhead2.三个指针 cur  t1 t23.  cur->next=t2;  t1->next=t2->next;  t2->t1->next; 最后让cur=t1;注意最后返回的是dummyhead-》next 而不是head;注意最后deletedummyhead19.删除链表的倒数第N个节点注......
  • 代码随想录一刷Day6--链表day1
    1.增加虚拟头节点,使头节点的移除跟别的移除统一(否则头节点需要让head指针往后移)2.删除节点的话,注意delete203.移除链表元素对链表的操作有点不熟悉ListNode*DummyHead=newListNode(0,head);  使用new进行虚拟头节点的创建删除tmp删除分支时,不用让cur=cur-》next 70......
  • 代码随想录|day3 链表 203.移除链表元素、707.设计链表、206.反转链表
    基础知识:代码随想录203.移除链表元素建议:本题最关键是要理解虚拟头结点的使用技巧,这个对链表题目很重要。这里主要记录用虚头的方法。即设置一个虚拟的头指针帮忙解题。先看代码:classSolution{publicListNoderemoveElements(ListNodehead,intval){ Li......
  • 代码随想录算法训练营第三十三天|Day33 动态规划
    62.不同路径https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html视频讲解:https://www.bilibili.com/video/BV1ve4y1x7Eu思路int**initDP(intm,intn){int**dp=(int**)malloc(sizeof(int*)*m);inti,j;for(i=0;i<......
  • 代码随想录刷题学习日记
    仅为个人记录复盘学习历程,解题思路来自代码随想录代码随想录刷题笔记总结网址:代码随想录404.左叶子之和计算给定二叉树的所有左叶子之和。(所有的左边的叶子节点的和)提供参数:根结点root关键思路:遍历,判断若为左叶子节点,则将值累加。主要操作:递归三要素1.返回值类型和参......