剑指offer-替换空格

本文为剑指 offer 系列第六十五篇。
主要知识点为字符串，平常就是一个调库可以解决的问题，这里要自己来实现。

题目描述

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

解题思路

思路1

由于c++的char类型没有封装好的用来替换字符的方法，所以我们可以用python直接调用库来解决。

思路2

其实可以再申请一段空间作为res，然后依次的遍历原来的char，碰到非空格就直接加到res中，碰到空格就加上“%20”，最后将原来的指针指向新的res即可。

思路3

思路2存在一个问题就是需要再申请一段空间，其实可以直接在原来的char上进行操作。
按照正常情况，char字符串是以‘\0’为标识结束的，所以我们可以往后延长数据，延长（2*空格个数）个字节，因为本来的一个空格现在变成了‘20%’。
用两个指针分别指向原来的字符串和延长后字符串的最后一位，依次向前遍历，将非空格数据进行后移，将空格数据进行替换。
等到两个指针重合说明已经替换完成，从而这个问题就结束了。

解题代码

思路1代码

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串 
    # 直接调用替换函数 24ms 5868k
    def replaceSpace(self, s):
        # write code here
        return s.replace(' ','%20')

思路3代码

class Solution {
public:
    void replaceSpace(char *str,int length) {
        int spaceNum = 0;
        char *p = str;
        while(*p != '\0'){
            if(*p == ' '){
                spaceNum++;
            }
            p++;
        }
        char* last = p+spaceNum*2;
        while(p != last){
            if(*p == ' '){
                *(last--) = '0';
                *(last--) = '2';
                *(last--) = '%';
            }else{
                *(last--) = *(p);
            }
            p--;
        }
    }
};

时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！