剑指offer-替换空格

一、解题思想

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

看到这个题目，我第一想到的是，把字符串遍历一遍，每遇到一个空格就把空格替换成”%20“，由于是把一个字符替换成3个字符，所以我们必须把后面所有的字符都向后移动2个字符位置，否则就有两个字符背覆盖掉。
但是这样的做法，会使得时间复杂度为O(N^2)，我们还有没有更优的方法来解答这个题呢，答案是有的。

我们把字符串先遍历一遍，把字符串的个数（包含空格）和空格的个数保存下来；由此我们可以计算出替换之后字符串总大小了，字符串个数+空格个数*2；然后我们定义两个指针，p1 和 p2，p1用来指向原始字符串的末尾，p2用来指向替换后字符串总数量的末尾，接下来我们移动p1，逐个把它指向的字符复制到p2所指向的位置，知道遇到第一个空格为止。当遇到第一个空格时 ，把p1向前移动一个位置，在p2前插入”%20“，%20的长度是3，所有p2也要向前移动3个位置。当p1和p2指向同一个位置时，说明字符串中的空格已经被全部替换完成。
如图所示:

这个算法所有的字符都只需要移动一次，所以这个时间复杂度是O(N);

二、代码的实现

void ReplaceBlank(char str[], int length)
{if (str == NULL || length <= 0)return;//originalLength 总字符长度，不包含\\0int originalLength = 0;//numberOfBlank 空格个数int numberOfBlank = 0;int i = 0;while (str[i] != '\\0'){++originalLength;if (str[i] == ' ')++numberOfBlank;++i;}//printf("%d\\n", originalLength); //13//printf("%d\\n", numberOfBlank); //2//newLength 加上修改后的字符串的总长度 ：17int newLength = originalLength + (numberOfBlank * 2);//如果newLength大于总容量大小则退出if (newLength > length)return;int indexOfOriginal = originalLength;int indexOfNew = newLength;//循环条件while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal){//原尾下标位置为0时，让新尾下标--，同时给字符，if (str[indexOfOriginal] == ' '){str[indexOfNew--] = '0';str[indexOfNew--] = '2';str[indexOfNew--] = '%';}//否则就把原尾下标--，把值给新尾else{str[indexOfNew--] = str[indexOfOriginal];}//indexOfOriginal原尾下标--要放在这，因为不管是为空还是赋值都需要indexOfOriginal----indexOfOriginal;}
}int main()
{char str[30] ="We are  happy.";int length = sizeof(str) / sizeof(str[0]);ReplaceBlank(str, length);printf("%s", str);return 0;
}

三、总结

整个题目的思路：

1.计算字符串的长度和字符串中空格的长度；

2.计算出被替换后字符串的长度：字符串长度+空格长度*2

3.使用两个指针p1和p2，p1指向原始字符串末尾，p2指向被替换后的字符串的末尾，如果字符串中的字符是空格则在p2之前插入”%20“，如果p1指向的字符不是空格，则把p1的字符拷贝到p2；直到p1指向的位置等于p2指向的位置，此时说明字符串中空格已经被全部替换了，循环结束。