350-替换或删除空格

朴灿烈づ我的快乐病毒、 2022-09-01 14:54 119阅读 0赞

## 1、替换空格算法 ##

**将空格替换为20%**

**算法1**：额外创建一个数组，如果是非空格，复制到新的数组，如果是空格，不复制，直接在新的数组中写20%。  
**时间复杂度度**：O(n)  
**空间复杂度**：O(n)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]

void ReplaceBlank1(char *str)
    {
        
    	assert(str != NULL);
    	int count = 0;//统计空格的数量
    	int i;
    	for(i=0;str[i]!='\0';i++)//统计空格数量
    	{
        
    		if(str[i] == ' ')
    			count++;
    	}
    	char *buf = (char *)malloc(2*count+strlen(str)+1);//新数组
    	//每一个空格增加2个位置，%20
    	int j = 0;//buf的下标
    	assert(buf != NULL);
    	for(i=0;str[i]!= '\0';i++)
    	{
        
    		if(str[i] != ' ')//非空格,直接复制
    			buf[j++] = str[i];
    		else //空格,不复制,在新数组中添加%20
    		{
        
    			buf[j++] = '%';
    			buf[j++] = '2';
    			buf[j++] = '0';
    		}
    	}
    	buf[j] = '\0';
    
    	strcpy(str,buf);//将新数组的内容复制到原字符串中
    	free(buf);
    }

**算法2**：通过计算空格数量,从后往前,直接在原字符串中修改  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
有3个空格，所以\\0要向后移动6个位置。

void ReplaceBlank(char *str)//O(n),O(1)
    {
        
    	int count = 0;//空格数量
    	for(int i=0;str[i]!='\0';i++)//统计空格的数量
    	{
        
    		if(str[i] == ' ')
    			count++;
    	}
    	//从后往前遍历字符串
    	int i = strlen(str);//当前需要处理的字符下标
    	int j = i + 2*count;//当前可以存放数据的下标
    	for(; i>=0; i--)
    	{
        
    		if(str[i] != ' ')//非空格,直接后移
    			str[j--] = str[i];
    		else//空格,不后移,直接在后面添加%20
    		{
        
    			str[j--] = '0';
    			str[j--] = '2';
    			str[j--] = '%';
    		}
    	}
    }

## 将字符串中连续的空格删除到只保留一个 ##

**算法1:**  
**时间复杂度O(n)  
空间复杂度O(n）**  
![\*\*\*\*][b0b6f32245a242dcada470ee87729d2d.png]

//算法1:创建一个新数组,从头到尾遍历原字符串
    //如果当前不是连续空格则复制该字符,如果是则不复制
    void DelBlank1(char *str)//O(n),O(n)
    {
        
    	assert(str != NULL);
    	char *buf = (char*)malloc(strlen(str)+1);//创建新数组
    	assert(buf != NULL);
    
    	int i = 0;//原字符串下标
    	int j = 0;//新数组下标
    	for( ;str[i]!= '\0';i++)
    	{
        
    		if(str[i]!=' ' || str[i+1]!=' ')//非连续空格
    		{
        
    			buf[j++] = str[i];
    		}
    	}
    	buf[j] = '\0';
    
    	strcpy(str,buf);
    	free(buf);
    }

**算法2：**  
**我们要从前往后遍历**  
**在原字符串中直接修改**  
![在这里插入图片描述][13fbf924220f4527804cc24c6498f22e.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]

**时间复杂度O(n)  
空间复杂度O(1)**

void DelBlank(char *str)
    {
        
    	int i = 0;//当前需要处理的字符下标
    	int j = 0;//当前可以存放数据的下标
    	while(str[i]!= '\0')
    	{
        
    		if(str[i]!=' ' || str[i+1]!=' ')//非连续空格,需要复制
    			str[j++] = str[i++];
    		else //连续空格,不需要复制数据
    			i++;
    	}
    	str[j] = '\0';
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/ef17dbdc5c4f438ca4630619d64d3af4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/b487111f930b45919dbbfd2a87766e23.png
[b0b6f32245a242dcada470ee87729d2d.png]: /images/20220829/1ab1c6a4df5540738db772321286de08.png
[13fbf924220f4527804cc24c6498f22e.png]: /images/20220829/5dd2fcf9a5dc4691b7dc3dd55a0f8af0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/b2812d1e1e5f47b5a3492b6a1af03fa4.png