寒光博客

[LeetCode]345.反转字符串中的元音字母
题目 编写一个函数,以字符串作为输入,反转该字符串中的元音字母。 示例 1: 输入: "hello" 输出: "h...
扫描右侧二维码阅读全文
21
2020/06

[LeetCode]345.反转字符串中的元音字母

题目

编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

示例 1:

输入: "hello"
输出: "holle"

示例 2:

输入: "leetcode"
输出: "leotcede"

说明:
元音字母不包含字母"y"。

链接:https://leetcode-cn.com/problems/reverse-vowels-of-a-string

解析

使用双指针,一个指针从头向尾遍历,一个指针从尾到头遍历,当两个指针都遍历到元音字符时,交换这两个元音字符。

为了快速判断一个字符是不是元音字符,我们将全部元音字符添加到集合 HashSet 中,从而以 O(1) 的时间复杂度进行该操作。

  • 时间复杂度为 O(N):只需要遍历所有元素一次
  • 空间复杂度 O(1):只需要使用两个额外变量

代码

  //快速判断 一个字符是否是元音字符 加入到 Hash集合中判断 O(1)
    public static Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

    public String reverseVowels(String s) {
        int i = 0, j = s.length() - 1;
        char[] result = new char[s.length()];
        char a, b;
        while (i <= j) {//不一定是对称
            a = s.charAt(i);
            b = s.charAt(j);
            if (!set.contains(a)) {//判断是否在集合中
                result[i++] = a;//不在 保存当前
            } else if (!set.contains(b)) { //i在 看j在不在
                result[j--] = b;
            } else {//俩都在  索引换位置记录
                result[i++] = b;
                result[j--] = a;
            }
        }
        return new String(result);
    }

反思

用HashSet来判断常量 ,同时用asList来初始化数据 很好用
设立一个result数组来记录答案 符合就交换 不符合就原样放入
i j 一定是要重叠的判断

本文作者:Author:     文章标题:[LeetCode]345.反转字符串中的元音字母
本文地址:http://dxoca.cn/Algorithm/359.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:June 21st, 2020 at 03:35 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment