数据结构之 Map 和 Set_字符串 包含 map

Map 和 Set 是一种适合动态查找的集合容器

Map中存储的是 key-value 的键值对，Set中只存储了 Key

HashMap的使用简单案例

package Map_Set;

import java.util.HashMap;
import java.util.Map;

public class Test_HashMap {
    public static void main(String[] args) {
        Map<String,String> hashMap = new HashMap<>();

        // put
        hashMap.put("0","张三");
        hashMap.put("1","李四");
        hashMap.put("2","王五");
        hashMap.put("3","孙六");
        hashMap.put(null,null);
        // HashMap 与 TreeMap 的不同，HashMap 的 key 可以为空
        System.out.println(hashMap.size());
        System.out.println(hashMap);

        // put的细节：如果key存在，会使用value替换原来key所对应的value，返回旧value
        String str = hashMap.put("3","鲁七");
        System.out.println(str);
        System.out.println(hashMap);

        // get:如果key存在，返回key所对应的value;如果key不存在，返回null
        System.out.println(hashMap.get(3));

        System.out.println(hashMap.getOrDefault("4","找不到"));

        System.out.println(hashMap.containsKey("4"));

        System.out.println(hashMap.containsValue("3"));

        for (String s:
             hashMap.keySet()) {
            System.out.print(s+" ");
        }
        System.out.println();

        for (String s:
             hashMap.values()) {
            System.out.print(s+" ");
        }
        System.out.println();

        for (Map.Entry<String ,String> entry:hashMap.entrySet()){
            System.out.print(entry.getKey()+":"+entry.getValue()+" ");
        }
        System.out.println();
    }
}
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
49
50
51

TreeMap的使用简单案例

package Map_Set;
import java.util.Map;
import java.util.TreeMap;
public class Test_TreeMap {

    public static void main(String[] args) {
        Map<String,String> treeMap = new TreeMap<>();

        // put(key,value):插入key-value的键值对
        // key 和 value 可以为空
        treeMap.put("0","张三");
        treeMap.put("1","李四");
        treeMap.put("2","王五");
        treeMap.put("3","孙六");
        // TreeMap 的 key 不能为空
        treeMap.put("4",null);
        System.out.println(treeMap.size());

        System.out.println(treeMap);

        // put的细节：如果key存在，会使用value替换原来key所对应的value，返回旧value
        String str = treeMap.put("4","鲁七");
        System.out.println(treeMap);
        System.out.println(str);

        // get:如果key存在，返回key所对应的value;如果key不存在，返回null
        System.out.println(treeMap.get("4"));

        //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
        System.out.println(treeMap.getOrDefault("5","没有"));

        // containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
        // 按照红黑树的性质来进行查找
        // 找到返回true，否则返回false
        System.out.println(treeMap.containsKey("4"));

        // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
        // 因为TreeMap是按照Key进行组织的，因此查找value时候就需要整体遍历
        // 找到返回true，否则返回false
        System.out.println(treeMap.containsValue("1"));
        System.out.println(treeMap.containsValue("6"));

        // 打印所有的key
        // keySet是将map中的key放置在Set中返回的
        for (String s:
             treeMap.keySet()) {
            System.out.print(s+" ");
        }
        System.out.println();

        // 打印所有的value
        // values()是将map中的value放在collect的一个集合中返回的
        for (String s:
             treeMap.values()) {
            System.out.print(s+" ");
        }
        System.out.println();

        // 打印所有的键值对
        // entrySet(): 将Map中的键值对放在Set中返回了
        for (Map.Entry<String,String> entry:treeMap.entrySet()){
            System.out.print(entry.getKey() +":"+entry.getValue()+" ");
        }
        System.out.println();
    }
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

注意：

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

TreeSet的简单使用案例

package Map_Set;

import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class Test_TreeSet {

    public static void main(String[] args) {

        Set<String> set = new TreeSet<>();

        // add(key): 如果key不存在，则插入，返回ture
        // 如果key存在，返回false
        set.add("0");
        set.add("1");
        set.add("2");
        set.add("3");
        set.add("3");
        System.out.println(set.size());
        System.out.println(set);

        System.out.println(set.contains("3"));
        System.out.println(set.contains("4"));

        set.remove("3");
        System.out.println(set);

        // Set 继承了 Iterator 接口
        // 可以使用迭代器打印
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();

    }
}
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

HashSet的简单使用案例

package Map_Set;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Test_HashSet {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("0");
        set.add("1");
        set.add("2");
        System.out.println(set);
        System.out.println(set.size());

        System.out.println(set.contains("2"));

        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();

        set.removeAll(set);
        System.out.println(set);
    }
}
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

注意：

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
8. TreeSet 和 HashSet 的区别

————————————————————————————————————————————

具体应用的简单案例

