【LeetCode】345. Reverse Vowels of a String 解题报告（Java & Python & C++）

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目描述

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:

Input: "hello"

Output: "holle"

Example 2:

Input: "leetcode"

Output: "leotcede"

Note:

The vowels does not include the letter “y”.

题目大意

把一个字符串中所有的元音字母倒序，其他位置不变。

解题方法

使用栈

理解题意很重要啊！

这个题的意思是把收尾向中间走的时候遇到的所有元音字符换位置。也就是说 “abecui”–>“ibucea”;

把某个东西进行翻转，很容易想到栈。所以把元音字符进栈，再次遍历的时候遇到元音字符就出栈即可。

class Solution(object):

    def reverseVowels(self, s):

        """

        :type s: str

        :rtype: str

        """

        vstack = []

        for c in s:

            if c in "aeiouAEIOU":

                vstack.append(c)

        res = []

        for c in s:

            if c in "aeiouAEIOU":

                res.append(vstack.pop())

            else:

                res.append(c)

        return "".join(res)

双指针

也就是用双指针的方法。一个从头查找，一个从尾查找。同时判断是否为元音字符，如果两个指针都是落在了元音字符上的时候，交换。别忘了交换位置之后前往下一个地点。

python代码如下：

class Solution(object):

    def reverseVowels(self, s):

        """

        :type s: str

        :rtype: str

        """

        N = len(s)

        res = list(s)

        left, right = 0, N - 1

        while left < right:

            while right >= 0 and res[right] not in "aeiouAEIOU":

                right -= 1

            while left < right and res[left] not in "aeiouAEIOU":

                left += 1

            if left < right:

                res[left], res[right] = res[right], res[left]

            left += 1

            right -= 1

        return "".join(res)

Java代码如下：

public class Solution {

    public String reverseVowels(String s) {

        ArrayList<Character> list=new ArrayList();

        list.add('a');

        list.add('e');

        list.add('i');

        list.add('o');

        list.add('u');

        list.add('A');

        list.add('E');

        list.add('I');

        list.add('O');

        list.add('U');

        char[] array=s.toCharArray();

        int head=0;

        int tail=array.length-1;

        while(head<tail){

            if(!list.contains(array[head])){

                head++;

                continue;

            }

            if(!list.contains(array[tail])){

                tail--;

                continue;

            }

            char temp=array[head];

            array[head]=array[tail];

            array[tail]=temp;

            head++;

            tail--;

        }

        return new String(array);

    }

}

AC:11ms

C++代码如下：

class Solution {

public:

    string reverseVowels(string s) {

        const int N = s.size();

        int left = 0, right = N - 1;

        while (left < right) {

            while (left < N && !isVowel(s[left])) left ++;

            while (right >= 0 && !isVowel(s[right])) right --;

            if (left < right)

                swap(s[left], s[right]);

            left ++;

            right --;

        }

        return s;

    }

private:

    bool isVowel(char x) {

        string t = "aeiouAEIOU";

        return t.find(x) != string::npos;

    }

};

日期

2016/5/1 20:52:19
2018 年 11 月 21 日 —— 又是一个美好的开始
2018 年 12 月 4 日 —— 周二啦！

巴特西

【LeetCode】345. Reverse Vowels of a String 解题报告（Java & Python & C++）

目录

题目描述

题目大意

解题方法

使用栈

双指针

日期

最新文章

热门文章