这是悦乐书的第206次更新，第218篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第74题（顺位题号是345）。编写一个函数，它将一个字符串作为输入，并仅反转一个字符串的元音。例如：
输入：“hello”
输出：“holle”
输入：“leetcode”
输出：“leotcede”
注意：元音不包括字母“y”。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
元音字母包含：a e i o u 这五个，利用栈先进后出的特性，把字符串转为字符数组，利用迭代，遇到五个元音字母（包含大小写）时，进行入栈操作。然后再利用迭代，当栈不为空时，且遇到五个元音字母时，将该字符数组当前字符替换为出栈的字符。
此解法的时间复杂度是O(n)，空间复杂度是O(n)。
public String reverseVowels(String s) {
if (s == null || s.trim().length() <= 1) {
return s ;
}
Stack<Character> stack = new Stack<Character>();
char[] arr = s.toCharArray();
for (int i=0; i<arr.length; i++) {
char ch = arr[i];
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
|| ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U') {
stack.push(ch);
}
}
for (int i=0; i<arr.length; i++) {
char ch = arr[i];
if (!stack.isEmpty() && (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
|| ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U')) {
arr[i] = stack.pop();
}
}
return new String(arr);
}
03 第二种解法
思路和第一种解法一样，只不过是将栈换成了字符串。
public String reverseVowels2(String s) {
if (s == null || s.trim().length() <= 1) {
return s ;
}
char[] arr = s.toCharArray();
String ss = "";
int count = -1;
for (int i=0; i<arr.length; i++) {
char ch = arr[i];
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
|| ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U') {
ss += ch;
count += 1;
}
}
for (int i=0; i<arr.length; i++) {
char ch = arr[i];
if (count >= 0 && (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
|| ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U')) {
arr[i] = ss.charAt(count);
count--;
}
}
return new String(arr);
}
04 第三种解法
利用双指针，将字符串转为字符数组，一个从0开始，一个从尾部开始，如果头尾指针所对应的字符均为元音，就交换两者的位置，如果头部或者尾部指针对应的字符不是元音，那么头部指针向尾部方向移动或者尾部指针向头部方向移动。
此解法的时间复杂度是O(log(n))，空间复杂度是O(n)。
public String reverseVowels3(String s) {
if (s == null || s.trim().length() <= 1) {
return s ;
}
char[] arr = s.toCharArray();
int i = 0, j = s.length()-1;
while (i < j) {
if (isVowels(arr[i]) && isVowels(arr[j])) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
if (!isVowels(arr[i])) {
i++;
}
if (!isVowels(arr[j])) {
j--;
}
}
return new String(arr);
}
public static boolean isVowels(char ch) {
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ) {
return true;
}
if (ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U') {
return true;
}
return false;
}
05 第四种解法
使用StringBuilder，借助循环，从字符串的头部开始判断，如果当前字符不是元音，直接append，如果是元音，则从字符串尾部开始找元音进行替换。
public String reverseVowels4(String s) {
if (s == null || s.trim().length() <= 1) {
return s ;
}
StringBuilder sb = new StringBuilder();
String str = "AEIOUaeiou";
int j = s.length()-1;
for (int i=0; i<s.length(); i++) {
if (str.indexOf(s.charAt(i)) != -1) {
while (j >= 0 && str.indexOf(s.charAt(j)) == -1) {
j--;
}
sb.append(s.charAt(j));
j--;
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
06 小结
算法专题目前已连续日更超过两个月，算法题文章74+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
