前言

Set和Map這兩種數據結構,在解決一些題上，效率很高。跟大家簡單分享一些題以及如何使用Set和Map去解決這些題目。

題目鏈接

136. 只出現一次的數字 - 力扣（LeetCode）

138. 隨機鏈表的復制 - 力扣（LeetCode）

舊鍵盤 (20)__牛客網

692. 前K個高頻單詞 - 力扣（LeetCode）

解題思路

一些題目的代碼實現?

import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class Test1 {//獲取單詞出現了多少次public static void main(String[] args) {String[] words={"Maybe","Maybe","hello","happy","sadness"};Map<String,Integer> map=countword(words);//使用map.entrySet()遍歷mapSet<Map.Entry<String,Integer>> entrySet=map.entrySet();//entrySet里面放的是Map.Entry<k,v>類型的for(Map.Entry<String,Integer> s:entrySet){System.out.println("key "+s.getKey()+" "+"val "+s.getValue());}}private static Map<String,Integer> countword(String[] words) {Map<String,Integer> map=new HashMap<>();//統計每個單詞出現了多少次for(String s:words){if(map.get(s)==null){//則沒有出現過一次map.put(s,1);}else{int val=map.get(s);map.put(s,val+1);}}return map;}
}

import java.util.HashSet;
import java.util.Locale;
import java.util.Scanner;
import java.util.Set;public class Test2 {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的區別while (in.hasNextLine()) {//這個是應該被輸入的String a = in.nextLine();//這個是實際上被輸入的String b = in.nextLine();a=a.toUpperCase();b=b.toUpperCase();Set<Character> set=new HashSet<>();for(int i=0;i<b.length();i++){char ch=b.charAt(i);set.add(ch);}Set<Character> set1=new HashSet<>();for(int i=0;i<a.length();i++){char ch=a.charAt(i);if(!set.contains(ch)&&!set1.contains(ch)){set1.add(ch);System.out.print(ch);}}}}
}

import java.util.*;public class Test3 {public List<String> topKFrequent(String[] words, int k) {Map<String,Integer> map=new HashMap<>();//統計單詞出現的次數for(String word:words){if(map.get(word)==null){map.put(word,1);}else{int val=map.get(word);map.put(word,val+1);}}//成為Top-k問題，創建小根堆PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {if(o1.getValue().compareTo(o2.getValue())==0){return o2.getKey().compareTo(o1.getKey());}return o1.getValue().compareTo(o2.getValue());}});//遍歷mapfor(Map.Entry<String,Integer> entry:map.entrySet()){if(minHeap.size()<k){minHeap.offer(entry);}else{Map.Entry<String,Integer> top=minHeap.peek();if(top.getValue().compareTo(entry.getValue())<0){minHeap.poll();minHeap.offer(entry);}if(top.getValue().compareTo(entry.getValue())==0){if(top.getKey().compareTo(entry.getKey())>0){minHeap.poll();minHeap.offer(entry);}}}}//此時的大根堆里面一定是前k個高頻單詞List<String> list=new ArrayList<>();for(int i=0;i<k;i++){Map.Entry<String,Integer> tmp=minHeap.poll();list.add(tmp.getKey());}//Collections專門用來處理集合Collections.reverse(list);return list;}public static void main(String[] args) {}
}

結語?

再見~

?

?

?

?