212. 空格替换先扩充，从后往前处理

和蔼的zhxing

发布于 2018-09-04 11:26:15

8060

发布于 2018-09-04 11:26:15

设计一种方法，将一个字符串中的所有空格替换成 %20 。你可以假设该字符串有足够的空间来加入新的字符，且你得到的是“真实的”字符长度。你的程序还需要返回被替换后的字符串的长度。

注意事项

如果使用 Java 或 Python, 程序中请用字符数组表示字符串。样例对于字符串"Mr John Smith", 长度为 13 替换空格之后，参数中的字符串需要变为"Mr%20John%20Smith"，并且把新长度 17 作为结果返回。

先扩充，从后往前处理

这个说是字符串，实际上是字符数组，并没有用c++STL的string来做，要是那样就太简单了，因为string本身支持+操作，只要遍历遇到空格用%20代替加上就可以了，如果是字符数组的话就难一些。容易想到的还是去遍历，遇到空格用%20来代替，从前向后遍历的话有一个问题，就是一个空格的地方放不下三个字符，要不先把后面的两个字符另外存起来，要不就会丢失数据，而且存起来是很麻烦的，因为要插入这个数据。还有一种方法是：新建一个字符数组，然后逐个去放，但是这个题要求原位处理，所以不行。

所以一个可行的思路是把原数组扩大，扩大的容量可以通过检查空格的个数来定，然后用两个指针，从后往前把字符放进去，遇到空格则连续放入%20，因为是从后往前，所以不会出现数据没有地方放的情况。画了个简单的图来说明每一步操作的结果。

其中blank_count是记录当前还有多少个空格没有遍历，这个量可以帮助我们找到要写入的字符的位置。而且每次处理完一个这个blank_count--。具体的处理细节见代码：

int replaceBlank(char string[], int length) {
        int blank_count=0;
        int new_length=length;
        for(int i=0;i<length;i++)
        {
            if(string[i]==32)
            blank_count++;
        }
        new_length+=blank_count*2;
        
        for(int i=length-1;i>=0;i--)
        {
            if(string[i]!=32)                   //如果不是空格，就把这个值放进去，从后往前
            {
                string[i+2*blank_count]=string[i];
            }
            else                                //如果是空格，则需把空格替换成三个字符`%20`
            {
                string[i+2*blank_count]='0';
                string[i+2*blank_count-1]='2';
                string[i+2*blank_count-2]='%';
                blank_count--;            //这个见1，则下次的遍历就会减3，因为这个要乘以2，再加上i要减一。
            }
            
        }
        return new_length;
        
        // write your code here
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.01.31 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度