面试题5-替换空格

红太狼 2022-03-12 14:22 200阅读 0赞

# 一、题目 #

### **       题目：**请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。　 ###

# 二、题目分析 #

###         最直观的做法是**从头到尾扫描字符串**，每一次碰到空格字符的时候做替换。由于是把1个字符替换成3个字符，我们必须要把空格后面所有的字符都后移两个字节，否则就有两个字符被覆盖了。这样的话，时间复杂度太高。 ###

###        所以通常采用的做法是从尾到头。先遍历一次字符串，这样就能统计出字符串中空格的总数，并可以由此计算出替换之后的字符串的总长度。然后从字符串的后面开始复制和替换。准备两个指针，P1和P2。P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾。接下来向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。接着向前复制，直到碰到第二、三或第n个空格。 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDAzOTE3_size_16_color_FFFFFF_t_70][]

# 三、代码实现 #

//len 为字符数组str的总容量，大于或等于字符串str的实际长度,大于字符串替换后的长度
    void func(char s[], int len) {
    	if (s == nullptr && len <= 0) return;// 边界检查1：判断字符数组是否为空
    	int count=0;//用于计数（空格的数量）
    	int oldlen = 0;//用于存储就数组的元素个数
    	int k = 0;
    	// 遍历字符串，统计空格个数、替换前字符个数
    	//oldlen 为字符串str的实际长度
    	while(s[k] != '\0') {
    		++oldlen;
    		if (s[k] == ' ') count++;
    		++k;
    	}
    	if (count == 0) return;//若空格字数为0，则无需替换
    	int newlen = oldlen + 2 * count;//字符数组替换后新长度
    	if (newlen > len) return;// 边界检查：判断字符数组是否越界
    	int i = oldlen, j = newlen;
    	while (i >= 0 && j >i) {//数组从后往前循环
    		if (s[i] != ' ') {//依次复制字符串内容
    			s[j] = s[i]; j--; i--;
    		}
    		else {//替换空格
    			i--; s[j--] = '0'; s[j--] = '2'; s[j--] = '%';
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDAzOTE3_size_16_color_FFFFFF_t_70]: /images/20220312/4bacf4203bc94726aa2a7c98fd638c5e.png