题目描述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;
    }
}