腾讯 2017 暑假实习生编程题（二）：小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。 你能帮帮小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();
    }
}