請教一道面試題

moonwhite999

最近去應(yīng)聘嵌入式開發(fā)，發(fā)現(xiàn)有一道題，基本每一個公司都會考
題目如下：
從一個給定的字符串，例如Student is study,中去掉給定的字符串，例如senu,最后得到的結(jié)果是
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;
}
但面試的都說這種算法用在嵌入式系統(tǒng)中效率太差，因?yàn)槲抑�前從沒有做過嵌入式系統(tǒng)開發(fā)，所以對效率問題不是那么敏感，請諸位指教應(yīng)該怎么實(shí)現(xiàn)好一些

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. }
    

復(fù)制代碼

這種題如果將效率那就空間換時間吧,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. }
    

復(fù)制代碼

ajianglaoka

1：ResultStr沒有申請空間,也沒有指到某一內(nèi)存區(qū).
2：其實(shí)沒有必要申請空間,假如SrcStr很大的話，浪費(fèi)很大空間,嵌入式系統(tǒng)資源有限,能不申請空間盡量別申請。
3：你上面的程序是錯誤的。SrcStr指針始終沒有變化。
4：面試官說的效率問題可能是指 同一個字符x出現(xiàn)在源字符串中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 發(fā)表
最近去應(yīng)聘嵌入式開發(fā)，發(fā)現(xiàn)有一道題，基本每一個公司都會考
題目如下：
從一個給定的字符串，例如Student is study,中去掉給定的字符串，例如senu,最后得到的結(jié)果是
tdnt i tdy

我是這樣做的
char * De ...

問題有點(diǎn)多哦

ExclusivePig

正則表達(dá)式呀。。

如果目標(biāo)平臺沒有正則的庫，移植個好了，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很大的話,有點(diǎn)浪費(fèi)空間.嵌入式嘛，能不浪費(fèi)空間就最好別浪費(fèi)。

gz80

思路就是空間換時間。用一個26字節(jié)的數(shù)組c來記錄哪些字母需要替換，然后掃描整個字符串，用其ascii碼-'a'或'A'來做下標(biāo)去查看是否需要替換。

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. }
    

復(fù)制代碼

[ 本帖最后由 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;
}


試試上面的代碼，我看可以滿足你的要求。