《剑指offer》5.替换空格

题目：请实现一个函数，把字符串中的每个空格替换成‘%20’，
例如，输入“we are happy.”，则输出“we%20are%20happy.”。

在python中，字符串是不可变类型。这意味着使用str.replace会生成一个新的字符串，即需要额外的O(n)大小的空间。

    def replace(self, *args, **kwargs): # real signature unknown
        """
        Return a copy with all occurrences of substring old replaced by new.
        
          count
            Maximum number of occurrences to replace.
            -1 (the default value) means replace all occurrences.
        
        If the optional argument count is given, only the first count occurrences are
        replaced.
        """
        pass

python的源码中明确指出会返回一个替换后的副本。
并且python的字符串是无法通过str[n]的形式进行修改的。
如果把字符串定义为str类型，是无法在O(1)的空间内完成的。
所以按照这道题的出题意思，得把这个字符串当成一个列表来处理。
然而我找了半天好像没法给列表初始化大小，最多用占位符来处理。
python中的列表在内存中也是连续的一段空间，只是它会自动的给你分配大小。
所以如果直接把空格替换为'%20'的话，会多出两个字符，也意味着空格后面的所有字符都需要右移2位。
这样的时间复杂度就是O(n²)级别的。
本题要考察的思路是直接把字符放到最终的位置，而不是每一次替换都让后面的字符右移。
即先扫描一遍数组，记录下空格的数量，然后直接计算每个字符在最终的数组中的位置，再从后往前直接把字符放到最终的位置上。这样只需要循环两遍数组就可以了，时间复杂度是O(n)级别的。
python代码实现如下：

def replace_blank(string):
    c = 0
    los = len(string)
    for i in string:
        if i == ' ':
            c += 1
    string += [None] * c * 2  # 扩充list的长度，不然后面会越界
    for i in range(los - 1, -1, -1):  # 倒序遍历数组
        if string[i] == ' ':
            string[i + c * 2 - 2: i + c * 2 + 1] = '%20'  # 替换空格为%20
            c -= 1
        else:
            string[i + c * 2] = string[i]
    return ''.join(string)


if __name__ == '__main__':
    string = list('we are happy.')
    print(replace_blank(string))