剑指 Offer 05. 替换空格

避免时间O(n^2)的写法，预先计算替换后的数组大小从后往前双指针复制降为O(n)，空间是O(1);

• 注意在 C++ 语言中， string 被设计成「可变」的类型，但是C#里面不行，长度固定，操作会消耗内存开辟新对象，可以用可变的字符序列StringBuilder类(虽然对这道题没什么意义，传进来的是个string)。

• StringBuilder的缓冲区扩容里是控制null，而C+ resize里面是空字符串''，已经实例化，所以可以对C+ resize扩容的部分直接访问，而StringBuilder不可以。

• 用string replace，split函数也可以，二刷注意一下这些库函数的时间复杂度和空间复杂度。

• 本地调试真好用，以后都用本地了，正好熟悉一下输入输出。

//C++
class Solution {
public:
    string replaceSpace(string s) {
        int blankCnt = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                blankCnt++;
            }
        }
        int oldSize = s.size() - 1;
        s.resize(s.size() + blankCnt * 2);
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[oldSize] != ' ') {
                s[i] = s[oldSize];
            } else {
                s[i--] = '0';
                s[i--] = '2';
                s[i] = '%';
            }
            oldSize--;
        }
        return s;
    }
};
//C# StringBuilder
public class Solution
{   
    public static string ReplaceSpace(string s) {
        StringBuilder str = new StringBuilder(s); //// 默认容量为16
        //Capacity是缓冲区的容量
        //Length是实际装的字符串长度
        int blankCnt = 0;
        for (int i = 0; i < str.Length; i++) {
            if (str[i] == ' ') {
                blankCnt++;
            }
        }
        int oldSize = str.Length - 1;
        int newSize = str.Length + 2 * blankCnt - 1;
        //str.EnsureCapacity(10010);
        str.Append(' ', 2 * blankCnt); //只扩容缓冲区不行，没有内容不能用下标访问，不像C+的resize
        for (int i = newSize; i >= 0; i--) {
            if (str[oldSize] != ' ') {
                str[i] = str[oldSize];
            } else {
                str[i--] = '0';
                str[i--] = '2';
                str[i] = '%';
            }
            oldSize--;
        }
        return str.ToString();
    }
}