6

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

 3 years ago
source link: https://sexywp.com/345-invert-vowles.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

345. 反转字符串中的元音字母 – Becomin' Charles跳至内容

Becomin' Charles

Mac | Linux | 团队管理 | 架构

  • Charles : Sorry, 我测试了一下，有个语法特性在 PHP 7.0 下不支持，更新到 2.0.7 可以修复。...

  • 大盛 : 你好，我启用后报错，怎么解决啊，我的WP版本是5.6.1，PHP版本是7.0

    Parse er...

  • Wang : 现在大部分大学老师在照本宣科，学生在应付考试，计算机专业在大学毕业前没打开过GitHub大有人在。自...
  • Charles : 我上面插图里，有我家里门禁室内机的电路板。电路板正面右上角，有一个开关，那个就是开锁按钮，可以看到就...
  • 求教 : 您好，最近在研究类似方案，刚刚好搜到你的文章。虽然没有看到介绍，但是我看文章的情况，貌似您的门禁室内...

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

这道题目，我直接想到的就是双指针算法了，一个指针从头往后找，一个指针从后往头找，然后找到元音后停下来，然后，交换，继续循环。

关键是循环终止的位置，应该是头尾两个指针碰到的时候。我就写出了这样的代码：

class Solution:
def reverseVowels(self, s: str) -> str:
ss = [ x for x in s ]
l = len(ss)
j = l - 1
vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
while i < j:
while i < l and ss[i] not in vowels:
while j > 0 and ss[j] not in vowels:
if i <= j:
ss[i], ss[j] = ss[j], ss[i]
return "".join(ss)
class Solution:
    def reverseVowels(self, s: str) -> str:
        ss = [ x for x in s ]
        i = 0
        l = len(ss)
        j = l - 1
        vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
        while i < j:
            while i < l and ss[i] not in vowels:
                i += 1
            while j > 0 and ss[j] not in vowels:
                j -= 1

            if i <= j:
                ss[i], ss[j] = ss[j], ss[i]
                i += 1
                j -= 1
        return "".join(ss)

我先把字符串转换成了 list，因为我发现字符串里的字符不能更改，记得 Python 的 string 是 immutable 的。所以换了。

这个算法的复杂度理论上是 O(n) 的，不过在尾指针那里，往头部找元音的时候，如果最坏情况，可能会是重复搜索，可以增加一个条件，就是 j >= i 避免无畏地搜索。

发布于 2021/03/092021/03/14作者 Charles分类 算　　法标签 algorithm、two pointers

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

评论

名称 *

电子邮件 *

站点

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK