LeetCode：721.Accounts Merge账户合并（C语言）

我不是女神ヾ 2023-01-07 13:27 102阅读 0赞

**题目描述：**  
给定一个列表 accounts，每个元素 accounts\[i\] 是一个字符串列表，其中第一个元素 accounts\[i\]\[0\] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。账户本身可以以任意顺序返回。

示例 1：

输入：  
accounts = \[\[“John”, “johnsmith@mail.com”, “john00@mail.com”\], \[“John”, “johnnybravo@mail.com”\], \[“John”, “johnsmith@mail.com”, “john\_newyork@mail.com”\], \[“Mary”, “mary@mail.com”\]\]  
输出：  
\[\[“John”, ‘john00@mail.com’, ‘john\_newyork@mail.com’, ‘johnsmith@mail.com’\], \[“John”, “johnnybravo@mail.com”\], \[“Mary”, “mary@mail.com”\]\]  
解释：  
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 “johnsmith@mail.com”。  
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。  
可以以任何顺序返回这些列表，例如答案 \[\[‘Mary’，‘mary@mail.com’\]，\[‘John’，‘johnnybravo@mail.com’\]，  
\[‘John’，‘john00@mail.com’，‘john\_newyork@mail.com’，‘johnsmith@mail.com’\]\] 也是正确的。

提示：

accounts的长度将在[1，1000]的范围内。
    accounts[i]的长度将在[1，10]的范围内。
    accounts[i][j]的长度将在[1，30]的范围内。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/accounts-merge  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

