【LC】HashMap和HashSet应用OJ

逃离我推掉我的手 2024-04-26 10:53 52阅读 0赞

![在这里插入图片描述][3f9026f5c260455c8ecd6dfef03f83ed.gif_pic_center]

✨**博客主页:**[ **心荣~**][Link 1]  
✨**系列专栏:**[**【LeetCode/牛客刷题】**][LeetCode]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

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

*  1. 只出现一次的数字
 *  2. 复制带随机指针的链表
 *  3. 宝石与石头
 *  4. 旧键盘
 *  5. 前K个高频单词
 *  6. 下厨房

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

**在线OJ** : [136. 只出现一次的数字][136.]

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

**说明**：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

**示例 1**:

输入: [2,2,1]
    输出: 1

**示例 2**:

输入: [4,1,2,1,2]
    输出: 4

?**解题思路**:

*  **思路1**：

使用异或 ; 相同的两个数异或的结果是0，把数组所有数异或一遍，由于给定的数据一定有一个唯一的，所以最终得到的结果就是唯一数。

*  **思路2**：

使用Set，Set中的元素不重复，遍历数组 , 判断Set中是否含有这个数，如果含有这个数，就将Set里面的这个数删除，否则存入该数，最终Set剩下的数为唯一数。

class Solution {
        
        //方法一:练习使用Set
        public int singleNumber(int[] nums) {
        
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
        
                if(!set.contains(nums[i])) {
        
                    set.add(nums[i]);
                }else{
        
                    set.remove(nums[i]);
                }
            }
    
            for (int i = 0; i < nums.length; i++) {
        
                if(set.contains(nums[i])) {
        
                    return nums[i];
                }
            }
            return -1;
        }
        //方法二:使用异或
        /*public int singleNumber(int[] nums) {
            int ret = 0;
            for (int i = 0; i < nums.length; i++) {
                ret ^= nums[i];
            }
            return ret;
        }*/
    }

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

**在线OJ** : [138. 复制带随机指针的链表][138.]

给你一个长度为 **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** 作为传入参数。

**示例 1**：

![img][]

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

**示例 2**：

![img][img 1]

输入：head = [[1,1],[2,1]]
    输出：[[1,1],[2,1]]

**示例 3**：

![img][img 2]

输入：head = [[3,null],[3,0],[3,null]]
    输出：[[3,null],[3,0],[3,null]]

**提示**：

*  0 <= n <= 1000
 *  \-104 <= Node.val <= 104
 *  Node.random 为 null 或指向链表中的节点。

?**解题思路**:

使用Map，键值对为<已知链表结点地址, 复制链表结点地址>

第一次遍历已知链表时，创建复制链表对象的结点并将它们结点地址以<已知链表结点地址, 复制链表结点地址>键值对的形式存入Map中，然后第二次遍历已知链表，根据已知链表结点找到Map中对应复制链表的结点将复制链表结点链接起来 .

/*
    // Definition for a Node.
    class Node {
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    */
    
    class Solution {
        
        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);
        }
    }

## 3. 宝石与石头 ##

**在线OJ** : [771. 宝石与石头][771.]

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

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

**示例 1**：

输入：jewels = "aA", stones = "aAAbbbb"
    输出：3

**示例 2**：

输入：jewels = "z", stones = "ZZ"
    输出：0

**提示**：

*  1 <= jewels.length, stones.length <= 50
 *  jewels 和 stones 仅由英文字母组成
 *  jewels 中的所有字符都是 **唯一的**

?**解题思路**:

将宝石 jewels 放入Set中，设置一个计数器 , 然后遍历石头stones 判断 jewels中是否含有stones 中的字符，含有则计数器++ .

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

## 4. 旧键盘 ##

**在线OJ** : \[[编程题\]旧键盘][Link 2]

**题目详情**：

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

**输入描述**:

输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、以及下划线“\_”（代表空格）组成。题目保证2个字符串均非空。

**输出描述**:

按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。

**输入** :

7_This_is_a_test
    _hs_s_a_es

**输出** :

7TI

?**解题思路**:

对比应该输入的字符串和实际得到的字符串，如果应该输入字符串中的字母没有出现在实际得到的字符串中，则这些字母就是键盘中坏了的字母键。

我们可将实际被输入的字符串添加到Set中，然后遍历应该输入的字符串，找到Set中不存在的字母，并输出这些字母，

由于应该输入的字符串中可能存在重复的字符，且要按顺序输出，我们可以采用一个辅助的集合Set用来查重，就是输出前判断这个集合中是否含有这个字符，如果含有则不输出，不含有则输出并将该元素放入辅助集合中。

import java.util.HashSet;
    import java.util.Scanner;
    import java.util.Set;
    
    public class Main {
        
        public static void func(String strInput, String strOutput) {
        
            Set<Character> set = new HashSet<>();
            for (char ch : strOutput.toUpperCase().toCharArray()) {
        
                set.add(ch);
            }
    
            Set<Character> badSet = new HashSet<>();
            for (char ch : strInput.toUpperCase().toCharArray()) {
        
                if(!badSet.contains(ch) && !set.contains(ch)) {
        
                    badSet.add(ch);
                    System.out.print(ch);
                }
            }
        }
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            String strInput = scanner.nextLine();
            String strOutput = scanner.nextLine();
            func(strInput, strOutput);
        }
    }

