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

题解: 逆向遍历

  1. 分析：由于函数返回为void，说明此题不能另外开辟数组，需要in-place操作。我们知道字符串的遍历无非是从左到右和从右到左两种。
    1）如果从左到右，会发现如果遇到空格，会将原来的字符覆盖。于是，此方法不行。
    2）那么就考虑从右向左，遇到空格，就填充“20%“，否则将原字符移动应该呆的位置。
  2. 具体过程如图所示：
  • length为原字符串最后一个字符的位置，new_lngth为结果字符串的最后一个位置
  1. 代码：
    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];
         }
     }
 }
};
  2. 复杂度
    时间复杂度：O(length)
    空间复杂度：O(1)