牛客网（java实现）

问题描述：

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

问题分析：

时间复杂度为 O(n2) 的算法思想 从头到尾，扫描字符串中的每个字符，遇到空格，先将剩余的字符（未遍历到的字符串）整体向后移动2个位置，然后，在空格和其后的2个字符的替换为"%20"。2. 时间复杂度为 O(n) 的算法思想 先遍历整个字符串，计算字符串中空格的总数，从而可以计算出替换后的字符串长度（根据替换规则，每次替换空格时，都会使字符串的长度增加2）。然后，使用两个指针或索引，从后往前遍历，即初始化指针或索引分别指向替换前和替换后字符串的末尾，循环递减，如遇到空格，则替换为 "%20"，从而减少字符串移动的次数，降低时间复杂度。

算法实现：

略

参考代码：

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int len = str.length();
        if (len <= 0)
            return "";
            //return null;
        String s = new String(str.toString());
        String ss = new String(s.replaceAll(" ", "%20"));
        return ss.toString();
    }
}