腾讯 2017 暑假实习生编程题（二）：小Q最近遇到了一个难题：

由《剑指 offer》面试题 4：替换空格，想到的技巧。

此处运用了一个小小的技巧：从后往前将大写字符依次插入数组尾部，时间复杂度 O(n) 。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    private static char[] work(String str) {
        int length = str.length();
        int upCount = 0;    // 存储字符串中大写字母的个数
        // 循环查找字符串中大写字母的个数
        for (int index = 0; index < length; index++) {
            char temp = str.charAt(index);
            if (temp >= 'A' && temp <= 'Z') {
                upCount++;
            }
        }
        // 扩大字符数组的空间（原大小 + 大写字母个数）
        for (int index = 0; index < upCount; index++) {
            str += " ";
        }
        char[] chars = str.toCharArray();
        // 从后往前遍历，将遇到大写字母依次（从后往前）填充到末尾的空格
        for (int indexI = length - 1, indexJ = length + upCount - 1; indexI >= 0; indexI--) {
            if (chars[indexI] >= 'A' && chars[indexI] <= 'Z') {
                chars[indexJ--] = chars[indexI];
                chars[indexI] = ' ';
            }
        }
        return chars;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        String inputStr;
        while (in.hasNext()) {
            inputStr = in.next();
            for(char c: work(inputStr)){
                if(c != ' '){
                    out.print(c);
                }
            }
            out.println();
        }
        out.flush();
    }
}