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

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

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]; 
    }
}

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

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;
    }
}

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();
    }
}

//比较器类
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;
    }
    }