題目描述1(344)
- 給定一個(gè)字符串拴魄，寫(xiě)一個(gè)函數(shù)將其逆序輸出
題目描述2（345）
- 給定一個(gè)字符串，寫(xiě)一個(gè)函數(shù)實(shí)現(xiàn)字符串中的原因字母逆序崖飘，其余的不變
解題思路（逆序）
- 逆序就是一個(gè)遍歷的過(guò)程，然后不停的交換位置這是最直接暴力也應(yīng)該是最優(yōu)解法了（不包含采用語(yǔ)言本身的逆序輸出函數(shù)）
- JAVA操作需要將字符串先轉(zhuǎn)換為數(shù)組杈女，為了加快交換速度朱浴，我們將數(shù)組從兩邊同時(shí)開(kāi)始遍歷交換吊圾，當(dāng)low指針>high指針時(shí)完成遍歷
代碼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（元音逆序）
- 首先逆序思路大體和上述差不多，但是我們需要注意此時(shí)需要的是元音逆序翰蠢，那么low指針和high指針的指向必須是元音字母项乒，這就可以采用類似于快排的思想，在low指針一直用while查找到一個(gè)元音字母梁沧，再用high指針用while查找到一個(gè)元音字母將其交換順序檀何，然后進(jìn)行下一輪
- 一直到low > high為止，在這個(gè)過(guò)程中需要注意數(shù)組越界的問(wèn)題廷支，和第一題相比多了一點(diǎn)條件
- 時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(n)
源代碼2
class Solution {
/*
1. 首先將字符串轉(zhuǎn)換為字符數(shù)組频鉴，便于交換操作
2. 根據(jù)提示，需要找出元音字母進(jìn)行交換恋拍，我們只需要找出對(duì)應(yīng)的下標(biāo)即可垛孔，可根據(jù)快排的思想，我們從兩邊分別開(kāi)始查找施敢。
左邊查找到一個(gè)元音字母時(shí)周荐，然后再用while循環(huán)從右邊查找元音字母，此時(shí)將兩個(gè)元音字母交換就可完成逆序僵娃，依次進(jìn)行直到
大小兩個(gè)指針相遇結(jié)束概作。
3. 需要隨時(shí)注意下標(biāo)越界的情況，否則會(huì)報(bào)錯(cuò)
4. 時(shí)間復(fù)雜度O(n),空間復(fù)雜度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;
}
}
