Map与Set面试题（高频）

目录

 

1.只出现一次的数字

1.1题目描述

1.2思考过程

1.3代码

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

2.1题目描述

2.2思考过程

2.3代码 

3.宝石与石头

3.1题目描述

3.2思考过程

3.3代码 

4.旧键盘打字

4.1题目描述

4.2思考过程

 4.3代码

5.前K个高频单词

5.1题目描述

5.2思考过程

5.3代码 

---

 

1.只出现一次的数字

OJ：oj链接

1.1题目描述

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

说明：

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

---

1.2思考过程

---

 

1.3代码

1.3.1 异或

public int singleNumber(int[] nums) {
        int ret=0;
        for(int x:nums){
            ret^=x;
        }
        return ret;
    }

用异或来做这道题非常简单，只需要全部遍历一遍，然后全部异或起来，最终就得到了结果，时间复杂度，空间复杂度都很低，对这道题来说，异或来做是最优解。

---

3.3.2 Set来做

public int singleNumber(int[] nums) {
        Set<Integer> set=new HashSet<>();
        for(int x:nums){
            if(set.contains(x)){
                set.remove(x);
            }else{
                set.add(x);
            }
        }
        for(int x:nums){
            if(set.contains(x)){
                return x;
            }
        }
        return -1;
 
    }

第二种方法我们可以用Set来做，由于Set里面放的都是不重复的重复的只能放进去- -次，我们可以遍历这个数组，如果Set里已经有了，就直接删除即可，没有就添加进去，最后只剩下只出现-次的数字还在set中，最遍历数组如果set中有输出即可。

---

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

OJ：oj链接

2.1题目描述

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

---

2.2思考过程

---

2.3代码 

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

首先我们遍历一遍链表，new 新的节点。用map将原来的所有节点与新的节点一- -对应起来，存储在map中，然后用get()方法对他们进行访问，把一个个节点全都串起来。

---

3.宝石与石头

OJ：oj链接

3.1题目描述

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

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

---

3.2思考过程

---

3.3代码 

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

我们只需要将宝石数组中的玄素全部放在set中，然后遍历stones字符串，定义一个计数，器count,每次看set中是否包含,包含count就加一。

注意：要用toCharArray()方法将字符串转变为字符数组。

---

4.旧键盘打字

OJ：oj链接

4.1题目描述

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

输入描述:

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

输出描述:

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

输入

7_This_is_a_test
_hs_s_a_es

输出

7TI

---

4.2思考过程

---

 4.3代码

import java.util.HashSet;
import java.util.Locale;
import java.util.Scanner;
public class Main {
        public static void func(String inPut,String outPut){
        HashSet<Character> set1=new HashSet<>();
        for (char ch:outPut.toUpperCase().toCharArray()) {
            set1.add(ch);
        }
        HashSet<Character> set2=new HashSet<>();
        for (char ch:inPut.toUpperCase().toCharArray()){
            if(!set1.contains(ch)&&!set2.contains(ch)){
                System.out.print(ch);
                set2.add(ch);
            }
        }
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNextLine()){
            String inPut=scanner.nextLine();
            String outPut=scanner.nextLine();
            func(inPut,outPut);
        }
    }
}

首先我们将实际键盘输出的字符串，全部转变为大写，并存在set1中。接着我们遍历键盘输入的字符串，如果set1中存在且set2中不存在就把它打印，并添加到set2中，防止打印多次。

注意：

1. 题目最后要求输出为大写，所以我们直接存时直接用toUpperCase()方法转换为大写。
2. set2存在的意义是防止打印重复。

---

5.前K个高频单词

OJ：oj链接

5.1题目描述

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

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

示例 1：

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

---

5.2思考过程

---

5.3代码 

public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map=new HashMap<>();
        for(String str:words){
            if(!map.containsKey(str)){
                map.put(str,1);
            }else{
                int key=map.get(str);
                map.put(str,key+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> minQueue=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(minQueue.size()<k){
                minQueue.offer(entry);
            }else{
                Map.Entry<String, Integer>top=minQueue.peek();
                if(entry.getValue().compareTo(top.getValue())==0){
                    if(entry.getKey().compareTo(top.getKey())<0){
                        minQueue.poll();
                        minQueue.offer(entry);
                    }
                }else {
                    if(entry.getValue().compareTo(top.getValue())>0){
                        minQueue.poll();
                        minQueue.offer(entry);
                    }
                }
            }
        }
        List<String> ret=new ArrayList<>();
        for(int i=0;i<k;i++){
            String str=minQueue.poll().getKey();
            ret.add(str);
        }
        
        Collections.reverse(ret);
        return ret;
    }

首先我们可以用输入全部遍历一遍，然后把它们出现的次数也统计，并一一对应的存放在map中。这也属于top-k问题，所以也需要用对来解决，我们先建立一一个k大小的小堆，然后，我map，将它们一一-往小堆里放，每次和堆顶元素的val值先比较，val如果大就入队，相等就compareto()比较字典序，最后堆中就是前k个高频单词。

注意：

1. 我们拿到key和value的一一对应关系我们要用到entryset()方法最后拿到的类型为Map.Entry<String,Integer>。
2. 由于我们拿到的是它们一一对应关系建的堆，为特殊类型，所以我们要写一个比较器在实例化堆时给它。
3. 这里用到的类型都是包装类所以我们全部要用comperto()来比较。
4. 由于是创建的是小堆，最后我们给ret时要反转一下正好次数多的在前，用Collectio.reverse()方法翻转。