LeetCode算法题-Reverse Vowels of a String(Java实现-四种解法)

时间:2023-07-09 16:25:02

这是悦乐书的第206次更新,第218篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第74题(顺位题号是345)。编写一个函数,它将一个字符串作为输入,并仅反转一个字符串的元音。例如:

输入:“hello”

输出:“holle”

输入:“leetcode”

输出:“leotcede”

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

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

元音字母包含:a e i o u 这五个,利用栈先进后出的特性,把字符串转为字符数组,利用迭代,遇到五个元音字母(包含大小写)时,进行入栈操作。然后再利用迭代,当栈不为空时,且遇到五个元音字母时,将该字符数组当前字符替换为出栈的字符。

此解法的时间复杂度是O(n),空间复杂度是O(n)。

public String reverseVowels(String s) {
if (s == null || s.trim().length() <= 1) {
return s ;
}
Stack<Character> stack = new Stack<Character>();
char[] arr = s.toCharArray();
for (int i=0; i<arr.length; i++) {
char ch = arr[i];
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
|| ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U') {
stack.push(ch);
}
}
for (int i=0; i<arr.length; i++) {
char ch = arr[i];
if (!stack.isEmpty() && (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
|| ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U')) {
arr[i] = stack.pop();
}
}
return new String(arr);
}

03 第二种解法

思路和第一种解法一样,只不过是将栈换成了字符串。

public String reverseVowels2(String s) {
if (s == null || s.trim().length() <= 1) {
return s ;
}
char[] arr = s.toCharArray();
String ss = "";
int count = -1;
for (int i=0; i<arr.length; i++) {
char ch = arr[i];
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
|| ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U') {
ss += ch;
count += 1;
}
}
for (int i=0; i<arr.length; i++) {
char ch = arr[i];
if (count >= 0 && (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
|| ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U')) {
arr[i] = ss.charAt(count);
count--;
}
}
return new String(arr);
}

04 第三种解法

利用双指针,将字符串转为字符数组,一个从0开始,一个从尾部开始,如果头尾指针所对应的字符均为元音,就交换两者的位置,如果头部或者尾部指针对应的字符不是元音,那么头部指针向尾部方向移动或者尾部指针向头部方向移动。

此解法的时间复杂度是O(log(n)),空间复杂度是O(n)。

public String reverseVowels3(String s) {
if (s == null || s.trim().length() <= 1) {
return s ;
}
char[] arr = s.toCharArray();
int i = 0, j = s.length()-1;
while (i < j) {
if (isVowels(arr[i]) && isVowels(arr[j])) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
if (!isVowels(arr[i])) {
i++;
}
if (!isVowels(arr[j])) {
j--;
}
}
return new String(arr);
} public static boolean isVowels(char ch) {
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ) {
return true;
}
if (ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U') {
return true;
}
return false;
}

05 第四种解法

使用StringBuilder,借助循环,从字符串的头部开始判断,如果当前字符不是元音,直接append,如果是元音,则从字符串尾部开始找元音进行替换。

public String reverseVowels4(String s) {
if (s == null || s.trim().length() <= 1) {
return s ;
}
StringBuilder sb = new StringBuilder();
String str = "AEIOUaeiou";
int j = s.length()-1;
for (int i=0; i<s.length(); i++) {
if (str.indexOf(s.charAt(i)) != -1) {
while (j >= 0 && str.indexOf(s.charAt(j)) == -1) {
j--;
}
sb.append(s.charAt(j));
j--;
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}

06 小结

算法专题目前已连续日更超过两个月,算法题文章74+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!