🍹前言：

🌈🌈🌈
这是我关于蓝桥杯系列的第4篇文章，其实关于算法的部分并不是很多，大部分的内容都放在了Java语言的基础知识上；希望能够帮助到使用Java参加比赛的同学，将Java这门语言的基础掌握牢固，在比赛之外也能有所收获~
✨✨✨

🌻🌻参加蓝桥杯仅仅会使用数组是远远不够的，很多语言都有自带的数据结构供我们使用，可以极大程度地简化编码。就像使用C++的同学必须熟练掌握STL标准模板库一样，Java城南也有三大家族等着我们探索：List、Set、Map。

☕☕上图中的Java集合并不需要全部掌握，在平时我们只需要掌握以下几个即可：

1. ArrayList——List集合，底层基于数组实现
2. LinkedList——List集合，底层基于链表实现
3. HashSet——Set集合，底层使用哈希表实现
4. TreeSet——Set集合，底层使用二叉树实现
5. HashMap——Map集合，用于存储键值对key-value

🚀题目传送门：

光说不练假把式~这里准备了几道蓝桥杯题库中的题目以供练习👇🏻

（由于List是数组的替代品，使用场景太常见了，所以只给出Set和Map的练习题）

题目	链接
算法训练 集合运算	http://lx.lanqiao.cn/problem.page?gpid=T1474
算法训练 字串统计	http://lx.lanqiao.cn/problem.page?gpid=T219

---

🍑集合详解：

👩🏻‍🏫Java.util包下提供了三个常用的集合接口，分别是List，Set，Map，下面开始逐一介绍~

🍓1.List

📖List接口继承了Collection接口，可以简单的将List当作是一个没有固定长度的数组来使用。

📑List下面有两个实现类最为常用：ArrayList与LinkedList。其中ArrayList的底层是Object[]数组，优势在于可以随机访问，而LinkedList的底层是链表，访问某个元素的效率比ArrayList低，但优势在于需要大量增删改的时候速度很快。

🌈常用方法：

• 构造方法：

  ArrayList<Integer> array = new ArrayList<>();
LinkedList<Integer> array = new LinkedList<>();

  或者直接使用接口代替具体实现类：

  List<Integer> array = new ArrayList<>();
List<Integer> array = new LinkedList<>();

  其中<>中的内容叫做泛型，表示我们在集合中添加的元素只能是泛型所指定的类型，需要注意泛型不能是基本数据类型，要用基本类型的包装类代替。

• 添加元素：void add(E element)

  在指定位置插入元素：void add(int index, E element)，指定位置以及后面的所有元素向后移动一个位置。

• 返回集合的长度：int size()

• 向List中添加另一个集合中的全部元素：

  boolean addAll(Collection<? extends E> c)

  在指定位置插入另一个集合中的全部元素：

  boolean addAll(int index, Collection<? extends E> c)

• 返回List集合中指定索引位置的元素：

  E get(int index)

• 返回list集合中第一次出现o对象的索引位置

  int indexOf(Object o)

  如果list集合中没有o对象，返回-1

• 删除指定索引的元素：E remove(int index)

• 将索引为index位置的元素更改为element元素：E set(int index, E element)

示例代码：🌼

public static void main(String[] args) {
        List<Integer> array = new ArrayList<>();
        array.add(1);
        array.add(2);
        array.add(3);
        System.out.println("现在的List：" + array);
        array.remove(1);
        System.out.println("删除下标1的元素：" + array);
        array.set(0, 666);
        System.out.println("修改元素：" + array);
    }

结果：

现在的List：[1, 2, 3]
删除下标1的元素：[1, 3]
修改元素：[666, 3]

Process finished with exit code 0

⛅怎样遍历List？

1. 同数组一样使用索引遍历：

   for (int i = 0; i < array.size(); i++) {
           int temp = array.get(i);
           ...
       }
   

2. 使用for-each增强型for循环遍历：

   for (Integer integer : array) {
           int temp = integer;
           ...
       }
   

3. 使用迭代器遍历：

   可以把iterator当作一个指针，初始时指向位置-1，hasNext()判断指针指向的下一个位置是否还有元素，next()将指针向后移动，并返回对应的元素。

   Iterator<Integer> iterator = array.iterator();
       while (iterator.hasNext()) {
           int temp = iterator.next();
           ...
       }
   

🍏2.Set

📖Set集合也可以当作数组来用，不过Set集合中不允许存储重复的元素，因此经常使用Set集合去重。

📑Set接口下的两个最为重要的实现类分别是HashSet与TreeSet，HashSet按Hash算法来存储集合中的元素，因此具有很好的存取和查找性能。底层数据结构是哈希表；TreeSet底层是红黑树，TreeSet可以确保集合元素处于排序状态。

⭐需要注意的是：

1. HashSet并不具备自动排序的功能，但是有些时候放进HashSet中的元素也会有顺序，然而这只是一种巧合，如果放进去的元素很多，HashSet并不能保证其顺序。

2. TreeSet具备自动排序的功能，将Integer或者Double放进TreeSet会自动帮我们排序，但是如果我们想将对象放进TreeSet，必须要让对象的类继承Comparable接口，并重写compareTo方法，使其具备比较大小的能力，这样TreeSet才知道按什么顺序存储对象。

3. Set中放入对象时需要重写equals方法来定义如何判断两个元素是否相同，其实Set的知识点还是很多的，本文主要面向参加蓝桥杯的同学，所以也不用过于深究，这里只介绍Set的简单使用~

🌈常用方法：

基本上和List相同~

• 构造方法：

  HashSet<Double> set = new HashSet<>();
TreeSet<Double> set = new TreeSet<>();

  或者

  Set<Double> set = new TreeSet<>();
Set<Double> set = new HashSet<>();

• 添加元素：boolean add(E e)，boolean addAll(Collection extends E> c)

• 删除元素：boolean remove(Object o)

• 清空集合：void clear()

• 删除在指定集合中出现的所有元素（差集）：

  boolean removeAll(Collection> c)

• 返回集合长度：int size()

• 判断集合是否为空：boolean isEmpty()

• 判断集合是否包含某个元素或者另一个集合：

  boolean contains(Object o)

  boolean containsAll(Collection> c)

示例代码：🌼

public static void main(String[] args) {
        TreeSet<Double> set = new TreeSet<>();
        set.add(2.3);
        set.add(6.1);
        set.add(0.2);
        System.out.println(set);
    }

结果：

[0.2, 2.3, 6.1]

Process finished with exit code 0

⛅怎样遍历Set？

Set的遍历方式和List类似，不过Set存储的顺序和放入的顺序不同，不能使用索引访问。

1. 使用for-each循环：

   for (Double aDouble : set) {
           double temp = aDouble;
           ...
       }
   

2. 使用迭代器遍历：

   Iterator<Double> iterator = set.iterator();
       while (iterator.hasNext()) {
           double temp = iterator.next();
           ...
       }
   

🥥3.Map

📖List与Set中的元素都是单个存储的，而Map中的元素是成对存储的，每个元素由键与值两部分组成，通过键可以找对所对应的值。

📑Map接口中最常用的实现类是HashMap，存储数据采用的哈希表结构，元素的存取顺序不能保证一致。需要注意的是，Map中的集合不能包含重复的键，值可以重复；每个键只能对应一个值。

🌈常用方法：

• 构造方法：

  Map<String, Integer> map = new HashMap<>()

  由于Map中存储的是键值对key-value，所以泛型有两个，前一个是键，后一个是值，这里的key是String类型，value是Integer类型。

• 存放数据：map.put("张三", 36)

• 获取map长度：int len = map.size()

• 通过key获取value：int age = map.get("张三")

• 通过key删除指定的元素：map.remove("张三")

• 修改key所对应的value值：map.replace("张三", 26)

• 判断map中是否存在某个key或者value：

  boolean bool = map.containsKey("张三")
boolean bool = map.containsValue(26)

示例代码：🌼

public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("张三", 36);
        map.put("李四", 33);
        map.replace("张三", 37);
        System.out.println(map);
    }

结果：

{李四=33, 张三=37}

Process finished with exit code 0

⛅怎样遍历Map？

1. 使用for-each遍历所有的key或者value：

   //        遍历map中的键
       for (String str : map.keySet()) {
           System.out.println(str);
       }
       
   //        遍历map中的值
       for (Integer age : map.values()) {
           System.out.println(age);
       }
   

2. 使用entrySet遍历，在键和值都需要时使用

   for (Map.Entry<String, Integer> entry : map.entrySet()) {
           System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
       }
   

3. java8提供了Lambda表达式支持，语法看起来更简洁，可以同时拿到key和value (参加蓝桥杯时要注意评测平台的JDK版本要高于1.8才能用)

   map.forEach((key, value) -> {
           System.out.println(key + " " + value);
       });
   

---

🍺实战演练：

这里准备了两道蓝桥杯的练习题，集合运算与字串统计，以供练习~

👉🏻集合运算：

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

