剑指offer刷题（2）：空格替换

发表于 | 阅读次数:

剑指offer刷题（2）：空格替换

刷题平台：牛客网

空格替换

考点：

字符串

1、题目描述

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

2、解题思路

  • 1、思路一：从前往后依次查找空格，然后依次挪并且将空格替换成“%20”；该方法的计算复杂度为$O( n^2 )$
    ,因为空格后面的数据有可能重复的移动，所以该方法并不好。
  • 2、思路二：我们可以先扫面一遍字符串，然后记录下该字符串中的空格数num_space,然后替换玩以后的数据新的长度new_length应该为length+2*num_space，此时我们在从后往前不停的复制数据，并且在遇到了空格的时候将其替换成“%20”。在该方法中所有的数据只会被移动一次，所以计算复杂度为$O(n)$。

3、算法实现

C/C++实现

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
26
27
class Solution {
public:
	void replaceSpace(char *str,int length) {
        int num_space=0;
        for(int i=0;i<length;i++)
        {
            if(str[i]==' ')
            {
                num_space++;
            }
        }
        int new_length=length+2*num_space;
        for(int i=length;i>=0;i--)
        {
            if(str[i]!=' ')
            {
                str[new_length--]=str[i];
            }
            else
            {
                str[new_length--]='0';
                str[new_length--]='2';
                str[new_length--]='%';
            }
        }
	}
};