【Map与Set】之LeetCode&牛客练习

太过爱你忘了你带给我的痛 2023-09-28 16:56 70阅读 0赞

**目录**

1. 只出现一次的数字

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

3. 宝石与石头

4. 旧键盘

5. 前k个高频单词

--------------------

## **1. 只出现一次的数字** ##

**题目链接：**[136. 只出现一次的数字][136.]

**题目要求：**

![2996cdf9eb4d4f468c57a3a9a4f96e7b.png][]

**分析一下：**

![6fe2d85ce31348438264f0332e65774b.png][]

**上代码：**

//2.使用集合 
        //时间复杂度：O(n)
        public int singleNumber(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for(int i = 0; i < nums.length; i++) {
                int key = nums[i];
                if(!set.contains(key)) {
                    set.add(nums[i]);
                }else {
                    set.remove(key);
                }
            }
            //此时集合，就剩一个元素了 找到这个元素
            for(int i = 0; i < nums.length; i++) {
                int key = nums[i];
                if(set.contains(key)) {
                    return nums[i];
                }
            }
            return -1;
        }

--------------------

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

**题目链接：**[138. 复制带随机指针的链表][138.]

**题目要求：**

![d10b10d89c374460b8497665e599d1a4.png][]

**分析一下：**

![39a161e4fe8d4562a794748fb1dbd05a.png][]

**上代码：**

class Solution {
        public Node copyRandomList(Node head) {
            //注意不能使用treemap不然不能比较
            Map<Node,Node> map = new HashMap<>();
            //1.第一次遍历链表
            Node cur = head;
            while(cur != null) {
                Node node = new Node(cur.val);
                map.put(cur,node);
                cur = cur.next;
            }
            //2.第二次遍历链表
            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);
        }
    }

--------------------

## **3. 宝石与石头** ##

**题目链接：**[771. 宝石与石头][771.]

**题目要求：**

![86f35f499698450092303792d3ef5c79.png][]

**分析一下：**

![607951bc8d724964b5d8fd7993476f0f.png][]

**上代码：**

class Solution {
        public int numJewelsInStones(String jewels, String stones) {
            Set<Character> set = new HashSet<>();
            //把宝石放进集合中
            for(char ch : jewels.toCharArray()) {
                set.add(ch);
            }
            int count = 0;
            //遍历石头，在石头中找宝石，计数++
            for(char ch : stones.toCharArray()) {
                if(set.contains(ch)) {
                    count++;
                }
            }
            return count;
        }
    }

--------------------

## **4. 旧键盘** ##

**题目链接：**[旧键盘 (20)\_\_牛客网 (nowcoder.com)][_20_ _nowcoder.com]

**题目要求：**

![de2fd6424c074daca44d6ab736ad21d1.png][]

**分析一下：**

![b0e78b771c4149dc94ef6580a660c47e.png][]

**上代码：**

import java.util.*;
    
    public class Main {
        public static void func(String str1,String str2) {
            Set<Character> set = new HashSet<>();
            //str2先转大写，再转数组，然后放入集合
            for(char ch : str2.toUpperCase().toCharArray()) {
                set.add(ch);
            }
            //遍历希望输入的，转为大写，再转数组，和实际输入进行比较
             Set<Character> set2 = new HashSet<>();
             for(char ch : str1.toUpperCase().toCharArray()) {
                if(!set.contains(ch) && !set2.contains(ch)) {
                    System.out.print(ch);
                    set2.add(ch);
                }
            }
        }
        
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            while(scan.hasNextLine()) {
                String str1 = scan.nextLine();//希望输入的
                String str2 = scan.nextLine();//实际输入的
                
                func(str1,str2);
            }
        }
    }

--------------------

## **5. 前k个高频单词** ##

**题目链接：**[692. 前K个高频单词][692. _K]

**题目要求：**

![c00c78ee791b4da49bfcaaba0dbaf814.png][]

**分析一下：**

![28cdc74ca11c4f269afd12110759b579.png][]

**上代码：**