## 5. 前K个高频单词 ##

**在线OJ** : [692. 前K个高频单词][692. _K]

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

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

**示例 1**：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
    输出: ["i", "love"]
    解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
        注意，按字母顺序 "i" 在 "love" 之前。

**示例 2**：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
    输出: ["the", "is", "sunny", "day"]
    解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
        出现次数依次为 4, 3, 2 和 1 次。

**注意**：

*  1 <= words.length <= 500
 *  1 <= words\[i\] <= 10
 *  words\[i\] 由小写英文字母组成。
 *  k 的取值范围是 \[1, 不同 words\[i\] 的数量\]

**进阶**：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

?**解题思路**:

1.  使用Map统计单词词频。
2.  利用topK求前k个词频频率最高的元素（所以需要小根堆），如果出现词频相同的单词，优先保留字典顺序在前的。
3.  将堆里面的元素存入List，并使用Collections类工具逆序List。
4.  返回List。

注意: 我们在一开始构造完大小为K的小根堆时 , 堆中可能会有相同频率的元素, 题目要求频率相同时, 要以字典顺序在前的优先 ; 所以当频率相同时, 我们需要更改比较器的比较方式, 让其以字符串去比较; 也就是说在重写比较器的compare方法时，除了考虑单词频，还需要考虑词频相同时，将字典顺序较大的单词放在堆顶。

class Solution {
        
        public List<String> topKFrequent(String[] words, int k) {
        
            //统计每个单词出现的次数
            Map<String, Integer> map = new HashMap<>();
            for (String word:words) {
        
                if(map.get(word) == null)  {
        
                    map.put(word,1);
                }else {
        
                    Integer val = map.get(word);
                    map.put(word, val+1);
                }
            }
            //建立大小为k的小根堆
            PriorityQueue<Map.Entry<String,Integer>> minHeap = 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());
                }
            });
    
            for (Map.Entry<String,Integer> entry:map.entrySet()) {
        
                if(minHeap.size() < k) {
        
                    minHeap.offer(entry);
                }else {
        
                    Map.Entry<String, Integer> top = minHeap.peek();
                    if(entry.getValue().compareTo(top.getValue()) > 0) {
        
                        minHeap.poll();
                        minHeap.offer(entry);
                    }else {
        
                        if(entry.getValue().compareTo(top.getValue()) == 0) {
        
                            if(entry.getKey().compareTo(top.getKey()) < 0) {
        
                                minHeap.poll();
                                minHeap.offer(entry);
                            }
                        }
                    }
                }
            }
    
            List<String> ret = new ArrayList<>();
            for (int i = 0; i < k; i++) {
        
                ret.add(minHeap.poll().getKey());
            }
            Collections.reverse(ret);
            return ret;
        }
    }

## 6. 下厨房 ##

**在线OJ** : [WY8 下厨房][WY8]

**题目详情**：

牛牛想尝试一些新的料理，每个料理需要一些不同的材料，问完成所有的料理需要准备多少种不同的材料。

**输入描述**:

每个输入包含 1 个测试用例。每个测试用例的第 i 行，表示完成第 i 件料理需要哪些材料，各个材料用空格隔开，输入只包含大写英文字母和空格，输入文件不超过 50 行，每一行不超过 50 个字符。

**输出描述**:

输出一行一个数字表示完成所有料理需要多少种不同的材料。

**输入**:

BUTTER FLOUR
    HONEY FLOUR EGG

**输出**:

?**解题思路**:

1.  题目中有多组输入
2.  利用split()方法将输入的字符串以空格分割到数组当中, 再遍历数组放到一个Set中
3.  输出Set中元素个数即可.

import java.util.HashSet;
    import java.util.Scanner;
    import java.util.Set;
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            Set<String> set = new HashSet<>();
            while (scanner.hasNext()) {
        
                String str = scanner.nextLine();
                String[] strs = str.split(" ");
                for (String s : strs) {
        
                    set.add(s);
                }
            }
            System.out.println(set.size());
        }
    }

[3f9026f5c260455c8ecd6dfef03f83ed.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f1036da29a5045878829656f671f5cc7.gif
[Link 1]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[LeetCode]: https://blog.csdn.net/trong_/category_11997769.html
[136.]: https://leetcode-cn.com/problems/single-number/
[138.]: https://leetcode-cn.com/problems/copy-list-with-random-pointer/
[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/ee7e3b4ca78a4a36a0d38db98e5f5cfb.png
[img 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/9842c942e98948b4bd460872d19adfea.png
[img 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f71e16544ca8408fa0d96303c25fc2db.png
[771.]: https://leetcode-cn.com/problems/jewels-and-stones/
[Link 2]: https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
[692. _K]: https://leetcode-cn.com/problems/top-k-frequent-words/
[WY8]: https://www.nowcoder.com/practice/ca5c9ba9ebac4fd5ae9ba46114b0f476?tpId=122&tqId=33654&ru=/exam/oj