题目：给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
示例：
输入："Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"
思路1：双指针方式。
1)申明hIndex=0,eIndex=S.length-1两个指针
2)hIndex从前往后移，eIndex从后往前移动
3)如果S[hIndex]为字母，判断S[eIndex]的值：
3.1)如果S[eIndex]为字母，S[hIndex]和S[eIndex]互换
3.2)如果S[eIndex]为非字母,hIndex不偏移，eIndex--直到S[eIndex]也是字母
注意点：S是常量无法修改，可把他转成char[]。
代码如下：
public String reverseOnlyLetters(String S) {
/**********************双指针方式*************************/
int hIndex = 0, eIndex = S.length() - 1;
char[] arr = S.toCharArray();
while (hIndex < eIndex) {
char h = arr[hIndex];
if (h >= 'A' && h <= 'Z' || (h >= 'a' && h <= 'z')) {// 字母需要反转
while(eIndex>hIndex) {// 需要循环找出前一个字母
char e = arr[eIndex];
if (e >= 'A' && e <= 'Z' || (e >= 'a' && e <= 'z')) {
arr[hIndex]=e;
arr[eIndex]=h;
System.out.println(Arrays.toString(arr));
eIndex--;
break;
}
eIndex--;
}
}
hIndex++;
}
return new String(arr);
}
思路2：使用栈方式。
1)分两次遍历S
2)第一次遍历S，index从0到S.length-1,把字母的字符入stack
3)第二次遍历，index从0到S.length-1,声明StringBuffer用于存储返回结果,如果是字母则增加栈顶,如果是非字母则增加S[i]
public String reverseOnlyLetters(String S) {
/*******************栈出入的方式***********************/
//字母入栈
Stack<Character> stack = new Stack<Character>();
for(int i=0;i<S.length();i++) {
char c = S.charAt(i);
if(c >= 'A' && c <= 'Z' || (c >= 'a' && c <= 'z')) {
stack.push(c);
}
}
//遍历S，遇到字母出栈，遇到非字母使用S[i]，加到buffer后面
StringBuffer buffer = new StringBuffer();
for(int i=0;i<S.length();i++) {
char c = S.charAt(i);
if(c >= 'A' && c <= 'Z' || (c >= 'a' && c <= 'z')) {
buffer.append(stack.pop());
} else {
buffer.append(c);
}
}
return buffer.toString();
}
-------------------------------小白学算法
