首页 > 考试 > 其他 > 正文
LeetCode笔记:345. Reverse Vowels of a String
2016-10-02       个评论    来源:Minecraft  
收藏    我要投稿

问题:

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

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

大意:

写一个函数,输入一个字符串然后翻转里面的元音字母。

例1:
给出 s = “hello”,返回”holle”。

例2:
给出 s = “leetcode”,返回”leotcede”。

注意:
元音不包括字母“y”。

思路:

首先想到的一个思路是遍历字符串中每个字母,遇到元音字母就记录下字母和所在的位置。遍历完后,对着记录下来的元音字母,将字符串中的元音按照反序替换一遍就好了,这种做法也做出来了,但是结果非常耗时,花了200多ms。
后来想到了第二种方法,在字符串的头和尾都放一个指针进行遍历,两端向中间去遍历,当两端都遇到元音字母后,就对换。直到两个指针碰头为止。这个方法就快多了,同时优化一下检查是否是元音字母的方法,只需要几ms就搞定了。
需要注意的是题目中并没有说字符串是纯大写或者小写,所以大小写都要考虑,这个容易忽略。

代码1(Java):

public class Solution {
    public String reverseVowels(String s) {
        int[] vowelIndex = new int[s.length()];
        char[] vowelChar = new char[s.length()];
        int index = 0;// 标记上面两个数组记录的位置
        // 记录元音字母及出现的位置
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a' || s.charAt(i) == 'e' || s.charAt(i) == 'i' || s.charAt(i) == 'o' || s.charAt(i) == 'u' || s.charAt(i) == 'A' || s.charAt(i) == 'E' || s.charAt(i) == 'I' || s.charAt(i) == 'O' || s.charAt(i) == 'U') {
                vowelChar[index] = s.charAt(i);
                vowelIndex[index] = i;
                index++;
            }
        }
        // 替换元音字母位置
        if (index == 0) return s;
        else {
            StringBuffer buffer = new StringBuffer(s);
            for (int i = 0; i < index; i++) {
                buffer.replace(vowelIndex[i], vowelIndex[i]+1, String.valueOf(vowelChar[index-i-1]));
            }
            return buffer.toString();
        }
    }
}

代码2(Java):

public class Solution {
    static final String vowels = "aeiouAEIOU";
    public String reverseVowels(String s) {
        int first = 0, last = s.length() - 1;
        char[] array = s.toCharArray();
        while(first < last){
            // 正向找元音
            while(first < last && vowels.indexOf(array[first]) == -1){
                first++;
            }
            // 逆向找元音
            while(first < last && vowels.indexOf(array[last]) == -1){
                last--;
            }
            // 对换
            char temp = array[first];
            array[first] = array[last];
            array[last] = temp;
            first++;
            last--;
        }
        return new String(array);
    }
}

 

点击复制链接 与好友分享!回本站首页
上一篇:Codeforces Round #373 (Div. 2) C. Efim and Strange Grade 贪心、实数字符串"a.b"处理
下一篇:(LeetCode)Rectangle Area --- 求图形覆盖的面积
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站