删除空格时间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';
}
本题目还可以将删除空格改成删除指定字符。

补充：软件开发 , C++ ,