剑指offer - 替换空格

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/4060ac7e3e404ad1a894ef3e17650423

题意

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

题解

从头到尾依次复制，如果遇到空格将后面的字符依次后移，当然这很低效，最欢时间复杂度O(N*N)。可以用O(N)的额外空间来依次复制，遇到空格替换%20，时间复杂度O(N)。其实可以不用花这O(N)的空间，我们可以先计算出恭需要增加多大的空间，然后从尾到头填充字符，因为，长度不可能比原来短，所以直接在原来的数组空间操作即可，不用担心覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
	void replaceSpace(char *str,int length) {
	    int spaceCount=0;
        for(int i=0;i<length;i++){
            if(str[i]==' ') spaceCount++;
        }
        int j=length+spaceCount*2;
        str[j--] = 0;
        for(int i=length-1;i>=0;i--){
            if(str[i]==' '){
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
            }
            else{
                str[j--] = str[i];
            }
        }
	}
};

扩展题目

有两个有序的数组A和B，要将B插入到A中使得整个数组仍然有序。
其实是一样的，计算出两个数组的总长度，然后在A数组中从后往前依次填充，比较A数组和B数组将大的填入。