Java集合框架简介

背景：软件学院《面向对象程序设计》期末考试有两道“机测”题，这里的考查重点不在于动态规划或复杂图论（不然算法课考什么），而在于对 Java 基础语法、IO 输入输出以及集合框架（Java Collections Framework） 的熟练应用。

这一篇文章不涉及面向对象设计，可以单纯地当作java语法入门。简介常用的 List、Set、Map，以及处理大数 (BigInteger) 和字符串 (String) 的一些技巧。掌握了这些，在之后的学习过程中可以更专注于“业务逻辑” (比如说设计管理系统) ，而不是在底层数据结构上“重复造轮子”。

0. 输入输出 / 程序基本结构

import java.util.*;public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        // ...        sc.close();    }}

编程提示：

如果输入的第一行是一个单独的整数，用 Integer.parseInt(sc.nextLine()) 能避免处理行末尾换行符（相较于 sc.nextInt() ）

int n = Integer.parseInt(sc.nextLine());for(int i = 0; i < n; i++) //...

1. java.math.BigInteger

例题：

洛谷P1591
https://www.luogu.com.cn/problem/P1591

求 n! 中某个数码 a 出现的个数

输入格式：第一行为t, 表示数据组数。接下来 t 行，每行输入一个 n 和 a。对于每组数据，输出一个整数，表示 n! 中 a 出现的次数。

import java.math.BigInteger;import java.util.Scanner;class Main{    public static void main(String[] args){        Scanner sc = new Scanner(System.in);        int t = Integer.parseInt(sc.nextLine());        for(int i = 0; i < t; i++){            String[] param = sc.nextLine().split(" +");            int n = Integer.parseInt(param[0]);            BigInteger res = new BigInteger("1");            for(int j = 1; j <= n; j++){                res = res.multiply(BigInteger.valueOf(j));            }            String temp = res.toString();            int cnt = 0;            for(int j = 0; j < temp.length(); j++){                if(temp.charAt(j) == param[1].charAt(0)){                    cnt++;                }            }            System.out.println(cnt);        }        sc.close();    }}

2. List

Collections.sort 的 lambda 表达式

例题：

洛谷P1104
https://www.luogu.com.cn/problem/P1104

第一行输入 n 表示人数，接下来 n 行输入人员信息(姓名 出生年月日)，输出按特定规则排序后人员姓名。

import java.util.ArrayList;import java.util.List;import java.util.Scanner;import java.util.Collections;class Student{    int id;    String name;    int yyyy,mm,dd;    Student(int id, String name,String y, String m, String d){        this.id = id;        this.name = name;        this.yyyy = Integer.parseInt(y);        this.mm = Integer.parseInt(m);        this.dd = Integer.parseInt(d);    }    @Override    public String toString() {        return name;    }}public class Main {    public static void main(String[] args){        Scanner sc = new Scanner(System.in);        int n = Integer.parseInt(sc.nextLine());        List<Student> myList = new ArrayList<>();        for(int i = 1; i <= n; i++){            String[] param = sc.nextLine().split(" +");            myList.add(new Student(i, param[0], param[1], param[2], param[3]));        }        Collections.sort(myList, (s1,s2) -> {            if(s1.yyyy != s2.yyyy){                return s1.yyyy - s2.yyyy;            }            else if(s1.mm != s2.mm){                return s1.mm - s2.mm;            }            else if(s1.dd != s2.dd){                return s1.dd - s2.dd;            }            else{                return s2.id - s1.id;            }        });        for(int i = 0; i < n; i++){            System.out.println(myList.get(i));        }        sc.close();    }}

二维数组

二维数组可以直接像 cpp 的 vector<vector<int>> 一样声明

例题：

Leetcode 118 杨辉三角
https://leetcode.cn/problems/pascals-triangle

传入 int numRows 传出二维数组“杨辉三角”

import java.util.ArrayList;import java.util.List;class Solution {    public List<List<Integer>> generate(int numRows) {        List<List<Integer>> ans = new ArrayList<>();        for(int i = 0; i < numRows; i++){            List<Integer> row = new ArrayList<>();            for(int j = 0; j <= i; j++){                if(j == 0 || j == i){                    row.add(1);                }else{                    List<Integer> preRow = ans.get(i - 1);                    int num = preRow.get(j) + preRow.get(j - 1);                    row.add(num);                }            }            ans.add(row);        }        return ans;    }}

3. Set

最基本使用

例题：

洛谷P1059
https://www.luogu.com.cn/problem/P1059

输入 n 和一个长度为 n 的数组，输出去重后的数组的元素个数以及排序后的数组。

import java.util.*;class Main{    public static void main(String args[]){        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        Set<Integer> mySet = new HashSet<>();        for(int i = 0; i < n; i++){            mySet.add(sc.nextInt());        }        System.out.println(mySet.size());        List<Integer> arr = new ArrayList(mySet);        Collections.sort(arr);        for(int i = 0; i < arr.size(); i++){            System.out.print(arr.get(i) + " ");        }        sc.close();    }}

用 TreeSet 可以自动排序

Set<Integer> mySet = new TreeSet<>();// 输入逻辑略...List<Integer> arr = new ArrayList(mySet);for(int i = 0; i < arr.size(); i++){    System.out.print(arr.get(i) + " ");}

集合的 交、并、差 运算

import java.util.*;public class Main {    public static void main(String[] args) {        // A 班名单        Set<String> classA = new HashSet<>(Arrays.asList("Alice", "Bob", "Charlie", "David"));        // B 班名单        Set<String> classB = new HashSet<>(Arrays.asList("Charlie", "David", "Eve", "Frank"));        // 1. 求并集：两个班总共有哪些学生？        Set<String> union = new HashSet<>(classA); // 创建副本，保护原数据        union.addAll(classB);        System.out.println("并集: " + union);         // [Alice, Bob, Charlie, David, Eve, Frank]        // 2. 求交集：同时报了两个班的学生是谁？        Set<String> intersection = new HashSet<>(classA);        intersection.retainAll(classB);        System.out.println("交集: " + intersection);         // [Charlie, David]        // 3. 求差集：只报了 A 班、没报 B 班的是谁？        Set<String> difference = new HashSet<>(classA);        difference.removeAll(classB);        System.out.println("只在 A 班的: " + difference);         // [Alice, Bob]        // 4. 判断包含关系        boolean isSubset = classA.containsAll(Arrays.asList("Alice", "Bob"));        System.out.println("Alice 和 Bob 都在 A 班吗？ " + isSubset); // true    }}

4. Map

简单管理系统

例题：

洛谷P5266
https://www.luogu.com.cn/problem/P5266

一个简单的教务管理系统，Map<姓名, 成绩>，不同的op对应不同操作

输入格式是 op [name] [grade]

import java.util.*;public class Main{    public static void main(String[] args){        Scanner sc = new Scanner(System.in);        int n = Integer.parseInt(sc.nextLine());        Map<String, Integer> myMap = new HashMap<>();        for(int i = 0; i < n; i++){            String[] param = sc.nextLine().split(" +");            String op = param[0];            switch (op) {                case "1":                    myMap.put(param[1], Integer.parseInt(param[2]));                    System.out.println("OK");                    break;                case "2":                    if(myMap.containsKey(param[1])){                        System.out.println(myMap.get(param[1]));                    }else{                        System.out.println("Not found");                    }                    break;                case "3":                    if(myMap.containsKey(param[1])){                        myMap.remove(param[1]);                        System.out.println("Deleted successfully");                    }else{                        System.out.println("Not found");                    }                    break;                case "4":                    System.out.println(myMap.size());            }        }        sc.close();    }}

计数问题

注意 myMap.getOrDefault(key, 0) + 1) 的用法

例题：计数哈希表

Leetcode 451
https://leetcode.cn/problems/sort-characters-by-frequency

传入一个字符串 s 传出一个字符串
规则：按字母频数降序排列

例：

输入: s = "tree"输出: "eert"解释: 'e'出现两次，'r'和't'都只出现一次。因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

public String frequencySort(String s) {    Map<Character, Integer> myMap = new HashMap<>();    for(int i = 0; i < s.length(); i++){        myMap.put(s.charAt(i), myMap.getOrDefault(s.charAt(i), 0) + 1);    }    List<Character> myList = new ArrayList<>(myMap.keySet());    Collections.sort(myList, (a,b) -> myMap.get(b) - myMap.get(a));    StringBuilder sb = new StringBuilder();    for(char c : myList){        int count = myMap.get(c);        for(int i = 0; i < count; i++){            sb.append(c);        }    }    return sb.toString();} 

5. 杂项

诸如此类：
Collections.sort() Integer.MAX_VALUE myStr.split(" +") Math.min() StringBuilder

例题：

Leetcode 539 最小时间差
https://leetcode.cn/problems/minimum-time-difference

传入一个字符串数组，返回数组中任一两个时间的最小时间差，返回相差的分钟数。

例：

输入：timePoints = ["23:59","00:00"]输出：1

public int findMinDifference(List<String> timePoints) {    List<Integer> mins = new ArrayList<>();    for(String time: timePoints){        String[] parts = time.split(":");        int h = Integer.parseInt(parts[0]);        int m = Integer.parseInt(parts[1]);        mins.add(h * 60 + m);    }    Collections.sort(mins);    int minDiff = Integer.MAX_VALUE;    for(int i = 1; i < mins.size(); i++){        minDiff = Math.min(minDiff, mins.get(i) - mins.get(i - 1));    }    // 特殊处理跨天    minDiff = Math.min(1440 + mins.get(0) - mins.get(mins.size() - 1), minDiff);    return minDiff;}

StringBuilder 简单使用：

例题：

Leetcode 151
https://leetcode.cn/problems/reverse-words-in-a-string/

反转句子 s 中的所有单词

例：

输入：s = " the   sky  is blue   "输出："blue is sky the"

public String reverseWords(String s) {    StringBuilder sb = new StringBuilder();    s = s.trim();    String[] words = s.split(" +");    for(int i = words.length - 1; i >= 0; i--){        sb.append(words[i]);        if(i != 0){            sb.append(" ");        }    }    return sb.toString();}

一个栈的例题，传入一个只含三种括号 () [] {} 字符串，判断是否匹配

注意下 ArrayDeque myStack.peek() 这种东西

public boolean isValid(String s) {    Deque<Character> myStack = new ArrayDeque<>();    for(char c: s.toCharArray()){        if(c == '{' || c == '[' || c == '('){            myStack.push(c);        }else if(c == '}' || c == ']' || c == ')'){            if(myStack.isEmpty()) return false;            char temp = myStack.peek();            if((temp == '(' && c == ')') ||                 (temp == '[' && c == ']') ||                 (temp == '{' && c == '}')) {                    myStack.pop();                }            else return false;        }    }    return myStack.isEmpty();}