LeetCode刷题-反转字符串中的元音字母
前言说明
算法学习，日常刷题记录。
题目连接
题目内容
给你一个字符串s，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。
示例1:
输入：s = "hello"
输出："holle"
示例2:
输入：s = "leetcode"
输出："leotcede"
提示：
1 <= s.length <= 3 * 10^5
s由可打印的ASCII字符组成
方法1
使用双指针法，从字符串两侧往里遍历字符，如果两边对应出现元音字母，那么反转赋值到字符数组中，否则直接赋值到字符数组中。
但是需要注意左右指针的移动和停止，用两个标识isLeft和isRight来判断是否左右指针位置的字符都是元音字母，当左右指针位置的字符都是元音字母时，才交换两个字符。
因为不清楚是左指针先还是右指针先，所以判断三次，先判断左指针，再判断右指针，再判断一次左指针。
代码如下：
class Solution {
public String reverseVowels(String s) {
// 使用双指针法，从字符串两侧往里遍历字符，如果两边对应出现元音字母，那么反转赋值到字符数组中，否则直接赋值到字符数组中
if (s.length() == 1) {
// 当字符串长度为1时，直接返回字符串
return s;
}
// 定义反转后的字符数组，长度为字符串s的长度
char[] cs = new char[s.length()];
// 定义左侧是否找到元音字母的标识
boolean isLeft = false;
// 定义右侧是否找到元音字母的标识
boolean isRight = false;
// 定义左指针，初始为0
int left = 0;
// 定义右指针，初始为字符串s的最后下标
int right = s.length() - 1;
// 循环，当左指针大于等于右指针时，结束循环
while (left < right) {
if (isVowels(s.charAt(left))) {
// 若左指针下标的字符是元音字母，标识标为true
isLeft = true;
if (isRight || left >= right) {
// 若右指针的标识也是true或者左指针等于右指针，那么右指针下标的字符赋值到字符数组的左指针下标的位置，左指针下标的字符赋值到字符数组的右指针下标的位置
cs[left] = s.charAt(right);
cs[right] = s.charAt(left);
}
} else {
// 若左指针下标的字符不是元音字母，标识标为false，字符直接赋值给字符数组，左指针加1
isLeft = false;
cs[left] = s.charAt(left);
++left;
}
if (isVowels(s.charAt(right))) {
// 若右指针下标的字符是元音字母，标识标为true
isRight = true;
if (isLeft || left >= right) {
// 若左指针的标识也是true或者左指针等于右指针，左指针下标的字符赋值到字符数组的右指针下标的位置，那么右指针下标的字符赋值到字符数组的左指针下标的位置
cs[right] = s.charAt(left);
cs[left] = s.charAt(right);
}
} else {
// 若右指针下标的字符不是元音字母，标识标为false，字符直接赋值给字符数组，右指针减1
isRight = false;
cs[right] = s.charAt(right);
--right;
}
// 重复判断一次左指针下标的字符是否是元音字母，因为可能是右指针下标的字符为元音字母，如果右指针下标的字符是元音字母，但是左指针下标的字符是否是元音字母的判断在前面，程序无法往回运行，所以这里再判断一次左指针下标的字符是否是元音字母
if (isVowels(s.charAt(left))) {
// 若左指针下标的字符是元音字母，标识标为true
isLeft = true;
if (isRight || left >= right) {
// 若右指针的标识也是true或者左指针等于右指针，那么右指针下标的字符赋值到字符数组的左指针下标的位置，左指针下标的字符赋值到字符数组的右指针下标的位置
cs[left] = s.charAt(right);
cs[right] = s.charAt(left);
}
}
if (isLeft && isRight) {
// 若左指针和右指针的标识都为true，那么左指针和右指针的标识重置为false，同时左指针加1，右指针减1
isLeft = false;
isRight = false;
++left;
--right;
}
if (left == right) {
// 若左指针等于右指针，那么当前字符数组的下标进行一次直接赋值，因为如果当前下标的字母是元音字母而且只剩下一个时，如果不进行一次直接赋值，循环就结束了，这个下标的字符就会变成空值
cs[left] = s.charAt(left);
}
}
// 最后把字符数组转为字符串，返回结果
return new String(cs);
}
// 判断当前字符是否为元音字母
private boolean isVowels(char c) {
return 'a' == c || 'e' == c || 'i' == c || 'o' == c || 'u' == c || 'A' == c || 'E' == c || 'I' == c || 'O' == c || 'U' == c;
}
}
提交代码运行，运行结果如下：
运行结果
执行用时3ms，时间击败81.95%的用户，内存消耗38.3MB，空间击败87.70%的用户。
方法2
但是方法1繁杂混乱，理解困难，可能也看不懂，不推荐，方法2进行优化调整，变得逻辑清晰不繁杂，推荐。
方法2同样是使用双指针法，从字符数组两侧往里遍历字符，直到出现元音字母或者超出字符数组边界，若在左指针小于右指针时出现两个元音字母，那么交换字符数组中的两个元音字母。
第1步
先把字符串s转为字符数组arr。
定义左指针left，从字符数组arr左侧开始，初始为0。
定义右指针right，从字符数组arr右侧开始，初始为字符数组arr最后的下标。
第2步
双指针往里遍历字符数组arr，循环直到左指针left大于等于右指针right，结束循环。
第3步
循环时：
再进行内部循环，若左指针left还没超出字符数组边界并且指针位置的字符不是元音字母，那么左指针left移动加1，直到左指针left超出字符数组边界或指针位置的字符是元音字母，结束循环。
再进行内部循环，若右指针right还没超出字符数组边界并且指针位置的字符不是元音字母，那么右指针right移动减1，直到右指针right超出字符数组边界或指针位置的字符是元音字母，结束循环。
经过上面的两次内部循环，要么出现左指针left大于等于右指针right，要么左右指针位置的字符都是元音字母。
若这时左指针left小于右指针right，那么这时左右指针位置的字符都是元音字母，交换这两个元音字母，左指针left加1，右指针right减1。
第4步
循环结束后，把字符数组arr转为字符串，返回结果。
代码如下：
class Solution {
public String reverseVowels(String s) {
// 双指针法，从字符数组两侧往里遍历字符，直到出现元音字母或者超出字符数组边界，若在左指针小于右指针时出现两个元音字母，那么交换字符数组中的两个元音字母
// 先把字符串转为字符数组
char[] arr = s.toCharArray();
// 定义左指针，从字符数组左侧开始，初始为0
int left = 0;
// 定义右指针，从字符数组右侧开始，初始为字符数组最后的下标
int right = s.length() - 1;
// 双指针往里遍历字符数组，循环直到左指针大于等于右指针
while (left < right) {
while (left < s.length() && isNotVowel(arr[left])) {
// 若左指针还没超出字符数组边界并且指针位置的字符不是元音字母，那么左指针移动加1，直到左指针超出字符数组边界或指针位置的字符是元音字母，结束循环
++left;
}
while (right > 0 && isNotVowel(arr[right])) {
// 若右指针还没超出字符数组边界并且指针位置的字符不是元音字母，那么右指针移动减1，直到右指针超出字符数组边界或指针位置的字符是元音字母，结束循环
--right;
}
// 经过上面的两次while循环，要么出现左指针大于等于右指针，要么左右指针位置的字符都是元音字母
if (left < right) {
// 若左指针小于右指针，那么这时左右指针位置的字符都是元音字母，交换这两个元音字母
swap(arr, left, right);
// 左指针加1
++left;
// 右指针减1
--right;
}
}
// 最后把字符数组转为字符串，返回结果
return new String(arr);
}
// 判断当前字符是否不是元音字母
private boolean isNotVowel(char c) {
return 'a' != c && 'e' != c && 'i' != c && 'o' != c && 'u' != c && 'A' != c && 'E' != c && 'I' != c && 'O' != c && 'U' != c;
}
// 交换字符数组中的两个字符
private void swap(char[] arr, int left, int right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
提交代码运行，运行结果如下：
运行结果
执行用时2ms，时间击败99.77%的用户，内存消耗38.4MB，空间击败76.83%的用户。
原文链接
原文链接：反转字符串中的元音字母