/** * 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(). */
    #define MAXSTRLEN 35
    struct HashMap{ 
        char key[MAXSTRLEN];
        char name[MAXSTRLEN];
        char parent[MAXSTRLEN];
        UT_hash_handle hh;
    };
    struct HashMap *g_hashHead = NULL;
    char ***g_res = NULL;
    int *g_col = NULL;
    int g_resIndex = 0;
    #define MAXNUM 10000
    
    void InitMem(int accountsSize)
    { 
        g_hashHead = NULL;
        g_res = (char ***)malloc(sizeof(char **) * accountsSize);
        for(int i = 0; i < accountsSize; i++) { 
            g_res[i] = calloc(MAXNUM, sizeof(char*));
        }
        g_col = calloc(accountsSize, sizeof(int));
        g_resIndex = 0;
        return;
    }
    
    void FreeMem()
    { 
        struct HashMap *s = NULL;
        struct HashMap *tmp = NULL;
        HASH_ITER(hh,g_hashHead,s,tmp) { 
            HASH_DEL(g_hashHead,s);
            free(s);
        }
        return; 
    }
    
    struct HashMap *InsertHash(char *key, char *name, char *parent)
    { 
        struct HashMap *s = NULL;
        HASH_FIND_STR(g_hashHead,key,s);
        if(s == NULL) { 
            s = malloc(sizeof(struct HashMap));
            strcpy(s->key, key);
            strcpy(s->name, name);
            strcpy(s->parent, parent);
            HASH_ADD_STR(g_hashHead,key,s);
        }
        return s;
    }
    
    struct HashMap *UpadatHash(char *key, char *name, char *parent)
    { 
        struct HashMap *s = NULL;
        HASH_FIND_STR(g_hashHead,key,s);
        if(s == NULL) { 
            return NULL;
        }
        strcpy(s->name, name);
        strcpy(s->parent, parent);
        return s;
    }
    
    struct HashMap *Find(struct HashMap *x )
    { 
        struct HashMap *s = x;
        while(strcmp(s->key, s->parent) != 0) { 
            char parent[MAXSTRLEN] = { 0};
            strcpy(parent,s->parent);
            HASH_FIND_STR(g_hashHead,parent,s);
        }
        return s;
    }
    
    void Union(struct HashMap *a, struct HashMap *b) 
    { 
        struct HashMap *aParent = Find(a);
        struct HashMap *bParent = Find(b);
        //printf("FIND a %s parent %s %s\r\n",a->key,aParent->key,aParent->parent);
        //printf("FIND b %s parent %s %s\r\n",b->key,bParent->key,bParent->parent);
        if(strcmp(aParent->parent, bParent->parent) != 0) { 
            (void)UpadatHash(bParent->key, aParent->name, aParent->parent);
            (void)UpadatHash(b->key, aParent->name, aParent->parent);
        }
        return;
    }
    
    void ProcessAccount(char *** accounts, int accountsSize, int* accountsColSize)
    { 
        struct HashMap *a = NULL;
        struct HashMap *b = NULL;
        for (int i = 0; i < accountsSize; i++) { 
            a = NULL;
            b = NULL;
            char *name = accounts[i][0];
            char *key = accounts[i][0];
            char *parent = accounts[i][0];
            for(int j = 1; j < accountsColSize[i]; j++) { 
                key = accounts[i][j];
                parent = accounts[i][j];
                if(j == 1) { 
                    a = InsertHash(key, name, parent);
                    continue;
                }else{ 
                    b = InsertHash(key, name, parent);
                }
                Union(a,b);
            }
        }
        return;
    }
    
    bool IsSameParent(char *aKey, char *bKey)
    { 
        struct HashMap *a = NULL;
        struct HashMap *b = NULL;
        HASH_FIND_STR(g_hashHead,aKey,a);
        HASH_FIND_STR(g_hashHead,bKey,b);
        struct HashMap *aParent = Find(a);
        struct HashMap *bParent = Find(b);
        if(aParent != bParent) { 
            return false;
        }
        return true;
    }
    
    int SortCmp(const void *a, const void *b)
    { 
        char *aPtr = *(char**)a;
        char *bPtr = *(char**)b;
        return strcmp(aPtr,bPtr); 
    }
    
    int GetResIndex(char *key)
    { 
        struct HashMap *s = NULL;
        HASH_FIND_STR(g_hashHead,key,s);
        for(int i = 0; i < g_resIndex; i++) { 
            if(g_col[i] > 1) { 
                if(IsSameParent(s->parent, g_res[i][1])) { 
                    return i;
                }
            }
        }
        return -1;
    }
    
    void OutPutRes() 
    { 
        struct HashMap *s = NULL;
        struct HashMap *tmp = NULL;
        char parent[MAXSTRLEN] = { 0};
        HASH_ITER(hh,g_hashHead,s,tmp) { 
            int resIndex = GetResIndex(s->key);
            if(resIndex == -1) { 
                g_res[g_resIndex][0] = calloc(MAXSTRLEN, sizeof(char));
                strcpy(g_res[g_resIndex][0],s->name);
                g_res[g_resIndex][1] = calloc(MAXSTRLEN, sizeof(char));
                strcpy(g_res[g_resIndex][1],s->key);
                g_col[g_resIndex] = 2;
                g_resIndex++;
            }else{ 
                int index = g_col[resIndex];
                g_res[resIndex][index] = calloc(MAXSTRLEN, sizeof(char));
                strcpy(g_res[resIndex][index],s->key);
                g_col[resIndex]++;
            }
        }
        return;
    }
    
    void PrintHash()
    { 
        struct HashMap *s = NULL;
        struct HashMap *tmp = NULL;
        printf("PrintHash:\r\n");
        HASH_ITER(hh,g_hashHead,s,tmp) { 
            printf("hash: %s %s %s\r\n",s->name,s->key,s->parent);
        }
        return;
    }
    
    void PrintRes()
    { 
        for (int i = 0; i < g_resIndex; i++) { 
            for(int j = 0; j < g_col[i]; j++) { 
                printf("%s ",g_res[i][j]);
            }
            printf("\r\n");
        }
        return;
    }
    
    void SortRes()
    { 
        for(int i = 0; i < g_resIndex; i++) { 
            qsort(&g_res[i][1], g_col[i] - 1, sizeof(char*), SortCmp);//去掉NAME后 开始排序
        }
        return;
    }
    
    char *** accountsMerge(char *** accounts, int accountsSize, int* accountsColSize, int* returnSize, int** returnColumnSizes){ 
        InitMem(accountsSize);
        ProcessAccount(accounts, accountsSize, accountsColSize);
        //PrintHash();
        OutPutRes();
        SortRes();
        //PrintRes();
        FreeMem();
        *returnSize = g_resIndex;
        *returnColumnSizes = g_col;
        return g_res;
    }

**运行结果：**  
![在这里插入图片描述][20210118085850585.png_pic_center]

**Notes：**  
参考文档：[https://leetcode-cn.com/problems/accounts-merge/solution/cyu-yan-bing-cha-ji-hashjie-fa-by-tan-shao-yu-dou-/][https_leetcode-cn.com_problems_accounts-merge_solution_cyu-yan-bing-cha-ji-hashjie-fa-by-tan-shao-yu-dou-]

[20210118085850585.png_pic_center]: /images/20221119/7193f36530e3421d8a2443abd0b21ffe.png
[https_leetcode-cn.com_problems_accounts-merge_solution_cyu-yan-bing-cha-ji-hashjie-fa-by-tan-shao-yu-dou-]: https://leetcode-cn.com/problems/accounts-merge/solution/cyu-yan-bing-cha-ji-hashjie-fa-by-tan-shao-yu-dou-/