题目描述1(344)
题目描述2（345）
- 给定一个字符串，写一个函数实现字符串中的原因字母逆序，其余的不变
解题思路（逆序）
- 逆序就是一个遍历的过程，然后不停的交换位置这是最直接暴力也应该是最优解法了（不包含采用语言本身的逆序输出函数）
- JAVA操作需要将字符串先转换为数组，为了加快交换速度，我们将数组从两边同时开始遍历交换，当low指针>high指针时完成遍历
代码1
class Solution {
public String reverseString(String s) {
char[] array = new char[s.length()];
int low = 0, high = s.length()-1;
while (low <= high) {
array[low] = s.charAt(high);
array[high] = s.charAt(low);
high--;
low++;
}
return new String(array);
}
}
解题思路2（元音逆序）
- 首先逆序思路大体和上述差不多，但是我们需要注意此时需要的是元音逆序，那么low指针和high指针的指向必须是元音字母，这就可以采用类似于快排的思想，在low指针一直用while查找到一个元音字母，再用high指针用while查找到一个元音字母将其交换顺序，然后进行下一轮
- 一直到low > high为止，在这个过程中需要注意数组越界的问题，和第一题相比多了一点条件
- 时间复杂度O(n),空间复杂度O(n)
源代码2
class Solution {
/*
1. 首先将字符串转换为字符数组，便于交换操作
2. 根据提示，需要找出元音字母进行交换，我们只需要找出对应的下标即可，可根据快排的思想，我们从两边分别开始查找。
左边查找到一个元音字母时，然后再用while循环从右边查找元音字母，此时将两个元音字母交换就可完成逆序，依次进行直到
大小两个指针相遇结束。
3. 需要随时注意下标越界的情况，否则会报错
4. 时间复杂度O(n),空间复杂度O(n)
*/
public String reverseVowels(String s) {
if (s.length() == 0) return s;
char[] array = s.toCharArray();
int low = 0, high = s.length()-1;
while (low <= high) {
while (low <= s.length() - 1 && !isVowels(array[low])) low++;
while (high >= 0 && !isVowels(array[high])) high--;
if (low <= high) exch(array, low, high);
low++;
high--;
}
return new String(array);
}
private void exch(char[] array, int i, int j) {
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private boolean isVowels(char c) {
if (c == 'a' || c == 'e' ||
c == 'i' || c == 'o' ||
c == 'A' || c == 'E' ||
c == 'I' || c == 'O' ||
c == 'u' || c == 'U') {
return true;
} else return false;
}
}
