数据结构 Java数据结构 --- Map和Set_数据结构mapstr

Map 和 Set

1. Map

1.1 关于Map的说明

Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

1.2 Map 的常用方法说明

1.3 关于Map.Entry< K, V >的说明

Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式

例:

    public static void main(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        map.put("a",3);
        map.put("h",5);
        map.put("b",4);

        Set<Map.Entry<String, Integer>> entrySet =  map.entrySet();
        for (Map.Entry<String,Integer> entry : entrySet){
            System.out.println(entry.getKey()+"->"+entry.getValue());
        }      
    }
1
2
3
4
5
6
7
8
9
10
11

1.4 Map的注意事项

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2. Map中存放键值对的Key是唯一的，value是可以重复的
3. 在Map中插入键值对时，key不能为空，否则就会抛NullPointerException异常，但是value可以为空.(HashMap可以)
4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

1.5 TreeMap和HashMap的区别

2. Set

2.1 常见方法说明

例:

    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

1
2
3
4
5
6
7
8
9
10
11

2.2 Set的注意事项

1. Set是继承自Collection的一个接口类
2. Set中只存储了key，并且要求key一定要唯一
3. Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
4. Set最大的功能就是对集合中的元素进行去重
5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
7. Set中不能插入null的key

2.3 TreeSet和HashSet的区别

3. 面试题练习

第一题: 只出现一次的数字

LeetCode 136: 只出现一次的数字
描述:
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:

解题思路:

1. 把数组放入Set集合中.因为Set中key是唯一的.
2. 如果元素不在Set中,就添加元素到Set中.
3. 如果元素在Set中,就删除该元素.
4. 遍历结束,返回Set集合中的内容.

代码实现:

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int val : nums){
            if(!set.contains(val)){
                set.add(val);//Set中没有val就添加val到set中
            }else{
                set.remove(val);//set中有val就删除set中的val
            }
        }
        //遍历结束,返回set中的元素
        return set.iterator().next();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第二题: 复制带随机指针的链表

LeetCode 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. 第一次遍历链表,将 老节点 和 新节点 放入 Map中.
2. 第二次遍历链表,通过get方法得到新老节点来修改新节点的next和random
3. map.get(cur).next = map.get(cur.next) 链接新节点的next
4. map.get(cur).random = map.get(cur.random) 链接新节点的random
5. 遍历结束,返回map.get(head)

代码实现:

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,null,null);
            map.put(cur,node);//存储新老节点之间的映射
            cur = cur.next;
        }
        cur = head;
        // 第二次遍历
        while(cur != null){
            map.get(cur).next = map.get(cur.next);//修改next
            map.get(cur).random = map.get(cur.random);//修改random
            cur = cur.next;
        }
        return map.get(head);//返回新节点的头节点       
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第三题: 宝石与石头

LeetCode 771: 宝石与石头
描述:
给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。

解题思路:

1. 遍历字符串jewels将所有字符放入Set集合中.
2. 遍历字符串stones,判断是否字符在Set集合中,如果在就count++;
3. 返回count即可;

代码实现:

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        //遍历jewels 将字符放入到ch中
        for (Character ch:jewels.toCharArray()) {
            set.add(ch);
        }
        int count = 0;
        //遍历stones 判断set中是否有该字符,如果有就count++
        for (Character ch:stones.toCharArray()) {
            if(set.contains(ch)) count++;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第四题: 坏键盘打字

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

解题思路:

1. 分别用except和real接收实际输入和应该输入的字符串.
2. 将两个字符串都变成大写.
3. 遍历real字符串,将字符放入set集合中
4. 遍历except字符串,如果字符在set集合中没有就输出,并放入set1集合中.在每次判断的时候多判断一次.字符也不在set1集合中.

代码实现:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 将输入的内容大写
        String expect = sc.nextLine().toUpperCase();
        String real = sc.nextLine().toUpperCase();
        Set<Character> set = new HashSet<>();
        // 将real字符串的内容放入set集合中
        for (Character ch:real.toCharArray()) {
            set.add(ch);
        }
        // set1集合用来放坏的键盘的字符
        Set<Character> set1 = new HashSet<>();
        for (Character ch:expect.toCharArray()){
        	// 判断两次 以防止多次输出相同的字符
            if(!set.contains(ch) && !set1.contains(ch)){
                System.out.print(ch);
                set1.add(ch);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

第五题: 前K个高频单词

LeetCode 692: 前K个高频单词
描述:
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

解题思路:

1. 先用 Map 记录每个单词出现的次数
2. 再建立一个大小为k的小根堆.按照题目规定 来写Comparator
3. 遍历Map,当堆小于k的时候,直接入堆.当大于k的时候

• 如果堆顶元素出现的次数比当前元素的出现次数小,就出堆顶元素,将当前元素入堆.
• 如果堆顶元素出现的次数等于当前元素出现的次数,且按字典顺序在前面时,就出堆顶元素,将当前元素入堆

4. 最后循环堆,直到堆为空,每次将堆顶元素poll(),并放入到list的0下标处(相当于头插)

代码实现:

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        //建立大小为k的小根堆
        PriorityQueue<Map.Entry<String,Integer>> queue =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().equals(o2.getValue())){
                    //这里是出现次数相同时,根据字典顺序存放的规则
                    return o2.getKey().compareTo(o1.getKey());
                }else {
                	//这里是根据出现次数存放的规则
                    return o1.getValue() - o2.getValue();
                }
            }
        });
        // 记录每个单词出现的次数
        for (String str:words){
            map.put(str,map.getOrDefault(str,0)+1);
        }
        //遍历map
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(queue.size() < k){
            //大小小于k时,直接入堆
                queue.offer(entry);
            }else {
                Map.Entry<String ,Integer> top = queue.peek();
                // 分为堆顶元素出现次数相同 和 堆顶元素出现次数小于当前元素的情况 
                if(top.getValue().compareTo(entry.getValue()) == 0){
                	//当出现次数相同时,把字典顺序在前的放入堆中,在后的不用管
                    if(top.getKey().compareTo(entry.getKey()) > 0){
                        queue.poll();
                        queue.offer(entry);
                    }
                }else if(top.getValue().compareTo(entry.getValue()) < 0){
                    queue.poll();
                    queue.offer(entry);
                }
            }
        }
        //将堆中元素存放在list中
        List<String> list = new ArrayList<>();
        while (!queue.isEmpty()){
            list.add(0,queue.poll().getKey());//按照头插法
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48