Java集合框架简介
背景：软件学院《面向对象程序设计》期末考试有两道“机测”题，这里的考查重点不在于动态规划或复杂图论（不然算法课考什么），而在于对 Java 基础语法、IO 输入输出以及集合框架（Java Collections Framework） 的熟练应用。
这一篇文章不涉及面向对象设计，可以单纯地当作java语法入门。简介常用的 List、Set、Map，以及处理大数 (BigInteger) 和字符串 (String) 的一些技巧。掌握了这些，在之后的学习过程中可以更专注于“业务逻辑” (比如说设计管理系统) ，而不是在底层数据结构上“重复造轮子”。
0. 输入输出 / 程序基本结构
import java.util.*;
publicclassMain {
publicstaticvoidmain(String[] args) {
Scannersc=newScanner(System.in);
// ...
sc.close();
}
}
编程提示：
如果输入的第一行是一个单独的整数，用 Integer.parseInt(sc.nextLine()) 能避免处理行末尾换行符（相较于 sc.nextInt() ）
intn= Integer.parseInt(sc.nextLine());
for(inti=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;
classMain{
publicstaticvoidmain(String[] args){
Scannersc=newScanner(System.in);
intt= Integer.parseInt(sc.nextLine());
for(inti=0; i < t; i++){
String[] param = sc.nextLine().split(" +");
intn= Integer.parseInt(param[0]);
BigIntegerres=newBigInteger("1");
for(intj=1; j <= n; j++){
res = res.multiply(BigInteger.valueOf(j));
}
Stringtemp= res.toString();
intcnt=0;
for(intj=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;
classStudent{
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;
}
}
publicclassMain {
publicstaticvoidmain(String[] args){
Scannersc=newScanner(System.in);
intn= Integer.parseInt(sc.nextLine());
List<Student> myList = newArrayList<>();
for(inti=1; i <= n; i++){
String[] param = sc.nextLine().split(" +");
myList.add(newStudent(i, param[0], param[1], param[2], param[3]));
}
Collections.sort(myList, (s1,s2) -> {
if(s1.yyyy != s2.yyyy){
return s1.yyyy - s2.yyyy;
}
elseif(s1.mm != s2.mm){
return s1.mm - s2.mm;
}
elseif(s1.dd != s2.dd){
return s1.dd - s2.dd;
}
else{
return s2.id - s1.id;
}
});
for(inti=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;
classSolution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = newArrayList<>();
for(inti=0; i < numRows; i++){
List<Integer> row = newArrayList<>();
for(intj=0; j <= i; j++){
if(j == 0 || j == i){
row.add(1);
}else{
List<Integer> preRow = ans.get(i - 1);
intnum= 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.*;
classMain{
publicstaticvoidmain(String args[]){
Scannersc=newScanner(System.in);
intn= sc.nextInt();
Set<Integer> mySet = newHashSet<>();
for(inti=0; i < n; i++){
mySet.add(sc.nextInt());
}
System.out.println(mySet.size());
List<Integer> arr = newArrayList(mySet);
Collections.sort(arr);
for(inti=0; i < arr.size(); i++){
System.out.print(arr.get(i) + " ");
}
sc.close();
}
}
用 TreeSet 可以自动排序
Set<Integer> mySet = newTreeSet<>();
// 输入逻辑略...
List<Integer> arr = newArrayList(mySet);
for(inti=0; i < arr.size(); i++){
System.out.print(arr.get(i) + " ");
}
集合的 交、并、差 运算
import java.util.*;
publicclassMain {
publicstaticvoidmain(String[] args) {
// A 班名单
Set<String> classA = newHashSet<>(Arrays.asList("Alice", "Bob", "Charlie", "David"));
// B 班名单
Set<String> classB = newHashSet<>(Arrays.asList("Charlie", "David", "Eve", "Frank"));
// 1. 求并集：两个班总共有哪些学生？
Set<String> union = newHashSet<>(classA); // 创建副本，保护原数据
union.addAll(classB);
System.out.println("并集: " + union);
// [Alice, Bob, Charlie, David, Eve, Frank]
// 2. 求交集：同时报了两个班的学生是谁？
Set<String> intersection = newHashSet<>(classA);
intersection.retainAll(classB);
System.out.println("交集: " + intersection);
// [Charlie, David]
// 3. 求差集：只报了 A 班、没报 B 班的是谁？
Set<String> difference = newHashSet<>(classA);
difference.removeAll(classB);
System.out.println("只在 A 班的: " + difference);
// [Alice, Bob]
// 4. 判断包含关系
booleanisSubset= 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.*;
publicclassMain{
publicstaticvoidmain(String[] args){
Scannersc=newScanner(System.in);
intn= Integer.parseInt(sc.nextLine());
Map<String, Integer> myMap = newHashMap<>();
for(inti=0; i < n; i++){
String[] param = sc.nextLine().split(" +");
Stringop= 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 = newHashMap<>();
for(inti=0; i < s.length(); i++){
myMap.put(s.charAt(i), myMap.getOrDefault(s.charAt(i), 0) + 1);
}
List<Character> myList = newArrayList<>(myMap.keySet());
Collections.sort(myList, (a,b) -> myMap.get(b) - myMap.get(a));
StringBuildersb=newStringBuilder();
for(char c : myList){
intcount= myMap.get(c);
for(inti=0; i < count; i++){
sb.append(c);
}
}
return sb.toString();
}
5. 杂项
诸如此类：
Collections.sort()Integer.MAX_VALUEmyStr.split(" +")Math.min()StringBuilder
例题：
Leetcode 539 最小时间差
https://leetcode.cn/problems/minimum-time-difference
传入一个字符串数组，返回数组中任一两个时间的最小时间差，返回相差的分钟数。
例：
输入：timePoints = ["23:59","00:00"]
输出：1
publicintfindMinDifference(List<String> timePoints) {
List<Integer> mins = newArrayList<>();
for(String time: timePoints){
String[] parts = time.split(":");
inth= Integer.parseInt(parts[0]);
intm= Integer.parseInt(parts[1]);
mins.add(h * 60 + m);
}
Collections.sort(mins);
intminDiff= Integer.MAX_VALUE;
for(inti=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) {
StringBuildersb=newStringBuilder();
s = s.trim();
String[] words = s.split(" +");
for(inti= words.length - 1; i >= 0; i--){
sb.append(words[i]);
if(i != 0){
sb.append(" ");
}
}
return sb.toString();
}
一个栈的例题，传入一个只含三种括号 ()[]{} 字符串，判断是否匹配
注意下 ArrayDequemyStack.peek() 这种东西
publicbooleanisValid(String s) {
Deque<Character> myStack = newArrayDeque<>();
for(char c: s.toCharArray()){
if(c == '{' || c == '[' || c == '('){
myStack.push(c);
}elseif(c == '}' || c == ']' || c == ')'){
if(myStack.isEmpty()) returnfalse;
chartemp= myStack.peek();
if((temp == '(' && c == ')') ||
(temp == '[' && c == ']') ||
(temp == '{' && c == '}')) {
myStack.pop();
}
elsereturnfalse;
}
}
return myStack.isEmpty();
}
