LeetCode刷题-反转字符串中的元音字母

前言说明

算法学习,日常刷题记录。

题目连接

反转字符串中的元音字母

题目内容

给你一个字符串s,仅反转字符串中的所有元音字母,并返回结果字符串。

元音字母包括'a'、'e'、'i'、'o'、'u',且可能以大小写两种形式出现。

示例1:

输入:s = "hello"

输出:"holle"

示例2:

输入:s = "leetcode"

输出:"leotcede"

提示:

1 <= s.length <= 3 * 10^5
s由可打印的ASCII字符组成

方法1

使用双指针法,从字符串两侧往里遍历字符,如果两边对应出现元音字母,那么反转赋值到字符数组中,否则直接赋值到字符数组中。

但是需要注意左右指针的移动和停止,用两个标识isLeft和isRight来判断是否左右指针位置的字符都是元音字母,当左右指针位置的字符都是元音字母时,才交换两个字符。

因为不清楚是左指针先还是右指针先,所以判断三次,先判断左指针,再判断右指针,再判断一次左指针。

代码如下:

class Solution {
    public String reverseVowels(String s) {
        // 使用双指针法,从字符串两侧往里遍历字符,如果两边对应出现元音字母,那么反转赋值到字符数组中,否则直接赋值到字符数组中

        if (s.length() == 1) {
            // 当字符串长度为1时,直接返回字符串
            return s;
        }

        // 定义反转后的字符数组,长度为字符串s的长度
        char[] cs = new char[s.length()];

        // 定义左侧是否找到元音字母的标识
        boolean isLeft = false;
        // 定义右侧是否找到元音字母的标识
        boolean isRight = false;

        // 定义左指针,初始为0
        int left = 0;
        // 定义右指针,初始为字符串s的最后下标
        int right = s.length() - 1;

        // 循环,当左指针大于等于右指针时,结束循环
        while (left < right) {
            if (isVowels(s.charAt(left))) {
                // 若左指针下标的字符是元音字母,标识标为true
                isLeft = true;
                if (isRight || left >= right) {
                    // 若右指针的标识也是true或者左指针等于右指针,那么右指针下标的字符赋值到字符数组的左指针下标的位置,左指针下标的字符赋值到字符数组的右指针下标的位置
                    cs[left] = s.charAt(right);
                    cs[right] = s.charAt(left);
                }
            } else {
                // 若左指针下标的字符不是元音字母,标识标为false,字符直接赋值给字符数组,左指针加1
                isLeft = false;
                cs[left] = s.charAt(left);
                ++left;
            }

            if (isVowels(s.charAt(right))) {
                // 若右指针下标的字符是元音字母,标识标为true
                isRight = true;
                if (isLeft || left >= right) {
                    // 若左指针的标识也是true或者左指针等于右指针,左指针下标的字符赋值到字符数组的右指针下标的位置,那么右指针下标的字符赋值到字符数组的左指针下标的位置
                    cs[right] = s.charAt(left);
                    cs[left] = s.charAt(right);
                }
            } else {
                // 若右指针下标的字符不是元音字母,标识标为false,字符直接赋值给字符数组,右指针减1
                isRight = false;
                cs[right] = s.charAt(right);
                --right;
            }

            // 重复判断一次左指针下标的字符是否是元音字母,因为可能是右指针下标的字符为元音字母,如果右指针下标的字符是元音字母,但是左指针下标的字符是否是元音字母的判断在前面,程序无法往回运行,所以这里再判断一次左指针下标的字符是否是元音字母
            if (isVowels(s.charAt(left))) {
                // 若左指针下标的字符是元音字母,标识标为true
                isLeft = true;
                if (isRight || left >= right) {
                    // 若右指针的标识也是true或者左指针等于右指针,那么右指针下标的字符赋值到字符数组的左指针下标的位置,左指针下标的字符赋值到字符数组的右指针下标的位置
                    cs[left] = s.charAt(right);
                    cs[right] = s.charAt(left);
                }
            } 

            if (isLeft && isRight) {
                // 若左指针和右指针的标识都为true,那么左指针和右指针的标识重置为false,同时左指针加1,右指针减1
                isLeft = false;
                isRight = false;
                ++left;
                --right;
            }

            if (left == right) {
                // 若左指针等于右指针,那么当前字符数组的下标进行一次直接赋值,因为如果当前下标的字母是元音字母而且只剩下一个时,如果不进行一次直接赋值,循环就结束了,这个下标的字符就会变成空值
                cs[left] = s.charAt(left);
            }
        }

        // 最后把字符数组转为字符串,返回结果
        return new String(cs);
    }

