1 只出现一次的数字
题目描述： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
解题思路：我们可以采用HashMap去做，需要遍历两遍数组，第一遍的时候统计数组中的值与出现的次数成一个对应的键值对，第二遍的时候获取次数，如果次数为1，则就是我们要寻找的那个值
代码如下：
class Solution { public int singleNumber(int[] nums) { HashMap<Integer,Integer> map = new HashMap<>(); //第一遍遍历数组，统计数组值与出现的次数 for(int i =0;i<nums.length;i++){ if(!map.containsKey(nums[i])){ map.put(nums[i],1); }else{ map.put(nums[i],map.get(nums[i])+1); } } //第二遍去遍历数组，获取数组中值所对应的次数 for(int i =0;i<nums.length;i++){ if(map.get(nums[i])==1){ return nums[i]; } } //如果没有次数为1的，就返回一个负数 return -1; } }
2 复制带随机指针的链表
题目描述：对于一个单链表，不仅仅有着next域，还有一个random域，要将这个链表进行深拷贝一份结构相同的单链表出来
解题思路：我们可以尝试画出复制完的两个单链表，通过第一次遍历链表，同时创建新的节点，去利用HashMap存储旧链表与新链表之间的节点关系，第二次遍历链表，将新链表的每个节点串起来即可
关系：
代码如下：
class Solution { public Node copyRandomList(Node head) { HashMap<Node,Node> map = new HashMap<>(); Node cur = head; //第一次遍历，获取两个链表节点对应的关系 while(cur!=null){ Node node = new Node(cur.val); map.put(cur,node); cur=cur.next; } //第二次遍历，将新的链表的next与rondom域完善 cur=head; while(cur!=null){ map.get(cur).next=map.get(cur.next); map.get(cur).random=map.get(cur.random); cur=cur.next; } //返回头结点对应的值，就是新链表的头结点 return map.get(head); } }
3 宝石与石头
题目描述：给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。
例如：
输入：jewels = “aA”, stones = “aAAbbbb”
输出：3
解题思路：先遍历jewels，利用MapSet将其存储起来，在去遍历stones，如果包含了stones里面的元素，说明就是宝石，计数器就要加1，否则就是石头
代码如下：
class Solution { public int numJewelsInStones(String jewels, String stones) { HashSet<Character> set = new HashSet<>(); //遍历jewels for(int i = 0;i<jewels.length();i++){ set.add(jewels.charAt(i)); } //遍历stones int count=0;//计数器 for(int j = 0;j<stones.length();j++){ if(set.contains(stones.charAt(j))){ count++; } } return count; } }
4 坏键盘打字
预期输入： 7_This_is_a_test
实际输入： _hs_s_a_es
所以坏掉的键有：7TI
解题思路：我们可以先把实际输出的放到（先将字符串转成大写然后在变成一个数组）第一个set集合里面，第二次创建出一个新的set集合broken，再去遍历预期输入的字符串，如果第一个set里面不包含并且broken中也不包含，那么就可以打印（必须要先打印，因为set里面的元素不是按照顺序放的，所以我们必须检测到一个就要马上打印），然后在添加到broken中。
代码如下：
import java.util.*; public class Main { //strExce:7_This_is_a_test strActual:_hs_s_a_es public static void func(String strExce,String strActual) { HashSet<Character> set = new HashSet<>(); //将stractual变成大写并且转换成数组来遍历 for(char actual : strActual.toUpperCase().toCharArray()){ set.add(actual); } //broken集合为了将坏掉的键去重，防止重复打印 HashSet<Character> broken = new HashSet<>(); //将strexce变成大写，并且转换成为数组来遍历 for(char str:strExce.toUpperCase().toCharArray()){ if(!set.contains(str)&&!broken.contains(str)){ System.out.print(str); broken.add(str); } } } public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(scan.hasNextLine()){//由于带有空格，所以必须是hasNextLine String str1 = scan.nextLine(); String str2 = scan.nextLine(); func(str1,str2); } } }
5 前K个高频单词
题目描述：给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
解题思路：我们先根据word与k之间，利用键值对，将其对应关系存储在map里面，然后在结合之前所学的堆，我们需要建立一个大小为K的小根堆，然后在遍历Map，利用集合逆置输出即可，只是在比较的过程中，需要涉及到对象的比较，需要我们指定比较方式
代码如下：
class Solution { public List<String> topKFrequent(String[] words, int k) { //统计单词出现的次数 HashMap<String,Integer> map = new HashMap<>(); for (String s:words) { map.put(s,map.getOrDefault(s,0)+1); } //建立一个小根堆 PriorityQueue<Map.Entry<String,Integer>> minheap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() { @Override public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { //如果存在放入的元素小于K，那么遇到value值一样，应该按照key比较 if(o1.getValue().compareTo(o2.getValue())==0){ return o2.getKey().compareTo(o1.getKey()); } return o1.getValue()-o2.getValue(); } }); //遍历map,把堆建好 for (Map.Entry<String,Integer> entry:map.entrySet()) { //如果堆大小还没有K大，那么直接放入 if (minheap.size()<k){ minheap.offer(entry); }else{ //如果频率相同，就要比较字符串 Map.Entry<String,Integer> top = minheap.peek(); if(entry.getValue().compareTo(top.getValue())==0){ if(top.getKey().compareTo(entry.getKey())>0){ minheap.poll(); minheap.offer(entry); } }else{//按频率比较 if(top.getValue().compareTo(entry.getValue())<0){ minheap.poll(); minheap.offer(entry); } } } } //线性表存入String List<String> list = new ArrayList<>(); for (int i = 0; i < k; i++) { String str = minheap.poll().getKey(); list.add(str); } //反转逆置，返回线性表 Collections.reverse(list); return list; }
6 总结
对于以上五题，难度最大的应该就是第五题了，比较难想到，其实就是对于考验我们对于对象之间的比较能否掌握，以上五题整体难度一般，但能够体现出set与map应用的灵活，以及做题的优点！！
