剑指offer 替换空格

题目描述

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

思路：恩。人生苦短，我用python。

python实现：

1 # -*- coding:utf-8 -*-
2 class Solution:
3     # s 源字符串
4     def replaceSpace(self, s):
5         # write code here
6         return "%20".join(s.split(" "))

C++实现：

如果从头开始扫描，那么每遇到一个空格，都要将后面的字符往后移两位，最终时间复杂度O(n²),因此可以从串尾开始扫描。

 1 class Solution {
 2 public:
 3     void replaceSpace(char *str,int length) {
 4         //sOldLength记录origin string的长度，sNum记录空格个数。
 5         int sOldLength = 0, sNum = 0, i = 0;
 6         while (str[i] != '') {
 7             sOldLength++;
 8             if (str[i] == ' ') {
 9                 sNum++;
10             }
11             i++;
12         }
13         //sNewLength表示新串的长度 - 1
14         int sNewLength = sOldLength + 2 * sNum;
15         if (sNewLength >= length)
16             return;
17         while (sOldLength >= 0 && sNewLength > sOldLength) {
18             if (str[sOldLength] == ' ') {
19                 str[sNewLength--] = '0';
20                 str[sNewLength--] = '2';
21                 str[sNewLength--] = '%';
22             } else {
23                 str[sNewLength--] = str[sOldLength];
24             }
25             sOldLength--;
26         }
27     }

合并两个排序的数组（或者字符串)，如果从前往后复制每个数字需要重复移动数字（字符）多次，我们可以考虑从后往前复制。