java数据结构_Map和Set_面试题

本文讲解几道使用Map和Set解决的面试题：

1. 只出现一次的数字

2. 复制带有随机指针的链表

3. 宝石与石头

4. 坏键盘打字

5. 前K个高频单词

1. 只出现一次的数字

连接：136. 只出现一次的数字 - 力扣（LeetCode）

这道题目较为简单，关键定义出Set集合，然后合理使用contains和remove方法即可。

代码如下：

java">    public int singleNumber(int[] nums) {Set<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {if (set.contains(nums[i])) {set.remove(nums[i]);} else {set.add(nums[i]);}}for(int i = 0; i < nums.length; i++) {if(set.contains(nums[i])) {return nums[i];}}return -1;

上面的代码用了两个for循环遍历了nums，也可以在第二次中使用迭代器遍历返回

2. 复制带有随机指针的链表

连接：138. 随机链表的复制 - 力扣（LeetCode）

如图有如下链表，该链表是有三个成员变量的，有val，next，还有一个random域，random随机指向链表中的一个结点的地址，没有规律，可以指向自己，也可以为空。

需要对这个链表进行一个深拷贝：其val值和结构都与之前相同（之前的random指向自己，新的拷贝的链表的random仍指向自己...）但是地址是不相同的

解决：

可以先定义一个集合，遍历链表，将旧结点都存在一个集合当中

然后再对旧的链表再遍历一次，利用get方法得到刚刚保存在集合中的结点的val

代码如下：

java">  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;}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);}

注意，这道题中不能使用TreeMap，因为TreeMap在进行put时候，是需要进行比较的，该题中是引用类型Node，也未实现Comparable接口，会编译报错。

3. 宝石与石头

连接：771. 宝石与石头 - 力扣（LeetCode）

如下图，定义一个集合，将宝石中的字母均放入集合中，然后遍历stones，如果stones中有jewels中的字母，则定义一个计数器++，最后返回计数器的大小

代码如下：

java">    public int numJewelsInStones(String jewels, String stones) {HashSet<Character> set = new HashSet<>();for(int i = 0; i < jewels.length(); i++) {set.add(jewels.charAt(i));}int count = 0;for(int i = 0; i < stones.length(); i++) {if(set.contains(stones.charAt(i))) {count++;}}return count;}

也可以使用toCharArray方法：

4. 坏键盘打字

链接：旧键盘 (20)__牛客网

代码如下：

str1为完整输入的字母，str2为有重复的字母，第二个for循环检查str1中是否有重复的字母，有如果不重复就打印。

但是，题目要求是如果有字母已经打印过，就不需要再打印了，但我们的第二个循环是会打印的，可以小小修改：

再定义一个set2，在打印一次之后，就将该字母add进入set2中，在if条件中，加上!set2.contains(ch)即可

5. 前K个高频单词

链接：692. 前K个高频单词 - 力扣（LeetCode）

首先实现一个方法来统计单词出现的个数

代码如下：

因为要返回前K个高频单词，所以需要建立一个小根堆来进行排序，PriorityQueue的默认方式就是小根堆，但我们此时要插入的是一个Map.Entry，需要重写比较器，来告诉优先级对立，使用Map.Entry中的key / value进行比较：

代码如下：

此时使用的是一个匿名内部类，找到o1的value和o2的value进行比较

然后再遍历map，调整优先级队列，注意在调整时候出现的情况，如果单词出现次数一样，就让字母顺序小的进来

最终要返回一个List，但是小根堆出列，顺序是由小到大的，需要reverse一下

即完整代码如下：

java">  public static List<String> topKFrequent(String[] words, int k) {//1.统计每个单词出现的次数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);}}//建立小根堆，指定比较的方式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) {return o1.getValue() - o2.getValue();}});//3.遍历map 调整优先级队列for (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) {//让字母顺序小的进来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);}}}}//4.最终要返回一个List<String>List<String> ret = new ArrayList<>();for (int i = 0; i < k; i++) {Map.Entry<String, Integer> top = minHeap.poll();ret.add(top.getKey());}//但题目要求最终的输出结果还是要按照单词出现频率次数，由高到低排列//但我们的优先级队列是 小根堆，出队的话poll会先将小的出队//不能直接返回ret//反转一下Collections.reverse(ret);return ret;}

信心满满的放入力扣测试中，提交结果却还是报错：

我勒个大骚杠，无语啦！！！

但还是没办法，再研究，为什么会解答错误，预期结果是先输出 i ，再输出 love，我们的输出为先输出了love，后输出了 i，不对呀，我们明明记得在调整优先级队列的时候，考虑到了两个单词出现次数情况相同，然后让字母顺序小的单词入列，为什么此处出现了问题呢？

蓦然回首，bug却在灯火阑珊处。我们在遍历map向优先级队列填入元素的时候，在minHeap.size() < k的时候，即建立前k个元素的小根堆的时候，频率相同的情况，并没有处理，我们只是在后面放满元素的时候，才处理了频率相同的情况

举例，如果取前三个单词，即我们要先建立一个大小为3的小根堆，如果不在乎单词频率的情况下，随意放入：

如何修改？

因为我们小根堆建立之后的比较方式是通过这个匿名内部类的，可以在这里进行一些操作

修改如下：

最终代码如下：

java">class Solution {public static List<String> topKFrequent(String[] words, int k) {//1.统计每个单词出现的次数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);}}//建立小根堆，指定比较的方式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() - o2.getValue();}});//3.遍历map 调整优先级队列for (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) {//让字母顺序小的进来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);}}}}//4.最终要返回一个List<String>List<String> ret = new ArrayList<>();for (int i = 0; i < k; i++) {Map.Entry<String, Integer> top = minHeap.poll();ret.add(top.getKey());}//但题目要求最终的输出结果还是要按照单词出现频率次数，由高到低排列//但我们的优先级队列是 小根堆，出队的话poll会先将小的出队//不能直接返回ret//反转一下Collections.reverse(ret);return ret;}
}

完！！！