前言:

这是我关于蓝桥杯系列的第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下面有两个实现类最为常用:ArrayListLinkedList。其中ArrayList的底层是Object[]数组,优势在于可以随机访问,而LinkedList的底层是链表,访问某个元素的效率比ArrayList低,但优势在于需要大量增删改的时候速度很快。

常用方法:
  • 构造方法:

    ArrayList array = new ArrayList();
    LinkedList array = new LinkedList();

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

    List array = new ArrayList();
    List array = new LinkedList();

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

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

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

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

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

    boolean addAll(Collection

    2.Set

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

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

    ⭐需要注意的是:

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

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

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

    常用方法:

    基本上和List相同~

    • 构造方法:

      HashSet set = new HashSet();
      TreeSet set = new TreeSet();

      或者

      Set set = new TreeSet();
      Set 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 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() " />


    以上就是List,Set与Map的全部内容了,这些都是参加蓝桥杯的必备技能,或者说是学习Java的基石;需要在平时多加练习,多使用Java集合代替数组。祝参加蓝桥杯的Java选手们取得好成绩~

    创作不易,如果觉得本文对你有所帮助的话请动动小手,给博主点个免费的赞吧。‍♀️

    @作者:Mymel_晗,计科专业大学牲菜狗一枚,请大佬们多多关照~