刪除空格時間0(n),空間o(1)

刪除空格要求時間0(n),空間o(1)。這類型題目經常出現在筆試或者面試中，故我將此類問題做一總結。

     方法一：

[cpp]
int findKg(char* str,int st) 
{ 
    for( ; str[st] != '\0'; ++st) 
    { 
        if(str[st] == ' ') 
        { 
            return(st); 
        } 
    } 
    return(-1); 
} 
 
int findCh(char* str,int st) 
{ 
    for( ; str[st] != '\0'; ++st) 
    { 
        if(str[st] != ' ') 
        { 
            return(st); 
        } 
    } 
    return(-1); 
} 
 
void eraseKg(char* str) 
{ 
    int kg,ch; 
    kg = ch = -1; 
    while(1) 
    { 
        kg = findKg(str,kg + 1); 
        ch = findCh(str,kg + 1); 
 
        if(kg == -1 || ch == -1) 
        { 
            break; 
        } 
 
        swap(str[kg],str[ch]); 
    } 
 
    for(int i = 0; str[i] != '0'; ++i) 
    { 
        if(str[i] == ' ') 
        { 
            str[i] = '\0'; 
            return; 
        } 
    } 
} 

int findKg(char* str,int st)
{
 for( ; str[st] != '\0'; ++st)
 {
  if(str[st] == ' ')
  {
   return(st);
  }
 }
 return(-1);
}

int findCh(char* str,int st)
{
 for( ; str[st] != '\0'; ++st)
 {
  if(str[st] != ' ')
  {
   return(st);
  }
 }
 return(-1);
}

void eraseKg(char* str)
{
 int kg,ch;
 kg = ch = -1;
 while(1)
 {
  kg = findKg(str,kg + 1);
  ch = findCh(str,kg + 1);

  if(kg == -1 || ch == -1)
  {
   break;
  }

  swap(str[kg],str[ch]);
 }

 for(int i = 0; str[i] != '0'; ++i)
 {
  if(str[i] == ' ')
  {
   str[i] = '\0';
   return;
  }
 }
}     方法二:

[cpp]
void eraseKg1(char* str) 
{ 
    int i,j; 
    i = -1; 
    for(j = 0; str[j] != '\0'; ++j) 
    { 
        if(str[j] != ' ') 
        { 
            str[++i] = str[j]; 
        } 
    } 
    str[++i] = '\0'; 
} 

void eraseKg1(char* str)
{
 int i,j;
 i = -1;
    for(j = 0; str[j] != '\0'; ++j)
 {
  if(str[j] != ' ')
  {
   str[++i] = str[j];
  }
 }
 str[++i] = '\0';
}題目變形：將連續的多余一個的空格只剩一個

方法一：利用刪除空格算法，第一次遍歷數組要將連續空格的第一個空格修改為’\0’,調用刪除空格算法(刪除空格算法中遍歷字符串不能用str[j]!=’\0’判斷循環結束,而是在第一次遍歷中記錄字符串長度)，最後將空格修改回來即可。

方法二：類似刪除空格算法的方法二，只是將連續空格當成一個字符處理

[cpp]
//有連續空格只保留一個  
void erasekg2(char* str) 
{ 
    int i,j; 
    i = -1; 
    for(j = 0; str[j] != '\0'; ++j) 
    { 
        //兩個以上的空格作為一個字符處理  
        while(str[j] == ' ' && str[j] == str[j + 1]) 
        { 
            ++j; 
        } 
        str[++i] = str[j]; 
    } 
    str[++i] = '\0'; 
} 

//有連續空格只保留一個
void erasekg2(char* str)
{
 int i,j;
 i = -1;
 for(j = 0; str[j] != '\0'; ++j)
 {
  //兩個以上的空格作為一個字符處理
  while(str[j] == ' ' && str[j] == str[j + 1])
  {
            ++j;
  }
        str[++i] = str[j];
 }
 str[++i] = '\0';
}
本題目還可以將刪除空格改成刪除指定字符。