题目
由《剑指 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();
}
}
