请教一道面试题

moonwhite999

最近去应聘嵌入式开发，发现有一道题，基本每一个公司都会考
题目如下：
从一个给定的字符串，例如Student is study,中去掉给定的字符串，例如senu,最后得到的结果是
tdnt i tdy

我是这样做的
char * DeleteStr(char *SrcStr,char *ReplaceStr)
{

        char * ResultStr;
        int n = strlen(SrcStr);
        int j=0;
        for(int i = 0;i<n;i++)
        {
               if(strchr(ReplaceStr,SrcStr)==0)
               {
                     ResultStr[j++] = SrcStr;
                }
         }
         return ResultStr;
}
但面试的都说这种算法用在嵌入式系统中效率太差，因为我之前从没有做过嵌入式系统开发，所以对效率问题不是那么敏感，请诸位指教应该怎么实现好一些

ubuntuer

你自己的程序修正

1. 
   
2. 
   
3. char* DeleteStr1(char *SrcStr,char *ReplaceStr)
   
4. {
   
5.   int n = strlen(SrcStr);
   
6.   int j = 0;
   
7.   int i = 0;
   
8.   char* ResultStr = SrcStr;
   
9. 
   
10.   for(i = 0;i<n;i++)
    
11.    {
    
12.      if(strchr(ReplaceStr,SrcStr[i])==0)
    
13.       {
    
14.        ResultStr[j++] = SrcStr[i];
    
15.       }
    
16.    }
    
17.    ResultStr[j]='\0';
    
18.    return ResultStr;
    
19. }
    

复制代码

这种题如果将效率那就空间换时间吧,hash的思路,O(1)查找单个字母.思路大致如下,仅仅是思路,希望大家别拍砖!!!
不考虑大小写,删除的是a-z

1. 
   
2. 
   
3. char* DeleteStr2(char *SrcStr,char *ReplaceStr)
   
4. {
   
5.   int j = 0;
   
6.   int i = 0;
   
7.   char* ResultStr = SrcStr;
   
8.   int A[26];
   
9.   
   
10.   for(i=0;i<26;i++)
    
11.     A[i]=0;
    
12.   
    
13.   i=0;  
    
14.   while(ReplaceStr[i]!='\0')
    
15.    {
    
16.      A[ReplaceStr[i]-'a']=1;
    
17.      i++;
    
18.    }
    
19.   
    
20.   i=0;   
    
21.   while(SrcStr[i]!='\0')
    
22.    {
    
23.      if(SrcStr[i]<'a'||A[SrcStr[i]-'a']==0)
    
24.        ResultStr[j++] = SrcStr[i];
    
25.      i++;  
    
26.    }
    
27.    
    
28.    ResultStr[j]='\0';
    
29.    return ResultStr;
    
30. }
    

复制代码

ajianglaoka

1：ResultStr没有申请空间,也没有指到某一内存区.
2：其实没有必要申请空间,假如SrcStr很大的话，浪费很大空间,嵌入式系统资源有限,能不申请空间尽量别申请。
3：你上面的程序是错误的。SrcStr指针始终没有变化。
4：面试官说的效率问题可能是指 同一个字符x出现在源字符串中n次你的算法就要查找n次字符x。
5： strchr的原型是：char *strchr(const char *s, int c);

[ 本帖最后由 ajianglaoka 于 2009-9-16 09:26 编辑 ]

huangwei0413

原帖由 moonwhite999 于 2009-9-16 09:04 发表
最近去应聘嵌入式开发，发现有一道题，基本每一个公司都会考
题目如下：
从一个给定的字符串，例如Student is study,中去掉给定的字符串，例如senu,最后得到的结果是
tdnt i tdy

我是这样做的
char * De ...

问题有点多哦

ExclusivePig

正则表达式呀。。

如果目标平台没有正则的库，移植个好了，pcre...哈哈

epegasus

嵌入式哪有靠算法效率的?这不是扯么?

liklone

char * DeleteStr(char *SrcStr,char *ReplaceStr) {         char *ResultStr=new char[strlen(SrcStr)+1];         int n = strlen(ReplaceStr);                 int nFlag = 0; //Flag为1，则不拷贝                 int j=0,k=0;                 while((*SrcStr) != '\0')                 {                         nFlag = 0;                         for(int i=0;i<n;i++)                         {                                 if(*SrcStr == ReplaceStr)                                 {                                         nFlag = 1;                                         break;                                 }                         }                         if(1 == nFlag)                                 {SrcStr++;continue;}                         ResultStr[j] = *SrcStr;                         j++;                         SrcStr++;                 }          return ResultStr; }

[ 本帖最后由 liklone 于 2009-9-16 14:53 编辑 ]

ajianglaoka

char *ResultStr=new char[strlen(SrcStr)+1];


假如SrcStr很大的话,有点浪费空间.嵌入式嘛，能不浪费空间就最好别浪费。

gz80

思路就是空间换时间。用一个26字节的数组c来记录哪些字母需要替换，然后扫描整个字符串，用其ascii码-'a'或'A'来做下标去查看是否需要替换。

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include <malloc.h>
   
5. 
   
6. char c[26] = {0};
   
7. 
   
8. void setflg(char* str, int len)
   
9. {
   
10.   for(int i = 0; i < len; i++)
    
11.   {
    
12.     char idx = (str[i] >= 'A' && str[i] <= 'Z')?(str[i] - 'A'):(str[i] - 'a');
    
13.     c[idx] = 1;
    
14.   }
    
15. }
    
16. 
    
17. void compareStr(char* str, int len)
    
18. {
    
19.   for(int i=0;i < len; i ++)
    
20.   {
    
21.     char idx = (str[i] >= 'A' && str[i] <= 'Z')?(str[i] - 'A'):(str[i] - 'a');
    
22.     if (c[idx] == 1)
    
23.     {
    
24.        str[i] = '\0';
    
25.     }
    
26.   }  
    
27. }
    
28. 
    
29. void trimStr(char* inStr, char* outStr, int len)
    
30. {
    
31.   int idx = 0;
    
32.   for(int i = 0; i < len; i++)
    
33.   {
    
34.     if(inStr[i] != '\0')
    
35.     {
    
36.       outStr[idx] = inStr[i];
    
37.       idx++;
    
38.     }
    
39.   }
    
40. }
    
41. 
    
42. main()
    
43. {
    
44.   char a1[] = "Student is study";
    
45.   char a2[] = "senu";
    
46.   int len1 = strlen(a1);
    
47.   int len2 = strlen(a2);
    
48.   setflg(a2, len2);
    
49.   compareStr(a1, len1);
    
50.   char* outStr = (char*)malloc(sizeof(a1));
    
51.   memset(outStr, 0, sizeof(a1));
    
52.   trimStr(a1, outStr, len1);
    
53.   printf("%s\n", outStr);
    
54.   free(outStr);
    
55. }
    

复制代码

[ 本帖最后由 gz80 于 2009-9-16 17:47 编辑 ]

ljmmail

char * DeleteStr(char *src,  char *rstr )
{
      char     *p ,
                  *p1;
       p =  p1 = src ;
      while ( *p ){
          if(strchr(rstr,  *p ) == NULL)  *p1 ++ = *p;
          p ++;
      }
      *p1 = 0x00;
      return   src;
}


试试上面的代码，我看可以满足你的要求。