class Solution {
        public List<String> topKFrequent(String[] words, int k) {
            //1.统计单词出现的次数
            Map<String,Integer> map = new HashMap<>();
            for(String key : words) {
                if(map.get(key) == null) {
                    map.put(key,1);
                }else {
                    int val = map.get(key);
                    map.put(key,val+1);
                }
            }
            //2.建立大小为k的小根堆
            PriorityQueue<Map.Entry<String,Integer>> minQ = new PriorityQueue<>(k,new Comparator<Map.Entry<String,Integer>>(){
                @Override
                public int compare(Map.Entry<String,Integer> o1, Map.Entry<String,Integer> o2) {
                    //单词出现次数相同时，调整以key为准的大根堆
                    if(o1.getValue().compareTo(o2.getValue()) == 0) {
                        return o2.getKey().compareTo(o1.getKey());
                    }
                    return o1.getValue().compareTo(o2.getValue());
                    //根据单词出现的次数创建小根堆
                }
            });
    
            //3.遍历map,先给小根堆放满k个，然后从第k+1开始，和堆顶元素比较
            for(Map.Entry<String,Integer> entry : map.entrySet()) {
                if(minQ.size() < k) {
                //如果小根堆没有放满，就继续放    
                    minQ.offer(entry);
                }else {
                    //如果已经放满了小根堆，那么此时就要让当前元素和堆顶元素进行比较
                    Map.Entry<String,Integer> top = minQ.peek();
                    if(top != null) {
                        if(entry.getValue() > top.getValue()) {
                        minQ.poll();
                        minQ.offer(entry);
                        }else {
                            //如果此时<不用管，但如果=,就要根据题意按字典顺序排
                            if(top.getValue().compareTo(entry.getValue()) == 0) {
                                //value一样，看key
                                if(top.getKey().compareTo(entry.getKey()) > 0) {
                                    minQ.poll();
                                    minQ.offer(entry);
                                }
                            }
                        }
                    }
                    
                }
            }
            //此时前k个次数最多的单词，已经全部放入堆中了，将堆中元素出堆
            List<String> ret = new ArrayList<>();
            for(int i = 0; i < k; i++) {
                Map.Entry<String,Integer> top  = minQ.poll();
                if(top != null) {
                    ret.add(top.getKey());
                }
                
            }
            //前面是小根堆出堆的，根据次数高到低的要求，这就要逆置
            Collections.reverse(ret);
            return ret;
        }
    }

--------------------

[136.]: https://leetcode.cn/problems/single-number/
[2996cdf9eb4d4f468c57a3a9a4f96e7b.png]: https://img-blog.csdnimg.cn/2996cdf9eb4d4f468c57a3a9a4f96e7b.png
[6fe2d85ce31348438264f0332e65774b.png]: https://img-blog.csdnimg.cn/6fe2d85ce31348438264f0332e65774b.png
[138.]: https://leetcode.cn/problems/copy-list-with-random-pointer/
[d10b10d89c374460b8497665e599d1a4.png]: https://img-blog.csdnimg.cn/d10b10d89c374460b8497665e599d1a4.png
[39a161e4fe8d4562a794748fb1dbd05a.png]: https://img-blog.csdnimg.cn/39a161e4fe8d4562a794748fb1dbd05a.png
[771.]: https://leetcode.cn/problems/jewels-and-stones/
[86f35f499698450092303792d3ef5c79.png]: https://img-blog.csdnimg.cn/86f35f499698450092303792d3ef5c79.png
[607951bc8d724964b5d8fd7993476f0f.png]: https://img-blog.csdnimg.cn/607951bc8d724964b5d8fd7993476f0f.png
[_20_ _nowcoder.com]: https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
[de2fd6424c074daca44d6ab736ad21d1.png]: https://img-blog.csdnimg.cn/de2fd6424c074daca44d6ab736ad21d1.png
[b0e78b771c4149dc94ef6580a660c47e.png]: https://img-blog.csdnimg.cn/b0e78b771c4149dc94ef6580a660c47e.png
[692. _K]: https://leetcode.cn/problems/top-k-frequent-words/
[c00c78ee791b4da49bfcaaba0dbaf814.png]: https://img-blog.csdnimg.cn/c00c78ee791b4da49bfcaaba0dbaf814.png
[28cdc74ca11c4f269afd12110759b579.png]: https://img-blog.csdnimg.cn/28cdc74ca11c4f269afd12110759b579.png