C语言leecode刷题记录

1736809 发表于 2024-5-3 13:04

本帖最后由 1736809 于 2024-5-4 17:23 编辑

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

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

就是消耗内存很大，求大佬指点，提出改进的思路
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.s1=strs;
   pairs.s1_qsort=(char*)malloc(sizeof(char)*(strlen(strs)+1));
   strcpy(pairs.s1_qsort,pairs.s1);
   qsort(pairs.s1_qsort,strlen(strs),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.s1_qsort,pairs.s1_qsort)!=0)//no equal
         {
            group++;
            index=0;
            *returnSize=group+1;//group++

            *returnColumnSizes=(int*)realloc(*returnColumnSizes,sizeof(int)*(group+1));
            (*returnColumnSizes)=index+1;
            res=(char***)realloc(res,sizeof(char**)*(group+1));
            res=(char**)malloc(sizeof(char*)*(index+1));
         }
         else//equal
         {
            index++;
            (*returnColumnSizes)=index+1;
            res=(char**)realloc(res,sizeof(char*)*(index+1));
         }
         res=(char*)malloc(sizeof(char)*(strlen(pairs.s1)+1));
         strcpy(res,pairs.s1);
}
return res;
}

https://static.52pojie.cn/static/image/hrline/line1.png

https://static.52pojie.cn/static/image/hrline/line8.png

2024年5月4日更新

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

优化后的代码：
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={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.s1=strs;
   pairs.s1_qsort=(char*)malloc(sizeof(char)*(strlen(strs)+1));
   strcpy(pairs.s1_qsort,pairs.s1);
   qsort(pairs.s1_qsort,strlen(strs),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.s1_qsort,pairs.s1_qsort)!=0)//no equal
         {

            NofG=Gc;
            //printf("%d NofG=%d\n",i,NofG);
            Gc=1;
            Gs++;

         }
         else
         {
            Gc++;

         }


   }

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

}

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

for(int i=0;i<strsSize;i++)
{

         if(i==0||strcmp(pairs.s1_qsort,pairs.s1_qsort)!=0)//no equal
         {
            group++;
            index=0;
         }
         else//equal
         {
            index++;

         }
         res=(char*)malloc(sizeof(char)*(strlen(pairs.s1)+1));
         strcpy(res,pairs.s1);
}
return res;
}

侃遍天下无二人 发表于 2024-5-3 15:53

本帖最后由侃遍天下无二人于 2024-5-3 15:55 编辑

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

#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;
}

侃遍天下无二人 发表于 2024-5-3 16:07

本帖最后由侃遍天下无二人于 2024-5-3 16:08 编辑

写了个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=, aet=, ant=}

1736809 发表于 2024-5-4 13:14

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

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

1736809 发表于 2024-5-4 13:15

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

import java ...

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

你好，再见 发表于 2024-5-8 12:44

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

1736809 发表于 2024-5-9 09:22

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

leetcode.cn,一个刷题网站

vtor 发表于 2024-5-11 10:34

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

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

页: [1]

吾爱破解 - 52pojie.cn's Archiver

C语言leecode刷题记录