C语言leecode刷题记录

1736809

编程小白，最近在学C语言，想着练一练，并发帖记录一下
49. 字母异位词分组


字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
花了1个多小时，总算做出来了。

就是消耗内存很大，求大佬指点，提出改进的思路

[C] 纯文本查看 复制代码

struct pair{
    char * s1;
    char * s1_qsort;
 };
 typedef struct pair Pair;
 int cmp(void *a,void *b)
 {
    return (*(char *)a -  *(char *)b);
    //return ( *(int*)a - *(int*)b );
 }
 int paircmp(void *a,void *b)
 {
    Pair * Pa=(Pair*)a;
    Pair * Pb=(Pair*)b;
    return strcmp(Pa->s1_qsort,Pb->s1_qsort);
 }
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize=0;
    * returnColumnSizes=NULL;
    char***res=NULL;
    Pair * pairs=(Pair *)malloc(sizeof(Pair)*strsSize);

    for(int i=0;i<strsSize;i++)
    {
        pairs[i].s1=strs[i];
        pairs[i].s1_qsort=(char*)malloc(sizeof(char)*(strlen(strs[i])+1));
        strcpy(pairs[i].s1_qsort,pairs[i].s1);
        qsort(pairs[i].s1_qsort,strlen(strs[i]),sizeof(char),cmp);
        
    }
    qsort(pairs,strsSize,sizeof(Pair),paircmp);
    int group=-1;//记录最后组坐标
    int index=0;//记录组内坐标
    for(int i=0;i<strsSize;i++)
    {
        
            if(i==0||strcmp(pairs[i-1].s1_qsort,pairs[i].s1_qsort)!=0)//no equal
            {
                group++;
                index=0;
                *returnSize=group+1;//group++
        
                *returnColumnSizes=(int*)realloc(*returnColumnSizes,sizeof(int)*(group+1));
                (*returnColumnSizes)[group]=index+1;
                res=(char***)realloc(res,sizeof(char**)*(group+1));
                res[group]=(char**)malloc(sizeof(char*)*(index+1));
            }
            else//equal
            {
                index++;
                (*returnColumnSizes)[group]=index+1;
                res[group]=(char**)realloc(res[group],sizeof(char*)*(index+1));
            }
             res[group][index]=(char*)malloc(sizeof(char)*(strlen(pairs[i].s1)+1));  
            strcpy(res[group][index],pairs[i].s1);               
    }
    return res;
}

2024年5月4日更新

我把realloc相关函数删掉了，改成先计算组数和每组的个数，内存下降了很多，特地分享下成功的喜悦


优化后的代码：

[C] 纯文本查看 复制代码

 struct pair{
    char * s1;
    char * s1_qsort;
 };
 typedef struct pair Pair;
 int cmp(void *a,void *b)
 {
    return (*(char *)a -  *(char *)b);
    //return ( *(int*)a - *(int*)b );
 }
 int paircmp(void *a,void *b)
 {
    Pair * Pa=(Pair*)a;
    Pair * Pb=(Pair*)b;
    return strcmp(Pa->s1_qsort,Pb->s1_qsort);
 }
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    int NofG[10000]={0};//记录每组总个数
    int Gs=0,Gc=0;
    *returnSize=0;
    * returnColumnSizes=NULL;
    char***res=NULL;
    Pair * pairs=(Pair *)malloc(sizeof(Pair)*strsSize);

    for(int i=0;i<strsSize;i++)
    {
        pairs[i].s1=strs[i];
        pairs[i].s1_qsort=(char*)malloc(sizeof(char)*(strlen(strs[i])+1));
        strcpy(pairs[i].s1_qsort,pairs[i].s1);
        qsort(pairs[i].s1_qsort,strlen(strs[i]),sizeof(char),cmp);
        
    }
    qsort(pairs,strsSize,sizeof(Pair),paircmp);
    for(int i=0;i<strsSize;i++)
    {
        
        if(i==0)//no equal
        {
            Gc=1;
            
        }
        else
        {
            if(strcmp(pairs[i-1].s1_qsort,pairs[i].s1_qsort)!=0)//no equal
            {
                
                NofG[Gs]=Gc;
                //printf("%d NofG[Gs]=%d\n",i,NofG[Gs]);
                Gc=1;
                Gs++;

            }
            else
            {
                Gc++;

            }
            
            
        }


    }
    NofG[Gs++]=Gc;
    res=(char***)malloc(sizeof(char**)*Gs);
    *returnColumnSizes=(int*)malloc(sizeof(int)*(Gs));
    *returnSize=Gs;
    for(int i=0;i<Gs;i++)
    {
        res[i]=(char**)malloc(sizeof(char*)*(NofG[i]));
        (*returnColumnSizes)[i]=NofG[i];

    }
    
    int group=-1;//记录最后组坐标
    int index=0;//记录组内坐标

    for(int i=0;i<strsSize;i++)
    {
        
            if(i==0||strcmp(pairs[i-1].s1_qsort,pairs[i].s1_qsort)!=0)//no equal
            {
                group++;
                index=0;
            }
            else//equal
            {
                index++;
              
            }
             res[group][index]=(char*)malloc(sizeof(char)*(strlen(pairs[i].s1)+1));  
            strcpy(res[group][index],pairs[i].s1);               
    }
    return res;
}

