面試100 36在字符串中刪除指定的字符

   面試100 在字符串中刪除指定的字符

在字符串中刪除指定的字符
   輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。
   例如，輸入”They are students.”和”aeiou”，
    則刪除之后的第一個(gè)字符串變成”Thy r stdnts.”。

  (1)思路建立一個(gè)256位長(zhǎng)度bit數(shù)組，存儲(chǔ)第二個(gè)字符串的每個(gè)字符，遍歷第一個(gè)字符串的時(shí)候，根據(jù)hash映射，判斷該位是否需要?jiǎng)h除。
重要的一方面：進(jìn)行刪除操作
    遍歷第一個(gè)字符串的時(shí)候，記錄當(dāng)前已經(jīng)刪除的字符串個(gè)數(shù)del，然后將不被刪除的字符，向前移動(dòng)del位置。
    這樣的話整個(gè)字符串的操作的時(shí)間復(fù)雜度就為o(n)。 del初始為0      
  (2)思路2
     和第一種方法類似，設(shè)置了一個(gè)指針，deletePtr指向當(dāng)前刪除之后，后序指針預(yù)移動(dòng)的地方，沒(méi)移動(dòng)一個(gè)字符，deletePtr自增。

二 代碼如下：
     

#include <iostream>
 using namespace std ;
 const int N = 50 ;
 
 void del(char * p , char * hash)
 {
      int delcount = 0 ;//記錄已經(jīng)刪除的字符數(shù)目 
      char * s = p;
      while(*s)      
      {
         if(hash[*s])              
            delcount++ ;                           
          else
            *(s-delcount) = *s ;                                       
         s++ ;            
      }
      *(s-delcount) = '\0' ;
 }
 
 
 int main()
 {
   char s1[N] = "They are students." ; 
   char s2[N] = "aeiou" ;
   char hash[129] ;
   memset(hash , 0 ,sizeof(hash)) ;
   
   char * s = s2;
   while(*s)    //對(duì)第二個(gè)字符串映射hash函數(shù) 
     hash[*s++] = 1 ; 
   
   del(s1 , hash) ;
   cout<<s1<<endl;             
   
   system("pause") ;
   return 0;    
 }

posted on 2011-05-22 22:25 kahn 閱讀(1086) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 算法相關(guān)