剑指offer刷题第二题

第二题 替换空格

思路：一种是申请一个新字符串遍历即可，一种是在原字符串上进行替换。当从前往后遍历字符时遇到空格需要后面的字母移动，时间复杂度为O(n2)；而先计算出扩容后的大小从后面利用两个指针，一个指向之前的字符串的尾部，一个指向扩容后的尾部，向前移动第一个指针，判断该位置字母是否是空格来控制后一个指针位置的值。时间复杂度为O(n)。

代码：

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int oldLastIndex = str.length() - 1;
        int newLastIndex = oldLastIndex;
        for(int i = 0;i < str.length();i++)
            if(str.charAt(i) == ' ')
                newLastIndex += 2;
        
        while(str.length() - 1 < newLastIndex) {
            str.append(' ');
        }
        
        
        while(oldLastIndex >= 0) {
            char c = str.charAt(oldLastIndex);
            oldLastIndex--;
            if(c != ' ') {
                str.setCharAt(newLastIndex, c);
                newLastIndex--;
            }
            else {
                str.setCharAt(newLastIndex, '0');
                str.setCharAt(newLastIndex - 1, '2');
                str.setCharAt(newLastIndex - 2, '%');
                newLastIndex -= 3;
            }
        }
        return str.toString();
    }
}