    // 判断当前字符是否为元音字母
    private boolean isVowels(char c) {
        return 'a' == c || 'e' == c || 'i' == c || 'o' == c || 'u' == c || 'A' == c || 'E' == c || 'I' == c || 'O' == c || 'U' == c;
    }
}

提交代码运行,运行结果如下:

运行结果

执行用时3ms,时间击败81.95%的用户,内存消耗38.3MB,空间击败87.70%的用户。

方法2

但是方法1繁杂混乱,理解困难,可能也看不懂,不推荐,方法2进行优化调整,变得逻辑清晰不繁杂,推荐。

方法2同样是使用双指针法,从字符数组两侧往里遍历字符,直到出现元音字母或者超出字符数组边界,若在左指针小于右指针时出现两个元音字母,那么交换字符数组中的两个元音字母。

第1步

先把字符串s转为字符数组arr。

定义左指针left,从字符数组arr左侧开始,初始为0。

定义右指针right,从字符数组arr右侧开始,初始为字符数组arr最后的下标。

第2步

双指针往里遍历字符数组arr,循环直到左指针left大于等于右指针right,结束循环。

第3步

循环时:

再进行内部循环,若左指针left还没超出字符数组边界并且指针位置的字符不是元音字母,那么左指针left移动加1,直到左指针left超出字符数组边界或指针位置的字符是元音字母,结束循环。

再进行内部循环,若右指针right还没超出字符数组边界并且指针位置的字符不是元音字母,那么右指针right移动减1,直到右指针right超出字符数组边界或指针位置的字符是元音字母,结束循环。

经过上面的两次内部循环,要么出现左指针left大于等于右指针right,要么左右指针位置的字符都是元音字母。

若这时左指针left小于右指针right,那么这时左右指针位置的字符都是元音字母,交换这两个元音字母,左指针left加1,右指针right减1。

第4步

循环结束后,把字符数组arr转为字符串,返回结果。

代码如下:

class Solution {
    public String reverseVowels(String s) {
        // 双指针法,从字符数组两侧往里遍历字符,直到出现元音字母或者超出字符数组边界,若在左指针小于右指针时出现两个元音字母,那么交换字符数组中的两个元音字母

        // 先把字符串转为字符数组
        char[] arr = s.toCharArray();

        // 定义左指针,从字符数组左侧开始,初始为0
        int left = 0;
        // 定义右指针,从字符数组右侧开始,初始为字符数组最后的下标
        int right = s.length() - 1;

        // 双指针往里遍历字符数组,循环直到左指针大于等于右指针
        while (left < right) {
            while (left < s.length() && isNotVowel(arr[left])) {
                // 若左指针还没超出字符数组边界并且指针位置的字符不是元音字母,那么左指针移动加1,直到左指针超出字符数组边界或指针位置的字符是元音字母,结束循环
                ++left;
            }

            while (right > 0 && isNotVowel(arr[right])) {
                // 若右指针还没超出字符数组边界并且指针位置的字符不是元音字母,那么右指针移动减1,直到右指针超出字符数组边界或指针位置的字符是元音字母,结束循环
                --right;
            }

            // 经过上面的两次while循环,要么出现左指针大于等于右指针,要么左右指针位置的字符都是元音字母

            if (left < right) {
                // 若左指针小于右指针,那么这时左右指针位置的字符都是元音字母,交换这两个元音字母
                swap(arr, left, right);
                // 左指针加1
                ++left;
                // 右指针减1
                --right;
            }
        }

        // 最后把字符数组转为字符串,返回结果
        return new String(arr);
    }

    // 判断当前字符是否不是元音字母
    private boolean isNotVowel(char c) {
        return 'a' != c && 'e' != c && 'i' != c && 'o' != c && 'u' != c && 'A' != c && 'E' != c && 'I' != c && 'O' != c && 'U' != c;
    }

    // 交换字符数组中的两个字符
    private void swap(char[] arr, int left, int right) {
        char temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}

提交代码运行,运行结果如下:

运行结果

执行用时2ms,时间击败99.77%的用户,内存消耗38.4MB,空间击败76.83%的用户。

原文链接

原文链接:反转字符串中的元音字母

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,968评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,601评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,220评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,416评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,425评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,144评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,432评论 3 401
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,088评论 0 261
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,586评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,028评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,137评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,783评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,343评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,333评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,559评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,595评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,901评论 2 345

推荐阅读更多精彩内容