37-将字符串中连续的空格删除,只保留一个空格（算法）

╰半橙微兮° 2022-12-22 08:59 16阅读 0赞

#include <stdio.h>
    #include <assert.h>
    #include <string.h>
    #include <stdlib.h>
    
    /*
    字符串替换:多换一,一换一,一换多
    */
    //将字符串中连续的空格删除,只保留一个空格.例如"a b   c     d"->"a b c d"
    //算法1:如果是连续空格,则删除后一个空格(将后面所有字符往前移),O(n^2),O(1)
    void DelBlank1(char *str)//O(n^2),O(1)
    {
        
    	for(int i=0;str[i]!='\0';)
    	{
        
    		if(str[i]==' ' && str[i+1]==' ')//连续空格
    		{
        
    			for(int j=i+1;str[j]!='\0';j++)
    			{
        
    				str[j] = str[j+1];
    			}
    		}
    		else
    		{
        
    			i++;
    		}
    	}
    }
    
    //算法2,利用空间换时间
    void DelBlank2(char *str)//O(n),O(n)
    {
        
    	char *tmp = (char *)malloc(strlen(str)+1);//保存处理好的字符串
    	int i = 0;//str下标
    	int j = 0;//tmp下标
    
    	while(str[i] != '\0')//O(n)
    	{
        
    		if(str[i]==' ' && str[i+1]==' ')//连续空格,不复制
    		{
        
    			i++;
    		}
    		else
    		{
        
    			tmp[j++] = str[i++];
    		}
    	}
    	tmp[j] = '\0';
    
    	strcpy(str,tmp);
    	free(tmp);
    }
    
    //算法3,直接在原数组中替换
    void DelBlank(char *str)//O(n),O(1)
    {
        
    	int i = 0;//遍历字符串str
    	int j = 0;//当前存放数据的下标
    	while(str[i] != '\0')
    	{
        
    		if(str[i]==' ' && str[i+1]==' ')//连续空格,不复制
    		{
        
    			i++;
    		}
    		else
    		{
        
    			str[j++] = str[i++];
    		}
    	}
    	str[j] = '\0';
    }
    
    int main()
    {
        
        char str[] = "a b  c     d       e";
    	DelBlank(str);
    	printf("%s\n",str);
    	return 0;
    }