侃遍天下无二人

我猜可以用桶排序的思想来做，或者弱化一下，用Map<String, List<String>>更好实现，在C++里用 std::map<std::string, std::list<std::string>>  代替

[C++] 纯文本查看 复制代码

#include <iostream>
#include <map>
#include <list>
#include <string>

int main() {
    // 创建一个map，其中键是字符串，值是字符串列表
    std::map<std::string, std::list<std::string>> myMap;

    // 添加数据到map中
    myMap["fruits"].push_back("apple");
    myMap["fruits"].push_back("banana");
    myMap["vegetables"].push_back("carrot");
    myMap["vegetables"].push_back("lettuce");

    // 遍历map
    for (const auto& entry : myMap) {
        std::cout << "Key: " << entry.first << std::endl;
        std::cout << "Values: ";
        // 遍历当前键对应的list
        for (const auto& value : entry.second) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

侃遍天下无二人

写了个Java版本，你看看内存占用咋样，感觉不会少，毕竟偷了不少懒

[Java] 纯文本查看 复制代码

import java.util.*;

class ReorderMap {
    private final Map<String, List<String>> map = new TreeMap<>();
    private String strMap(String key) {
        char[] a = key.toCharArray();
        Arrays.sort(a);
        return new String(a);
    }
    public boolean put(String key_value) {
        String key = strMap(key_value);
        if(!map.containsKey(key)) {
            map.put(key, new LinkedList<>());
        }
        return map.get(key).add(key_value);
    }
    @Override
    public String toString() {
        return map.toString();
    }
}

public class Test {
    public static void main(String[] args) {
        String[] str = {"eat", "tea", "tan", "ate", "nat", "bat"};
        ReorderMap reorderMap = new ReorderMap();
        for (String s : str) {
            reorderMap.put(s);
        }
        System.out.println(reorderMap);
    }
}

输出结果：

{abt=[bat], aet=[eat, tea, ate], ant=[tan, nat]}

1736809

侃遍天下无二人 发表于 2024-5-3 15:53
我猜可以用桶排序的思想来做，或者弱化一下，用Map更好实现，在C++里用 std::map  代替

[mw_shl_code=cp ...

C++正在学习中，其实是想要C版本的优化，还是表示感谢

1736809

侃遍天下无二人 发表于 2024-5-3 16:07
写了个Java版本，你看看内存占用咋样，感觉不会少，毕竟偷了不少懒

[mw_shl_code=java,true]import java ...

不会JAVA，其实想要C语言版的，感谢回帖

你好，再见

C++中可以用unordered_map<vector<int>,vector<string>>
第一个vector中记录26个字母的出现次数，第二个vector中记录符合字母出现次数的单词，就能够实现记录下所有重排字母的单词
然后全部输出即可，
C还没想好怎么操作省时，我肯定三个for循环超时了
另外请问一下楼主这道题的评测网站是什么呀

1736809

你好，再见 发表于 2024-5-8 12:44
C++中可以用unordered_map
第一个vector中记录26个字母的出现次数，第二个vector中记录符合字母出现次数的 ...

leetcode.cn,一个刷题网站

vtor

能不能建立哈希表，比如ate这个字符串的值是‘a’ + 't' +'e'，,然后让哈希相等的认为相等

不对，不能用简单的方法计算哈希，，得在里面加上不同的权重，好难啊啊