替换空格

1. 题目难度：二星
2. 考察点：字符串
3. 题解

题解: 逆向遍历

1. 分析：由于函数返回为void，说明此题不能另外开辟数组，需要in-place操作。我们知道字符串的遍历无非是从左到右和从右到左两种。
   1）如果从左到右，会发现如果遇到空格，会将原来的字符覆盖。于是，此方法不行。
   2）那么就考虑从右向左，遇到空格，就填充“20%“，否则将原字符移动应该呆的位置。
2. 具体过程如图所示：

• length为原字符串最后一个字符的位置，new_lngth为结果字符串的最后一个位置

3. 代码：

   class Solution {
   public:
    void replaceSpace(char *str,int length) {
        if (str == nullptr || length <= 0) return; // 养成良好习惯，判空操作
        int cnt = 0;  // 空格的个数
        for (int i=0; i != length; ++i) {
            if (str[i] == ' ') ++cnt;
        }
        if (!cnt) return; // 没有空格，直接返回
        int new_length = length+cnt*2;
        for (int i=length; i >= 0; --i) {
            if (str[i] == ' ') {
                str[new_length--] = '0';
                str[new_length--] = '2';
                str[new_length--] = '%';
            }
            else {
                str[new_length--] = str[i];
            }
        }
    }
   };

4. 复杂度
   时间复杂度：O(length)
   空间复杂度：O(1)