Map和Set相关OJ题

1.宝石与石头771. 宝石与石头 - 力扣（LeetCode）

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

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

基本思路：可以采用字符串的形式，也可以采用集合的方式，这里我们以集合的方式。我们首先把jewels放在一个集合中，定义一个count来计数，然后遍历stones，判断stones中是否有jewels中的元素，如果有，count++，直到stones遍历完，返回count。

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

注：这里不能用HashMap，因为HashMap的KEY值必须能比较，而这里的类型是字符。 

2.坏键盘打字

输入：输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、 以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。
输出描述：按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。

基本思路：根据题目要求，其中的英文字母只输出大写，所以我们可以先把所有的字符串全都转换成大写，然后把实际输出的字符串放在一个集合中，遍历输入的字符串，如果该字符串中包含集合中未有的元素，则输出，还要注意题目中要求每个坏键只输出一次。

import java.util.Scanner;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            badBank(str1, str2);
        }
 
    }
    public  static void badBank(String str1, String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < str2.length(); i++) {
            char ch = str2.charAt(i);
            set.add(ch);
        }
        HashSet<Character> list = new HashSet<>();
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if (!set.contains(ch) && !list.contains(ch)) {
                list.add(ch);
                System.out.print(ch);
            }
        }
    }

    
}

 3.前K个高频单词692. 前K个高频单词 - 力扣（LeetCode）

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

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

基本思路：这个问题可以联想到之前介绍的top-k的问题，把前k个元素建立小跟堆，将剩下的元素与小跟堆的堆顶元素比较，直到所有的元素都遍历完，前k个元素就是我们所要求的。

public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        //1. 统计每个单词出现的次数
        for(String word : words) {
            if(map.get(word) == null) {
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }

        //2. 建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public 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());
            }
        });
        //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) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else if(top.getValue().compareTo(entry.getValue()) == 0) {
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        ArrayList<String> list = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp = minHeap.poll();
            list.add(tmp.getKey());
        }
        //e-2 f-3 a-5
        Collections.reverse(list);
        return list;
    }

注:

• 在建立小跟堆时，我们时比较元素的value的大小来排序的，但当他们的value值相同时，我们较他们key值的大小，按照字母表的顺序进行比较。
• 在输出时，小跟堆是按照最小的最先出，比如此时输出e-5,f-3,a-5,但题目要求按频率由高到底输出，所以我们可以申请一个集合，把他们放进去，最后进行翻转即可。
• 而且在输出时，遇到频率相同的，要按照字母表的顺序输出。

4.只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

基本思路：给定一个集合set，遍历这个数组nums,如果set中包含nums中的元素，则删除，否则，则放到集合中，遍历玩数组后;再遍历该数组，看set中是否包含nums中的元素，有则返回该值。

public int singleNumber(int[] nums) {
      HashSet<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;
}

5.复制带随机指针的链表138. 随机链表的复制 - 力扣（LeetCode）

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

这里我们是深拷贝，不是简单的把值赋值就可以了。

基本思路：

• 如果头结点head为空节点，直接返回null；
• 初始化哈希表，节点cur指向头结点；
• 复制链表，利用集合map先把每个节点的储存起来，每一个map就是一个entry,entry包含key和value,我们让key储存老节点，value储存新节点，把这个映射关系放到map中，让cur遍历至原链表下一节点；
• 构建新链表的引用指向，修改新节点的next和random，直到链表遍历结束，返回head。

 public Node copyRandomList(Node head) {
if(head==null) return null;
        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;
//构建新链表的next和random指向
        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);
    }