输入两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。交集、并集和余集的计算都要求写成一个单独的函数。
　　输入第一行为一个正整数n，表示集合A中的元素个数；第二行有n个按从小到大的顺序输入且互不相同的整数，表示集合A中的元素；第三行为一个正整数m，表示集合B中的元素个数；第四行有m个按从小到大的顺序输入且互不相同的整数，表示集合B中的元素；集合中的所有元素均为int范围内的整数，1≤n,m≤1000。
　　输出第一行按从小到大的顺序输出A、B交集中的所有元素；第二行按从小到大的顺序输出A、B并集中的所有元素；第三行按从小到大的顺序输出B在A中的余集中的所有元素。

样例输入

5
1 2 3 4 5
5
2 4 6 8 10

样例输出

2 4
1 2 3 4 5 6 8 10
1 3 5

👩🏻‍🏫题目让我们分别求集合的交并余，而且输出要有序，所以使用TreeSet；交集可以先遍历其中一个集合，然后判断元素是否在另一个集合中出现，出现则添加至答案；并集直接将两个集合都加入答案即可；余集可以先将A集合全部放入答案，然后遍历B集合，如果元素在A集合中出现则将答案中对于的元素删除。

🍦AC代码（Java）：

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {

    static Set<Integer> setA = new TreeSet<>();
    static Set<Integer> setB = new TreeSet<>();

    public static Set<Integer> getIntersection(Set<Integer> setA, Set<Integer> setB) {
        Set<Integer> res = new TreeSet<>();
        for (Integer integer : setA) {
            if (setB.contains(integer))
                res.add(integer);
        }
        return res;
    }

    public static Set<Integer> getUnion(Set<Integer> setA, Set<Integer> setB) {
        Set<Integer> res = new TreeSet<>();
        res.addAll(setA);
        res.addAll(setB);
        return res;
    }

    public static Set<Integer> getDifference(Set<Integer> setA, Set<Integer> setB) {
        Set<Integer> res = new TreeSet<>(setA);
        for (Integer integer : setB) {
            res.remove(integer);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int temp = sc.nextInt();
            setA.add(temp);
        }
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int temp = sc.nextInt();
            setB.add(temp);
        }
        Set<Integer> intersection = getIntersection(setA, setB);
        for (Integer integer : intersection) {
            System.out.print(integer + " ");
        }
        System.out.println("");
        Set<Integer> union = getUnion(setA, setB);
        for (Integer integer : union) {
            System.out.print(integer + " ");
        }
        System.out.println("");
        Set<Integer> difference = getDifference(setA, setB);
        for (Integer integer : difference) {
            System.out.print(integer + " ");
        }
    }
}

👉🏻字串统计：

问题描述

给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。

输入格式

第一行一个数字L。
　　第二行是字符串S。
　　L大于0，且不超过S的长度。

输出格式

一行，题目要求的字符串。

输入样例1：
　　4
　　bbaabbaaaaa

输出样例1：
　　bbaa

输入样例2：
　　2
　　bbaabbaaaaa

输出样例2：
　　aa

数据规模和约定

n<=60
　　S中所有字符都是小写英文字母。

提示

枚举所有可能的子串，统计出现次数，找出符合条件的那个

👩🏻‍🏫根据提示让我们枚举所有可能，那么不妨使用Map存储每个子串出现的次数，key是子串，value是出现次数，然后不断截取子串统计次数，再加个打擂比较就可以了。

🍦AC代码（Java）：

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        String str = sc.next();
        Map<String, Integer> map = new HashMap<>();
        //	答案默认为str，防止所有子串都出现一次的情况
        String res = str;
        int max = 0;
        for (int i = len; i <= str.length(); i++) {
            for (int j = 0; j <= str.length() - i; j++) {
                String subStr = str.substring(j, j + i);
                if (map.containsKey(subStr)) {
                    int count = map.get(subStr);
                    count++;
                    map.replace(subStr, count);
                    //	多个子串出现次数相同，选出现早的，还有相同选最长的
                    if (count > max) {
                        max = count;
                        res = subStr;
                    } else if (count == max) {
                        res = res.length() >= subStr.length() ? res : subStr;
                    }
                } else {
                    map.put(subStr, 1);
                }
            }
        }
        System.out.println(res);
    }
}

---

🍌🍌🍌
以上就是List，Set与Map的全部内容了，这些都是参加蓝桥杯的必备技能，或者说是学习Java的基石；需要在平时多加练习，多使用Java集合代替数组。祝参加蓝桥杯的Java选手们取得好成绩~
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。🙇🏻‍♀️
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲菜狗一枚，请大佬们多多关照~