1.有十万个数据，找到第一个重复的数据

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            Random random = new Random();
            list.add(random.nextInt(20));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < 20; i++) {
            if(!set.add(list.get(i))){
                System.out.print(list.get(i));
                break;
            }else{
            	set.add(list.get(i));
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.随机生成 0-9999 之间的十万个数据，去除掉所有重复的数据

package Map_Set;

import java.util.*;

public class Test_Demo1 {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 10_0000; i++) {
            list.add(random.nextInt(10_0000));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < list.size(); i++) {
            set.add(list.get(i));
        }

        System.out.println(list.size());
        System.out.println(set.size());
        System.out.println(set);
    }

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

3.有十万个数据，统计每个数据出现了多少次

	public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            Random random = new Random();
            list.add(random.nextInt(20));
        }
        Map<Integer,Integer> hashmap = new HashMap<>();
        for (Integer key:
             list) {
            if(hashmap.get(key) == null){
                hashmap.put(key,1);
            }else {
                int count = hashmap.get(key);
                hashmap.put(key,count+1);
            }
        }

        for (Map.Entry<Integer,Integer> entry:
             hashmap.entrySet()) {
            if(entry.getValue()>1){
                System.out.println("重复的数据"+entry.getKey()+"出现的次数"+entry.getValue());
            }
        }
        System.out.println(hashmap);
    }
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

leetcode136.只出现一次的数字

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

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

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

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

解题思路

1. 通过 Set 来解题
2. 遍历数组，如果数组中的元素出现过两次，则在 Set 中删除该元素
3. 否则就将元素插入到 Set 中
4. 再次遍历数组，与 Set 中的元素进行对比，此时 Set 中包含的元素就是那个只出现一次的元素

代码如下

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet();

        for(int i=0;i<nums.length;i++){
            if(set.contains(nums[i])){
                set.remove(nums[i]);
            }else{
                set.add(nums[i]);
            }
        }

        for(int i=0;i<nums.length;i++){
            if(set.contains(nums[i])){
                return nums[i];
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

解题思路

1. 首先对链表做非空判断
2. 首先循环遍历链表，并且创建新链表的节点，并进行赋值
3. 利用 HashMap 将两个链表的地址对应关系进行对应
4. 再次遍历旧链表，根据 HashMap 中保存的对应关系对 新链表的引用进行赋值
5. 再次根据 HashMap 中的对应关系返回新链表的头结点

代码如下

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        Map<Node,Node> hashmap = new HashMap<>();
        Node cur = head;
        while(cur != null){
            Node node = new Node(cur.val);
            hashmap.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            // hashmap.get(cur) 指的就是新创建的节点 node
            hashmap.get(cur).next = hashmap.get(cur.next);
            hashmap.get(cur).random = hashmap.get(cur.random);
            cur = cur.next;
        }
        // 返回新创建链表节点的引用
        return hashmap.get(head);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

leetcode771.宝石与石头

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

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

示例 1：
输入：jewels = “aA”, stones = “aAAbbbb”
输出：3

示例 2：
输入：jewels = “z”, stones = “ZZ”
输出：0

解题思路

1. 创建一个 Set 容器，遍历黄金字符串中的每一个字符中，并且 add 加入到 Set 容器中
2. 遍历石头字符串的每一个字符，并与 Set 容器中的元素进行比较 计数。

代码如下

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        int count = 0;
        for(char ch : jewels.toCharArray()){
            set.add(ch);
        }
        for(char 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)

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

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

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

示例1
输入
7_This_is_a_test
_hs_s_a_es
输出
7TI

解题思路

1. 创建两个字符串，一个代表期望输入的字符串，一个代表实际输入的字符串
2. 创建两个 Set 容器，一个用于保存 遍历实际输入的字符串的字符
3. 注意实际输入的字符串要全部转换为大写
4. 遍历实际输入字符串的字符，找出符合 在 两个Set 容器中都不存在的字符
5. !setBroken.contains(ch) 的作用就是用于过滤循环输出的情况

代码如下

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();    // 期望输入
        String str2 = scanner.nextLine();    // 实际输入
        
        HashSet<Character> setActual = new HashSet<>();
        
        for(char ch : str2.toUpperCase().toCharArray()){
            setActual.add(ch);
        }
        
        HashSet<Character> setBroken = new HashSet<>();
        
        for(char ch : str1.toUpperCase().toCharArray()){
            if(!setActual.contains(ch) && !setBroken.contains(ch)){
                setBroken.add(ch);
                System.out.print(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

leetcode692.前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 次。

解题思路

代码如下

leetcode387.字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：
输入: s = “leetcode”
输出: 0

示例 2:
输入: s = “loveleetcode”
输出: 2

class Solution {
    public int firstUniqChar(String s) {
        if(s==null){
            return -1;
        }
        HashMap<Character,Integer> map = new HashMap<>();
        for(char ch : s.toCharArray()){
            if(map.get(ch)==null){
                map.put(ch,1);
            }else{
                int count = map.get(ch);
                map.put(ch,count+1);
            }
        }
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(map.get(ch) == 1){
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23