題目描述1(344)

• 給定一個(gè)字符串，寫一個(gè)函數(shù)將其逆序輸出

題目描述2（345）

• 給定一個(gè)字符串，寫一個(gè)函數(shù)實(shí)現(xiàn)字符串中的原因字母逆序，其余的不變

解題思路（逆序）

• 逆序就是一個(gè)遍歷的過程，然后不停的交換位置這是最直接暴力也應(yīng)該是最優(yōu)解法了（不包含采用語言本身的逆序輸出函數(shù)）
• JAVA操作需要將字符串先轉(zhuǎn)換為數(shù)組，為了加快交換速度，我們將數(shù)組從兩邊同時(shí)開始遍歷交換，當(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è)過程中需要注意數(shù)組越界的問題，和第一題相比多了一點(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ù)快排的思想，我們從兩邊分別開始查找。
    左邊查找到一個(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;
    }
}