0%

刷算法(4)-反转字符串中的元音字母

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

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

解题思路

这个题里暗含几个陷阱:

  1. 什么是元音字母?以下几个都是,注意含大写:

    1
    char[] dicts = new char[]{'a', 'o', 'e', 'i', 'u', 'A', 'O', 'E', 'I', 'U'};
  2. Java里String是不可变的,修改的话需要转成char[] xx = s.toCharArray

  3. 如果输入字符串长度为1直接返回即可,不需要计算;

  4. 正确抽象模型(快排思想):示例里只替换了一组元音字母,但是隐含的意思是要替换所有的元音。用两个索引分别标记最左边和最右边,从左边找到第一个元音停下来,然后从右边再找到第一个元音停下来,如果两个索引没有越界则交换。之后左边索引+1右边索引-1即可,直到左右索引越界结束循环。

解法1

这是我自己写的答案,有点拉杂:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package com.company;

import java.util.ArrayList;
import java.util.List;

public class Solution {
public String reverseVowels(String s) {
char[] dicts = new char[] {'a', 'o', 'e', 'i', 'u', 'A', 'O', 'E', 'I', 'U'};
List<Character> yuanyinList = new ArrayList<>();
for (char temp : dicts){
yuanyinList.add(temp);
}
char[] newDicts = s.toCharArray();
if (s.length() == 1){
return s;
}
int i = 0, j = s.length() -1;
while ( i<j ){
char left = newDicts[i];
char right = newDicts[j];

// 两边都是元音字母
if (yuanyinList.contains(left) && yuanyinList.contains(right)){
if (left != right) {
newDicts[i] = right;
newDicts[j] = left;
}
i++;
j--;
}
if (!yuanyinList.contains(left)){
i++;
continue;
}
if (!yuanyinList.contains(right)){
j--;
}
}
return String.valueOf(newDicts);
}
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package com.company;

import java.util.ArrayList;
import java.util.List;

public class Solution {
public String reverseVowels(String s) {
char[] dicts = new char[]{'a', 'o', 'e', 'i', 'u', 'A', 'O', 'E', 'I', 'U'};
List<Character> yuanyinList = new ArrayList<>();
for (char temp : dicts) {
yuanyinList.add(temp);
}
char[] newDicts = s.toCharArray();
if (s.length() == 1) {
return s;
}
int i = 0, j = s.length() - 1;
while (i < j) {
// 找到最左边的字母然后停下来
while (i < j && !yuanyinList.contains(newDicts[i])) {
++i;
}
// 找到最右边的字母然后停下来
while (i < j && !yuanyinList.contains(newDicts[j])) {
--j;
}
// 两边都是元音字母
if (i < j) {
char temp = newDicts[i];
newDicts[i] = newDicts[j];
newDicts[j] = temp;
i++;
j--;
}
}
return String.valueOf(newDicts);
}
}

优化

考虑到大小写元音问题,可以通过Character.toLowerCase('A')char都转小写再比较。

1
2
3
4
private boolean isVowel(char c) {
char lowerC = Character.toLowerCase(c);
return lowerC == 'a' || lowerC == 'e' || lowerC == 'i' || lowerC == 'o' || lowerC == 'u';
}