空格替换

数据结构和算法►字符串 评论

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时停止循环。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

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

呼延十Developer

个人简介。