空格替换

Posted1 by 呼延十 on September 25, 2018 Hot:

1.空格替换

来源: lintcode-空格替换

问题描述

描述

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

你的程序还需要返回被替换后的字符串的长度。

样例

对于字符串”Mr John Smith”, 长度为 13

替换空格之后,参数中的字符串需要变为”Mr%20John%20Smith”,并且把新长度 17 作为结果返回。

挑战

在原字符串(字符数组)中完成替换,不适用额外空间

解决思路

这道题的暴躁版本呢,就是依次遍历,当遇到空格时,将空格后的字符依次后移两位,这样就腾出了3个空位,插入%20即可。

机制版本的思路呢?

暴躁版本的问题就是,我们一次次的将后面的字符后移两位,有很多的重复操作,有没有可能一次性将字符移动到他最终的位置呢?

我们以hello world为例。

  1. 我们可以拿到当前字符串的长度为11,然后遍历一次后,拿到字符串中空格的数量1,将 L + 2 * n = 13就是最终字符串的长度。

  2. 设置两个指针,一个i=11指向原字符串末尾,一个j = 11指向新字符串末尾。

  3. 以i遍历原字符串,当i位置字符不等于空格,令j位置=i位置,如果i位置为空格,则给j,j-1,j-2位置依次放置0,2,%。

  4. 当i<0时停止循环。

实现代码

if(0==length) return 0;
        int num = 0;
        for(int i=0;i<length;i++){
            if(string[i] == ' ') num++;
        }

        int newLen = length + num*2;
        string[newLen] = 0;
        int j = 1;
        for(int i=length-1;i>=0;i--){
            if(string[i] != ' '){
                string[newLen - j] = string[i];
                j++;
            }
            else{
                string[newLen - j] = '0';
                j++;
                string[newLen - j] = '2';
                j++;
                string[newLen - j] = '%';
                j++;
            }
        }
        return newLen;
    }





ChangeLog

2018-09-22 添加第一题

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十