牛客网-替换空格

目录

• 问题描述
• 示例
• 具体思路
• • 思路一
• 代码实现

问题描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题目链接: https://www.nowcoder.com/questionTerminal/4060ac7e3e404ad1a894ef3e17650423

示例

示例1
输入：w e a r e l u c k y
返回值：w e % 2 0 a r e % 2 0 l u c k y

示例2
输入：We Are Happy
返回值：We%20Are%20Happy

具体思路

思路一

虽然是替换问题，到那时生成的字符串整体变长了
因替换内容比被替换内容长，所以，一定涉及到字符串中字符的移动问题
移动方向一定是向后移动，所以现在的问题无非是移动多少的问题
因为是‘ ’ ->“%20”，是1换3，所以可以先统计原字符串中空格的个数（设为count），然后可以计算出新字符串的长度
所以：new_str=old_str+2*count
最后，定义新老索引（或者指针），各自指向新老空间的结尾，然后进行old->new的移动
如果是空格，就连续放入“%20”，其他平移即可
当然，C++和Java都有很多容器，也可以从前往后通过开辟空间来进行解决。也就是使用空间来换取时间
但是，我们最好不要在当前场景下这么做

  替换空格大致可分为以下三个步骤：
（1）遍历一遍字符串，统计字符串当中的空格数count。
（2）通过空格数count算出替换后字符串的新长度new_str
   因为一个空格字符会被替换为三个字符，所以替换后字符串的新长度new_str=length+2*count
（3）从后向前对字符串进行填充
   计算出替换后的字符串的长度后，我们可以在原字符串当中，从后往前进行填充。若遇到的不是空格，则将遍历到的字符从后往前进行填充。

  若遇到的是空格，则从后往前填充字符‘0’，‘2’，‘%’
  如此进行下去，直到字符串遍历完毕即可得到替换后的字符串。

代码实现

class Solution {
public:
    void replaceSpace(char *str,int length) {
        int count=0;
        char *start=str;
        while(*start)
        {
            //if(*start==' ')
            if(isspace(*start))
            {
                count++;
            }
            start++;
        }

        char* old_str=str+length;
        char* new_str=str+length+2*count;
        while(old_str>=str&&new_str>=str)
        {
            //if((*old_str)!=' ')
            if(!isspace(*old_str))
            {
                *new_str=*old_str;
                new_str--;
                old_str--;
            }
            else
            {
                *new_str--='0';
                *new_str--='2';
                *new_str--='%';
                old_str--;
            }
        }
    }
};