Map与set小试牛刀

偏执的太偏执、 2023-09-27 12:10 95阅读 0赞

![在这里插入图片描述][1776aeff2bf44631951d10ca8f98f4fa.gif_pic_center]

#### 文章目录 ####

*  一、复制带随机指针的链表
 *  二、宝石与石头
 *  三、旧键盘
 *  四、前K个高频单词

## 一、复制带随机指针的链表 ##

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。  
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。  
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。返回复制链表的头节点。  
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 \[val, random\_index\] 表示：  
val：一个表示 Node.val 的整数。  
random\_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。  
你的代码 只 接受原链表的头节点 head 作为传入参数。  
![在这里插入图片描述][c29f3b08697d4555b1e13deb6379c194.png]  
![在这里插入图片描述][ebb7dafb9c9d4c91985009436963c464.png]  
我们利用HashMap来解决这个问题，key存放原本的链表顺序，value,存放我们构建新的链表。

public Node copyRandomList(Node head) {
        
            Map<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);
        }

## 二、宝石与石头 ##

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。  
字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。  
![在这里插入图片描述][c72f0361d0234211bd22289c7e233923.png]  
**思路分析**  
这题相当于是去重，我们把所有的宝石放到Set集合当中，遍历石头，如果Set存在计数器++。

public int numJewelsInStones(String jewels, String stones) {
        
            Set<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;
        }

## 三、旧键盘 ##

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。  
**输入描述:**  
输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、  
以及下划线“\_”（代表空格）组成。题目保证2个字符串均非空。  
**输出描述:**  
按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。  
![在这里插入图片描述][6322e903b1644bfb91e978340ad38170.png]  
![在这里插入图片描述][57bcb53146224fb0ba97b1b85fca1e9b.png]  
我们的思路是把实际输出的放入到Set中，然后遍历预期的去判断如果Set中没有则是坏的键，所以有一点特殊情况。

import java.util.*;
    public class Main {
        
       public static void main(String[] args) {
        
            Scanner scan = new Scanner(System.in);
            while(scan.hasNextLine())   {
        
                String str1 = scan.nextLine();
                String str2 = scan.nextLine();
                findWrongKey(str1,str2);
            }
        }
        public static void findWrongKey(String str1,String str2) {
        
            Set<Character> set = new HashSet<>();
            for(Character c :str2.toUpperCase().toCharArray()) {
        
                set.add(c);
            }
            for(Character c :str1.toUpperCase().toCharArray()) {
        
                if(!set.contains(c)) {
        
                    System.out.print(c);
                    set.add(c);
                }
            }
            System.out.println();
        }
    }

![在这里插入图片描述][37e79001ef0e48bfa18830048f740fe8.png]  
细心的同学可能会发现我们为什么要把这个坏键添加进去，如果我们不添加，我们可能会将一个坏键多次输出。

![在这里插入图片描述][e941c48366574efaa51847198f84cbbe.png]

## 四、前K个高频单词 ##

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。  
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。  
![在这里插入图片描述][348c942379eb42c09449157e5ef9bfdc.png]  
**思路分析：**  
1.我们先构建一个HashMap去统计一个单词次数  
2.创建一个按字典顺序 排序的优先级队列（小根堆）  
3.遍历HashMap,前k个直接放入，后面去比较，如果Value大于peek()直接放入，如果等于去比较Key,如果插入的Key小则直接放入  
4.然后将优先级队列的元素放入List中，借助Collections集合逆序一下。

但我们发现会有一些特殊情况，当Value相同时，我们需要去改变调整方式。  
![在这里插入图片描述][640fb81e226c4007a54bb968b8aa13ef.png]  
我们可以发现源码中==时直接就break了，我们需要当Value相同时去比较Key，将Key大的放在上面。  
![在这里插入图片描述][981e5b511ae740d99b57cfe06c02772f.png]  
我们在优先级队列传入比较器中需要稍加修改即可。

public List<String> topKFrequent(String[] words, int k) {
        
            List<String> list = new ArrayList<>();
            Map<String,Integer> map = new HashMap<>();
            //1.统计单词次数
            for (int i = 0; i < words.length; i++) {
        
                if(!map.containsKey(words[i])) {
        
                    map.put(words[i],1);
                }else {
        
                    map.put(words[i],map.get(words[i]) + 1);
                }
            }
            //2.创建一个优先级队列（小根堆）
            PriorityQueue<Map.Entry<String,Integer>> priorityQueue = new PriorityQueue<>(k,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.比较，确定前k个
            for (Map.Entry<String, Integer> m:map.entrySet()) {
        
                if(priorityQueue.size() < k) {
        
                    priorityQueue.offer(m);
                }else {
        
                    if(m.getValue().compareTo(priorityQueue.peek().getValue()) > 0) {
        
                        priorityQueue.poll();
                        priorityQueue.offer(m);
                    }else if(m.getValue().compareTo(priorityQueue.peek().getValue()) == 0) {
        
                        if(priorityQueue.peek().getKey().compareTo(m.getKey()) > 0) {
        
                            priorityQueue.poll();
                            priorityQueue.offer(m);
                        }
                    }
                }
            }
            //4.放入List
            for (int i = 0; i < k; i++) {
        
                list.add(priorityQueue.poll().getKey());
            }
            //5.逆序
            Collections.reverse(list);
            return list;
        }

[1776aeff2bf44631951d10ca8f98f4fa.gif_pic_center]: https://img-blog.csdnimg.cn/1776aeff2bf44631951d10ca8f98f4fa.gif#pic_center
[c29f3b08697d4555b1e13deb6379c194.png]: https://img-blog.csdnimg.cn/c29f3b08697d4555b1e13deb6379c194.png
[ebb7dafb9c9d4c91985009436963c464.png]: https://img-blog.csdnimg.cn/ebb7dafb9c9d4c91985009436963c464.png
[c72f0361d0234211bd22289c7e233923.png]: https://img-blog.csdnimg.cn/c72f0361d0234211bd22289c7e233923.png
[6322e903b1644bfb91e978340ad38170.png]: https://img-blog.csdnimg.cn/6322e903b1644bfb91e978340ad38170.png
[57bcb53146224fb0ba97b1b85fca1e9b.png]: https://img-blog.csdnimg.cn/57bcb53146224fb0ba97b1b85fca1e9b.png
[37e79001ef0e48bfa18830048f740fe8.png]: https://img-blog.csdnimg.cn/37e79001ef0e48bfa18830048f740fe8.png
[e941c48366574efaa51847198f84cbbe.png]: https://img-blog.csdnimg.cn/e941c48366574efaa51847198f84cbbe.png
[348c942379eb42c09449157e5ef9bfdc.png]: https://img-blog.csdnimg.cn/348c942379eb42c09449157e5ef9bfdc.png
[640fb81e226c4007a54bb968b8aa13ef.png]: https://img-blog.csdnimg.cn/640fb81e226c4007a54bb968b8aa13ef.png
[981e5b511ae740d99b57cfe06c02772f.png]: https://img-blog.csdnimg.cn/981e5b511ae740d99b57cfe06c02772f.png