[数据结构与算法]Map与Set高频面试算法题（只出现一次的数字，复制带随机指针的链表，宝石与石头，旧键盘，前k个高频单词）(Java实现)

目录

LeetCode 136? 只出现一次的数字

LeetCode 138 复制带随机指针的链表?

leetCode 771 宝石与石头

旧键盘打字

LeetCode 692 前K个高频单词

LeetCode 136? 只出现一次的数字

题目链接：只出现一次的数字

题目：

给一个非空整数数组，，只有一个元素出现了一次，剩余的元素都出现了两次，，请找出那个只出现一次的数字

示例：

方法一：

我们知道0异或任何数等于任何数，两个相等的数字异或为0，所以我们可以采用位运算，将所有的数依次异或，得到的数就是只出现一次的元素

代码展示：?

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0;i < nums.length;i++){
            ret = ret ^ nums[i];
        }
        return ret;
    }
}

方法二：

我们可以往HashSet中依次存放元素，因为set中不能存放重复元素，所以当某个元素插入失败时，说明set中已有该元素，将该元素从set中删掉，最后set中剩余的元素就是只出现一次的元素

代码展示：?

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for(int i = 0;i < nums.length;i++){
            if(!s.add(nums[i])){
                s.remove(nums[i]);
            }
        }
        Object[] array = s.toArray();
        return (int)array[0]; 
    }
}

LeetCode 138 复制带随机指针的链表?

题目链接：复制带随机指针的链表?

题目：

??

示例：

方法：

可以使用HashMap，K为原链表的结点，V为与K相对应的新节点，先复制完结点，再链接新结点，新结点要链接next和random指针域 ，链接方法如下：

• next链接的方法：map.get(cur).next = map.get(cur.next)，cur为遍历原链表的结点
• random链接的方法：map.get(cur).random = map.get(cur.random)

代码展示：?

class Solution {
    public Node copyRandomList(Node head) {
        Node cur = head;
        Map<Node,Node> m = new HashMap<>();
        while(cur != null){
            Node newNode = new Node(cur.val);
            m.put(cur,newNode);
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            m.get(cur).next = m.get(cur.next);
            m.get(cur).random = m.get(cur.random);
            cur = cur.next;
        }
        return m.get(head);
    }
}

leetCode 771 宝石与石头

题目链接：宝石与石头?

题目：

给你一个字符串 jewels?代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头，stones?中每个字符代表了一种你拥有的石头的类型，求你拥有的石头中有多少是宝石。

示例：

方法：

我们可以借助HashSet，将宝石依次插入到set中，再依次遍历每个石头，判断宝石中是否包含该石头，如果包含则计数+1?，返回最终计数

代码展示：?

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

旧键盘打字

题目链接：旧键盘

题目：

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。?

输入描述：

输出描述：

注意：输出要求英文字母大写，所以我们在输入时直接将字符串准换成大写，求转换大写后的坏键

方法：

我们可以将实际输出的字符保存到HashSet中，然后依次将应该输出的字符往set中插入，如果插入成功说明该键是坏键，直接输出该键

代码展示：?

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine().toUpperCase();//应该输出的
        String s2 = sc.nextLine().toUpperCase();//实际输出的
        Set<Character> s = new HashSet<>();
        for(int i = 0;i < s2.length();i++){
            s.add(s2.charAt(i));
        }
        for(int i = 0;i < s1.length();i++){
            if(s.add(s1.charAt(i))){
                System.out.print(s1.charAt(i));
            }
        }
        System.out.println();
    }
}

LeetCode 692 前K个高频单词

题目链接：前K个高频单词?

题目：

给一个单词列表words和一个整数k，返回前k个出现次数最多的单词

注意：返回的单词应该按单词的出现频率依次排序，如果不同的单词具有相同的出现频率，则按照字典序排序

示例：

方法：使用Top-k思想解决

1. 先使用HashMap统计各个单词以及对应的出现次数
2. map中存放的是K-V键值对，将前k个键值对插入到优先级队列中，键值对对应的类型为Map.Entry<K,V>
3. 往优先级队列中插入键值对时，需要创建比较器类，使Map.Entry<K,V>类型可以比较大小
4. 插入前k个后，后面插入的N-K个键值对需要和堆顶元素比较，如果比堆顶元素大则删除堆顶元素，插入该键值对
5. 插入完所有的键值对后，使用依次从优先级队列中删除后往List中添加
6. 因为堆顶元素是最小的，而题目要求是按照频率高往低输出，故List中保存的顺序是与题目要求相反的
7. 将List中的内容逆置后返回

分析如何创建比较器类及重写compare的方法 ：

我们往优先级队列中插入的是键值对，类型为Map.Entry<String,Integer>，我们要的前K个高频，从次数上看，是小堆的方式，堆顶元素出现的次数是最低的，后面的N-k个元素与堆顶元素比较时，次数大于堆顶元素时替换堆顶元素，从字典序上看，是大堆的方式，当元素出现的次数相同时，堆顶元素应为字典序大的

代码展示：

//比较器类
class KVCmp implements Comparator<Map.Entry<String,Integer>>{
    public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
        if(o1.getValue() > o2.getValue()){
            return 1;
        }
        if(o1.getValue()==o2.getValue() && o2.getKey().compareTo(o1.getKey())>0){
            return 1;
        }
        if(o1.getValue()==o2.getValue() && o2.getKey().compareTo(o1.getKey())==0){
            return 0;
        }
        return -1;
    }
}
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> m = new HashMap<>();
        //统计次数
        for(int i = 0;i < words.length;i++){
            m.put(words[i],m.getOrDefault(words[i],0)+1);
        }
        //new比较器类
        KVCmp cmp = new KVCmp();
        //创建优先级队列，传入比较器
        PriorityQueue<Map.Entry<String,Integer>> p = new PriorityQueue<>(cmp);
        Set<Map.Entry<String,Integer>> s = m.entrySet();
        int i = 0;
        //将键值对插入到优先级队列中
        for(Map.Entry<String,Integer> kv : s){
            //前k个直接插入
            if(i < k){
                p.offer(kv);
                i++;
            }else {
                //后面的经过比较后再插入
                if(cmp.compare(kv,p.peek()) > 0){
                    p.poll();
                    p.offer(kv);
                }
            }
        }
        List<String> ret = new ArrayList<>();
        //往list中插入键值对的V，也就是单词
        for(i = 0;i < k;i++){
            ret.add(p.poll().getKey());
        }
        Collections.reverse(ret);//逆置
        return ret;
    }
}