1. 知識拓展
1.1 HashSet和HashMap
1.1.1 HashSet
HashSet是實作Set< E >接口的一個實體類，資料以哈希表的形式存放，特點是不允許有重複元素且無序存放元素。既然是實作了Set< E >接口，那Set< E >接口的特性是什麼呢？
- Set接口繼承了Collection接口，故包含Collection接口的所有方法。
- 無序（存儲和取出順序不一緻，也有可能一緻），但元素唯一，不允許有重複。
- 實作類有HashSet，底層資料是哈希表；和TreeSet，底層資料是紅黑二叉樹。 如何初始化HashSet的值呢？
LeetCode#345 反轉字元串中的元音字母|Java HashSet和HashMap|雙指針|String字元串和字元數組
public static final String[] SET_VALUES = new String[] { "a", "b" };
public static final Set<String> MY_SET = new HashSet<>(Arrays.asList(SET_VALUES));
private final static HashSet<Character> vowels = new HashSet<>(
Arrays.asList('a', 'e', 'o', 'i', 'u', 'A', 'E', 'O', 'I', 'U'));
HashSet<String> h = new HashSet<String>() {{
add("a");
add("b");
}};
HashSet<String> h = new HashSet<String>();
h.add("a");
h.add("b");
1.1.2 HashMap
HashMap是實作Map<K,V>接口的一個實體類，它對鍵值做了一對一的映射關系，裡面鍵值不能重複。
HashMap由數組+連結清單組成的，數組是HashMap的主體，連結清單則是主要為了解決哈希沖突而存在的，如果定位到的數組位置不含連結清單（目前entry的next指向null）,那麼查找，添加等操作很快，僅需一次尋址即可；如果定位到的數組包含連結清單，對于添加操作，其時間複雜度為O(n)，首先周遊連結清單，存在即覆寫，否則新增；對于查找操作來講，仍需周遊連結清單，然後通過key對象的equals方法逐一比對查找。是以，性能考慮，HashMap中的連結清單出現越少，性能才會越好。
HashMap的總體結構
1.1.3 HashSet和HashMap的差別
1.2 String字元串和字元數組
1.2.1 String字元串和字元數組的互相轉換
字元數組轉換為字元串
char[] array = new char[] {'a','b','c','d','e','f','g'};
String str = new String(array);
char[] array = new char[] {'a','b','c','d','e','f','g'};
String str2 = String.valueOf(array);
字元串轉換為字元數組
使用toCharArray()方法。
String msg = "i am a good boy!";
char[] dest = msg.toCharArray();
1.2.2 取String字元串中的某個元素
使用charAt()方法，s是String類型，p，q是int型的。
char s1 = s.charAt(p);
char s2 = s.charAt(q);
2.題目描述
編寫一個函數，以字元串作為輸入，反轉該字元串中的元音字母。
示例 1:
輸入: “hello”
輸出: “holle”
示例 2:
輸入: “leetcode”
輸出: “leotcede”
說明:
元音字母不包含字母"y"。
3.分析
使用雙指針，一個指針從前往後周遊，一個指針從後往前周遊，遇到元音字母就交換位置。為快速判斷一個字元是不是元音字元，将全部元音字母（包括大小寫）添加到集合 HashSet 中，進而以 O(1) 的時間複雜度進行該操作。
時間複雜度：周遊所有的元素一次，O(n)
空間複雜度：隻使用兩個指針，O(1)
4.代碼
public class ReverseVowels {
//把所有的元音字母，包括大小寫存到HashSet中
private final static HashSet<Character> vowels = new HashSet<>(
Arrays.asList('a', 'e', 'o', 'i', 'u', 'A', 'E', 'O', 'I', 'U'));
public String reverseVowels(String s) {
//字元串為空，直接傳回null
if(s == null)
return null;
char[] res = new char[s.length()]; //結果字元數組
int p = 0, q = s.length()-1; //雙指針
while(p <= q) {
//取出指針對應的字元
char s1 = s.charAt(p);
char s2 = s.charAt(q);
if(!vowels.contains(s1)) { //s1不是元音字母
res[p++] = s1;
//p++; 第一次送出後修改
}
else if(!vowels.contains(s2)) { //s2不是元音字母
res[q--] = s2;
//q--; 第一次送出後修改
}
else { //兩指針對應元素至少有一個元音字母
res[p++] = s2;
res[q--] = s1;
}
}
return new String(res);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
ReverseVowels rv = new ReverseVowels();
System.out.println(rv.reverseVowels(str));
}
}
5.運作結果
送出修改記錄：
-把兩個語句合成一個之後，運作更快了
res[p] = s1;
p++;
改為
參考網址
https://blog.csdn.net/zfliu96/article/details/83476493#21HashSet_111
https://blog.csdn.net/weixin_44551646/article/details/94898951
https://blog.csdn.net/cong____cong/article/details/79727938
https://includestdio.com/1375.html
https://blog.csdn.net/woshimaxiao1/article/details/83661464
https://blog.csdn.net/weixin_42153410/article/details/95494014