以下是Java 常用 API 的系統性總結，特別適用于算法競賽（如 CCF CSP、藍橋杯、NOI）場景。按照功能分類，并給出代表性方法及簡要用法說明，方便復習與帶入考場：
? Java 常用 API 分類總結（算法競賽篇）
常見數據類型的數據范圍與默認值
當然可以！以下是 Java 中常見數據類型的數據范圍與默認值總結，適合你背誦、練習和面試使用：
? 一、Java 基本數據類型總結（8種）
| 類型 | 占用空間 | 范圍（含正負） | 默認值 |
|---|---|---|---|
byte | 1 字節 | -128 ~ 127 | 0 |
short | 2 字節 | -32,768 ~ 32,767 | 0 |
int | 4 字節 | -231 ~ 231-1（-2,147,483,648 ~ 2,147,483,647） | 0 |
long | 8 字節 | -2?3 ~ 2?3-1（約 ±9 × 101?） | 0L |
float | 4 字節 | 約 ±3.4 × 103?（7位有效數字） | 0.0f |
double | 8 字節 | 約 ±1.8 × 103??（15位有效數字） | 0.0d |
char | 2 字節 | 0 ~ 65535（Unicode 字符） | '\u0000' |
boolean | 1 位（JVM 按 1 字節處理） | true / false | false |
? 二、常用封裝類與常量（用于邊界判斷）
| 類型 | 最大值 | 最小值 | 示例 |
|---|---|---|---|
Integer | Integer.MAX_VALUE = 2147483647 | Integer.MIN_VALUE = -2147483648 | int a = Integer.MAX_VALUE; |
Long | Long.MAX_VALUE = 9223372036854775807L | Long.MIN_VALUE = -9223372036854775808L | |
Double | Double.MAX_VALUE ≈ 1.79769e+308 | Double.MIN_VALUE ≈ 4.9e-324（最小正數） | 注意 Double.MIN_VALUE 是正數 |
Float | Float.MAX_VALUE ≈ 3.40282e+38 | Float.MIN_VALUE ≈ 1.4e-45 | 同上 |
Character | Character.MAX_VALUE = 65535 ('\uffff') | Character.MIN_VALUE = 0 ('\u0000') |
? 三、如何選擇數據類型？（實用建議）
| 場景 | 推薦類型 | 原因 |
|---|---|---|
| 統計、計數 | int / long | 小數據用 int，大數據（>10?）用 long |
| 精確小數運算 | BigDecimal | 如貨幣計算，避免精度丟失 |
| 浮點計算 | double | 精度高于 float |
| 布爾開關 | boolean | 性能優，語義清晰 |
| 單個字符 | char | 適合處理字符型數據 |
? 四、經典面試題：Integer.MIN_VALUE 的絕對值是多少？
System.out.println(Math.abs(Integer.MIN_VALUE)); // 輸出仍為 -2147483648
這是因為 abs() 溢出！因為 -2147483648 沒有正數對應（超出 int 正范圍）。
? 五、背誦口訣助記法：
byte 短 short 剛好 32k，
int 四字節到 21億。
long 八字節超千萬億，
float double 飄到天際。
char 是 Unicode，boolean 真或假。
1?? 字符串處理（String 類）
| 方法 | 用途 | 示例 |
|---|---|---|
length() | 獲取字符串長度 | "abc".length() -> 3 |
charAt(i) | 獲取索引 i 處字符 | "abc".charAt(1) -> 'b' |
substring(start, end) | 截取子串（左閉右開） | "abcdef".substring(1,4) -> "bcd" |
indexOf(str) | 第一次出現位置 | "ababc".indexOf("ab") -> 0 |
lastIndexOf(str) | 最后一次出現位置 | "ababc".lastIndexOf("ab") -> 2 |
contains(str) | 是否包含 | "abc".contains("b") -> true |
split(regex) | 按正則分割為數組 | "a,b,c".split(",") -> [a, b, c] |
equals(str) | 是否相等 | "abc".equals("abc") -> true |
compareTo(str) | 字典序比較 | "abc".compareTo("abd") -> -1 |
toCharArray() | 轉為字符數組 | "abc" -> ['a','b','c'] |
replace(old, new) | 替換子串 | "aabb".replace("a", "c") -> "ccbb" |
trim() | 去除首尾空格 | " a b ".trim() -> "a b" |
toLowerCase() | 轉小寫 | "ABC".toLowerCase() -> "abc" |
toUpperCase() | 轉大寫 | "abc".toUpperCase() -> "ABC" |
startsWith(str) | 以某串開頭 | "abc".startsWith("a") -> true |
endsWith(str) | 以某串結尾 | "abc".endsWith("c") -> true |
2?? 高效字符串拼接（StringBuilder / StringBuffer）
| 方法 | 用途 |
|---|---|
append(str) | 添加字符串 |
insert(pos, str) | 插入字符串 |
delete(start, end) | 刪除子串 |
reverse() | 翻轉字符串 |
toString() | 轉回字符串 |
??
StringBuilder非線程安全，StringBuffer線程安全（但慢）。
3?? 數學計算（Math 類）
| 方法 | 說明 |
|---|---|
abs(x) | 絕對值 |
max(a, b) / min(a, b) | 最大 / 最小值 |
pow(a, b) | a 的 b 次冪 |
sqrt(x) | 平方根 |
cbrt(x) | 立方根 |
ceil(x) | 向上取整 |
floor(x) | 向下取整 |
round(x) | 四舍五入（返回 long） |
random() | 返回 [0,1) 間隨機數 |
log(x) / log10(x) | 自然對數 / 常用對數 |
sin(x), cos(x), tan(x) | 三角函數（弧度） |
4?? 數組處理（Arrays 工具類）
| 方法 | 說明 |
|---|---|
sort(array) | 升序排序 |
binarySearch(array, key) | 二分查找（有序數組） |
fill(array, val) | 全部填充為 val |
copyOf(arr, newLen) | 拷貝前 newLen 個元素 |
equals(a, b) | 比較兩個數組是否完全相等 |
toString(arr) | 數組轉字符串 |
asList(T... arr) | 數組轉固定長度 List |
5?? 集合框架
List（ArrayList / LinkedList）
| 方法 | 說明 |
|---|---|
add(e) | 添加元素 |
remove(i) | 刪除索引 i 元素 |
get(i) | 獲取元素 |
set(i, e) | 修改元素 |
size() | 獲取大小 |
contains(e) | 是否包含元素 |
Set（HashSet / TreeSet）
| 方法 | 說明 |
|---|---|
add(e) | 添加元素 |
remove(e) | 移除元素 |
contains(e) | 是否存在 |
size() | 元素個數 |
first() / last() | TreeSet 中的最小 / 最大值 |
ceiling(e) | ≥e 的最小值 |
floor(e) | ≤e 的最大值 |
? 一、常見 Set 實現類對比
| 類名 | 是否有序 | 是否允許 null | 是否線程安全 | 底層結構 |
|---|---|---|---|---|
HashSet | ? 無序 | ? 允許一個 | ? 不安全 | 哈希表 |
LinkedHashSet | ? 插入順序 | ? 允許一個 | ? 不安全 | 哈希表 + 雙向鏈表 |
TreeSet | ? 升序 | ? 不允許 | ? 不安全 | 紅黑樹（平衡二叉樹） |
? 二、常用 Set API 匯總
| 功能 | 示例代碼 | 說明 |
|---|---|---|
| 初始化 | Set<Integer> set = new HashSet<>(); | 常用 HashSet |
| 添加元素 | set.add(x); | 添加元素（若重復則不變） |
| 刪除元素 | set.remove(x); | 刪除元素（若無也不報錯） |
| 是否包含 | set.contains(x); | 判斷元素是否存在 |
| 獲取大小 | set.size(); | 元素個數 |
| 清空集合 | set.clear(); | 清空所有元素 |
| 是否為空 | set.isEmpty(); | 是否為空 |
| 遍歷元素 | for (int x : set) | 常用 for-each 遍歷 |
| 轉為 List | new ArrayList<>(set); | 若需排序或索引操作 |
| 集合并集（新增） | set.addAll(otherSet); | 將另一個集合元素加入本集合 |
| 集合交集（保留） | set.retainAll(otherSet); | 只保留兩集合都存在的元素 |
| 集合差集（去除） | set.removeAll(otherSet); | 去除在 otherSet 中也有的元素 |
? 三、典型代碼模板
📌 1. 初始化 + 去重存儲
Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(2); // 無效重復
System.out.println(set); // 輸出 [1, 2]
📌 2. 遍歷 + 判斷是否存在
for (int x : set) {if (x == 3) System.out.println("存在");
}
📌 3. 使用 TreeSet 實現自動排序
Set<String> treeSet = new TreeSet<>();
treeSet.add("banana");
treeSet.add("apple");
System.out.println(treeSet); // [apple, banana]
? 四、適配題型速查
| 題型類別 | 用法建議 | 舉例題目 |
|---|---|---|
| 去重統計 | 用 HashSet 存入后 size() | [CSP] 數字種類、集合大小 |
| 判斷是否重復 | set.contains(x) + set.add(x) | 力扣 217、219 |
| 保持順序去重 | 用 LinkedHashSet | 輸出按插入順序的唯一值序列 |
| 需要有序輸出 | 用 TreeSet + 自動排序 | 力扣 349、350（交集類） |
? 五、背誦口訣：“增刪查，去重快，TreeSet 排序不帶蓋！”
? 六、你可以練習的題目（推薦）
| 平臺 | 題目 ID / 名稱 | 涉及 API |
|---|---|---|
| 力扣 | 217. 存在重復元素 | set.contains() |
| 力扣 | 349. 兩個數組的交集 | set.retainAll() |
| 力扣 | 705. 設計哈希集合 | 手寫 Set 底層結構 |
| CSP | 出現過的數、不同的數種類統計 | set.add() + set.size() |
Map（HashMap / TreeMap）
| 方法 | 說明 |
|---|---|
put(key, val) | 添加鍵值對 |
get(key) | 獲取值（無則返回 null） |
getOrDefault(key, def) | 若無該 key，返回默認值 |
containsKey(key) | 是否包含鍵 |
keySet() | 所有 key 集合 |
values() | 所有 value |
entrySet() | 所有 entry（用于遍歷） |
頻次統計（CSP常見）
map.put(x, map.getOrDefault(x, 0) + 1);
6?? Collections 工具類（操作集合）
| 方法 | 說明 |
|---|---|
sort(list) | 升序排序 |
reverse(list) | 反轉列表 |
shuffle(list) | 隨機打亂 |
frequency(list, obj) | 統計出現次數 |
swap(list, i, j) | 交換元素 |
rotate(list, k) | 向右旋轉 k 位 |
max(list) / min(list) | 最大 / 最小值 |
7?? 優先隊列（PriorityQueue）
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 默認小根堆
pq.offer(3); pq.offer(1); pq.offer(2);
pq.peek(); // 1
pq.poll(); // 彈出最小的 1
自定義大根堆：
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
8?? 位運算（Integer 類）
| 方法 | 說明 |
|---|---|
bitCount(i) | 二進制中 1 的個數 |
highestOneBit(i) | 最高位的 1 的值（如 1000） |
lowestOneBit(i) | 最低位的 1 的值（如 0001） |
toBinaryString(i) | 二進制表示 |
parseInt(s, radix) | 任意進制轉十進制 |
toHexString(i) | 十六進制表示 |
9?? 大數處理
BigInteger
| 方法 | 說明 |
|---|---|
add() / subtract() / multiply() / divide() | 四則運算 |
mod() | 取模 |
pow(n) | 冪 |
compareTo(BigInteger) | 比較大小 |
gcd() | 最大公約數 |
isProbablePrime(certainty) | 判斷素數（概率） |
BigInteger a = new BigInteger("123456789");
BigInteger b = new BigInteger("987654321");
a.add(b).toString(); // 字符串輸出
BigDecimal
| 方法 | 說明 |
|---|---|
add(), subtract(), multiply(), divide() | 高精度小數運算 |
setScale(n, RoundingMode) | 設置小數位數 |
compareTo() | 比較大小 |
🔟 時間函數
| 方法 | 說明 |
|---|---|
System.currentTimeMillis() | 當前毫秒時間戳 |
System.nanoTime() | 納秒時間戳（高精度測時） |
LocalDateTime.now() | 當前時間 |
ChronoUnit.SECONDS.between(start, end) | 時間間隔 |
🔟+1 正則表達式處理
| 類 | 方法 |
|---|---|
Pattern.compile(regex) | 編譯正則 |
matcher(str) | 創建匹配器 |
find() / group() | 匹配和提取子串 |
matches() | 整體匹配是否成功 |
🔟+2 輸入輸出（Scanner, BufferedReader, PrintWriter）
| 類 | 方法 |
|---|---|
Scanner | next(), nextLine(), nextInt() |
BufferedReader | 高效讀取（支持 readLine()） |
PrintWriter | 快速輸出，println()、flush() |
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String s = br.readLine();
out.println(s);
out.flush();
常考模塊
自定義排序
你提的問題非常好！作為初學者，理解 Arrays.sort() 和 Collections.sort() 的區別與適用場景，對于寫出更規范、穩定、靈活的排序代碼至關重要。以下是詳細解釋和通用解法整理👇
? 一、Arrays.sort() 和 Collections.sort() 有什么區別？
| 比較點 | Arrays.sort() | Collections.sort() |
|---|---|---|
| 適用對象 | 數組（如 int[]、String[]、Integer[]） | List（如 ArrayList、LinkedList） |
| 所在包 | java.util.Arrays | java.util.Collections |
| 排序方式 | 默認升序；支持傳入比較器 Comparator | 默認升序；也支持傳入比較器 Comparator |
| 是否穩定排序 | 對對象數組使用 TimSort（穩定） | 使用 List.sort()，底層同樣是 TimSort（穩定） |
| 是否可以混用 | ? 不可以直接混用 | ? List 和 Collections.sort() 是配套的 |
🚫 不可以這樣混用：
List<Integer> list = new ArrayList<>();
Arrays.sort(list); // ? 錯誤，Arrays.sort 不能用于 List
? 正確用法：
int[] arr = new int[]{5, 2, 3};
Arrays.sort(arr); // 用于基本類型數組List<Integer> list = new ArrayList<>(List.of(5, 2, 3));
Collections.sort(list); // 用于 List
? 二、二者的典型應用對比
🧩 排序數組 → 用 Arrays.sort()
int[] arr = {4, 2, 9};
Arrays.sort(arr); // 升序：[2, 4, 9]
🧩 排序對象數組 → 仍用 Arrays.sort()
Student[] stu = ...;
Arrays.sort(stu, (a, b) -> b.score - a.score); // 按成績降序
🧩 排序 List → 用 Collections.sort() 或 Java 8 的 list.sort()
List<String> list = new ArrayList<>(List.of("cat", "apple", "banana"));
Collections.sort(list); // 默認字典序
等價于 Java 8 寫法：
list.sort(String::compareTo); // 同樣是字典序
? 三、是否可以用 Collections.sort() 替代 Arrays.sort()？
🟡 不能直接替代！ 因為它們的參數類型不同！
Arrays.sort()適用于 數組（如int[],Integer[],String[]等）Collections.sort()適用于 List（如ArrayList,LinkedList）
但你可以將數組轉成 List 來使用 Collections.sort()（用于對象類型數組）：
? 數組轉 List 再排序（適用于對象數組）
Integer[] arr = {5, 2, 9};
List<Integer> list = Arrays.asList(arr);
Collections.sort(list); // 排序后 arr 也變化（共享內存）
?? 注意： Arrays.asList() 返回的是一個固定長度的列表，不能增刪元素，只能排序或修改已有元素。
? 四、初學者建議記憶總結
| 想排序什么？ | 用什么？ | 支持自定義比較器？ | 是否穩定？ |
|---|---|---|---|
| int[] / double[] | Arrays.sort() | ? | ? |
| Integer[] / 對象數組 | Arrays.sort(arr, cmp) | ? | ? |
| List（ArrayList） | Collections.sort() / list.sort() | ? | ? |
| Map | 轉為 entrySet() 的 List 后排序 | ? | ? |
? 五、通用排序封裝函數（建議記憶）
// 通用對象排序（List）
public static <T> void sortList(List<T> list, Comparator<T> cmp) {Collections.sort(list, cmp);
}// 通用數組排序（對象數組）
public static <T> void sortArray(T[] arr, Comparator<T> cmp) {Arrays.sort(arr, cmp);
}
在 Java 中進行“自定義排序”，常用于對數組、對象集合（如 List）等進行靈活的排序。CSP 考試中，常見場景包括：
- 對多個字段排序（如先按成績，再按學號）
- 自定義結構（如 Pair）排序
- 降序 / 升序控制
? 一、對數組進行自定義排序（基本類型）
import java.util.*;public class CustomSortArray {public static void main(String[] args) {Integer[] arr = {5, 2, 8, 1, 9};// 降序排序Arrays.sort(arr, (a, b) -> b - a);System.out.println(Arrays.toString(arr)); // [9, 8, 5, 2, 1]}
}
注意：
int[]不能直接使用 Lambda 表達式，必須使用Integer[]對象數組。
? 二、自定義結構排序（如 Pair）
import java.util.*;class Pair {int id, score;public Pair(int id, int score) {this.id = id;this.score = score;}@Overridepublic String toString() {return "(" + id + "," + score + ")";}
}public class CustomSortPair {public static void main(String[] args) {List<Pair> list = new ArrayList<>();list.add(new Pair(1, 90));list.add(new Pair(3, 80));list.add(new Pair(2, 90));// 排序規則：先按 score 降序，再按 id 升序Collections.sort(list, (a, b) -> {if (a.score != b.score) return b.score - a.score; // 降序return a.id - b.id; // 升序});for (Pair p : list) {System.out.println(p);}}
}
? 三、二維數組排序（常見于模擬/DP）
import java.util.*;public class CustomSort2DArray {public static void main(String[] args) {int[][] data = {{1, 90},{2, 100},{3, 90}};// 按第二列降序，再按第一列升序Arrays.sort(data, (a, b) -> {if (a[1] != b[1]) return b[1] - a[1];return a[0] - b[0];});for (int[] row : data) {System.out.println(Arrays.toString(row));}}
}
? 四、優先隊列中的自定義排序（堆）
import java.util.*;public class CustomPriorityQueue {public static void main(String[] args) {// 最小堆按第一維升序，第二維降序PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {if (a[0] != b[0]) return a[0] - b[0];return b[1] - a[1];});pq.offer(new int[]{2, 100});pq.offer(new int[]{1, 80});pq.offer(new int[]{2, 90});while (!pq.isEmpty()) {System.out.println(Arrays.toString(pq.poll()));}}
}
📌 總結：常用模板
// Arrays.sort + Lambda
Arrays.sort(array, (a, b) -> {// 優先級：先按某字段，再按其他字段return a[0] - b[0]; // 升序 / b[0] - a[0] 降序
});// List + Collections.sort
Collections.sort(list, (a, b) -> {if (a.score != b.score) return b.score - a.score;return a.id - b.id;
});// PriorityQueue + 自定義比較器
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
以下是為 CCF CSP 考試 精心整理的「常見排序題速查表」，包含常考題型、解題策略、排序維度、API 示例等，幫助你快速定位解題方案。
? 一、速查表概覽（按題型分類）
| 題型類別 | 排序關鍵 | 排序維度 | 示例題目 | 典型排序語句 |
|---|---|---|---|---|
| 成績/統計排序 | 值大小 | 降序或多字段 | 成績排序、熱度統計等 | Collections.sort(list, (a,b)->b.score-a.score) |
| 時間線排序 | 時間戳 | 升序 | 日志記錄、任務調度等 | Arrays.sort(arr, Comparator.comparingInt(a -> a.time)) |
| 坐標排序 | x/y軸 | 多字段（先 x 后 y） | 坐標掃描、區間合并等 | Arrays.sort(points, (a,b)->a[0]==b[0]?a[1]-b[1]:a[0]-b[0]) |
| 編號優先 | 編號 | 按編號升序 | 按原始輸入順序輸出 | Collections.sort(list, Comparator.comparingInt(a->a.id)) |
| 并查集/連通塊 | 集合大小 | 降序或升序 | 連通塊排序輸出 | 自定義結構 + 統計 + 排序 |
| 哈希計數 | 次數 | 降序 + 值本身升序 | 頻率統計、單詞計數等 | 統計完后 List<Map.Entry> 排序 |
? 二、各類型題型詳解與模板
1?? 成績類排序（權重/成績/頻次）
例題：
- 成績排行
- 詞頻統計
class Student {int id, score;
}Collections.sort(list, (a, b) -> {if (a.score != b.score) return b.score - a.score;return a.id - b.id;
});
2?? 時間類排序（時間戳、操作先后）
例題：
- 日志排序
- 任務調度優先隊列
Arrays.sort(events, (a, b) -> a.time - b.time); // 按時間升序
或使用對象：
class Event {int time, id;
}
Collections.sort(list, Comparator.comparingInt(e -> e.time));
3?? 坐標/區間排序
例題：
- 掃描線、區間覆蓋、最大重疊區間
Arrays.sort(intervals, (a, b) -> {if (a[0] != b[0]) return a[0] - b[0]; // 起點升序return a[1] - b[1]; // 終點升序
});
4?? Map排序（基于統計結果）
例題：
- 詞頻統計
- 熱度排序
Map<Integer, Integer> count = new HashMap<>();
for (int x : arr) count.put(x, count.getOrDefault(x, 0) + 1);List<Map.Entry<Integer, Integer>> list = new ArrayList<>(count.entrySet());// 按頻率降序、數值升序排序
Collections.sort(list, (a, b) -> {if (!a.getValue().equals(b.getValue()))return b.getValue() - a.getValue();return a.getKey() - b.getKey();
});
5?? 并查集/連通塊大小排序
例題：
- 社交網絡連通塊分析
- 親戚關系等題
// 每個集合統計 size[]
// 然后將 size 按 root 排序
List<int[]> groups = new ArrayList<>();
for (int i = 1; i <= n; i++) {if (find(i) == i) groups.add(new int[]{i, size[i]});
}
groups.sort((a, b) -> b[1] - a[1]); // 按集合大小降序
6?? 字典序排序（字符串或數組）
例題：
- 最小字典序拼接
- 拼接序列/排序
Arrays.sort(strings); // 默認字典序
Arrays.sort(strings, Comparator.reverseOrder()); // 字典序逆序
? 三、優先隊列（堆）排序應用速查
| 需求類型 | 排序維度 | 聲明語句 |
|---|---|---|
| 最小值優先隊列 | 值升序 | PriorityQueue<Integer> pq = new PriorityQueue<>(); |
| 最大值優先隊列 | 值降序 | PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a); |
| 多字段堆排序 | 數組 or 對象 | PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{...}); |
? 四、常用 Java API 排序參考
| 用法 | 示例代碼 |
|---|---|
| 數組默認排序 | Arrays.sort(arr); |
| 對象數組排序 | Arrays.sort(objArr, (a, b) -> ...); |
| List 排序 | Collections.sort(list, (a, b) -> ...); |
| Map 排序（按值） | 見上面 Map 示例 |
| PriorityQueue 自定義順序 | new PriorityQueue<>((a,b) -> ...) |
📌 附：CCF CSP 排序常見題目清單（歷年）
| 年份 | 題目名稱 | 排序類型 |
|---|---|---|
| 202206 | 通信網絡 | 拓撲序 / 時間戳 |
| 202012 | 直播獲獎名單 | 詞頻統計 + 排序 |
| 201809 | 元素選擇器 | DOM序樹結構排序 |
| 201712 | 游戲 | 結構排序 + 計分 |
| 201703 | 學生排隊 | 優先隊列 / 模擬 |
🔐 五、哈希/計數
HashMap,HashSet：用于快速查找TreeMap,TreeSet：自動排序Map.getOrDefault(k, v)：避免空指針int[] cnt = new int[m + 1];：模擬 HashMap 的計數數組，常用于編號有限的場景（如 CSP）
🧩 六、模擬題常用
Scanner：快速讀入StringTokenizer（復雜輸入場景）或BufferedReader- 多維數組處理：
int[][] arr = new int[n][m]; - 模擬移動：方向數組
dx/dy
🔄 七、并查集（Union-Find）
int[] fa = new int[n];
for (int i = 0; i < n; i++) fa[i] = i;int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); }void union(int x, int y) { fa[find(x)] = find(y); }
🌉 八、圖論常用
? 圖存儲
- 鄰接表：
List<List<Integer>> graph = new ArrayList<>(); - 鄰接矩陣：
int[][] graph = new int[n][n];
? 遍歷
- DFS / BFS 模板
Queue<Integer> q = new LinkedList<>();
📐 九、動態規劃（DP）
- 通常使用
int[],int[][]進行狀態壓縮或轉移 - 可用
Arrays.fill()進行初始化 - 多維數組狀態轉移舉例：
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
💡 十、貪心算法
- 常用
Arrays.sort()或Collections.sort()后進行策略判斷 - 自定義排序：
Arrays.sort(arr, (a, b) -> a[0] - b[0]);
- 優先隊列（堆）：
PriorityQueue<Integer> pq = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(x); pq.poll(); pq.peek();
🧮 十一、常用工具類
| 功能 | API |
|---|---|
| 比較兩個對象 | Objects.equals(a, b) |
| 大整數運算 | BigInteger（如加減乘除、取模、冪） |
| 高精度小數 | BigDecimal |
Java API 使用示例代碼
當然可以，下面我將針對 CSP 常考模塊（字符串處理、模擬、哈希、排序、并查集、圖、DP、貪心）分別提供一兩個典型題目的Java API 使用示例代碼，方便你快速上手實戰題目。
? 一、字符串處理 - 示例題：“單詞統計”
題目描述：給定一段英文文本，統計不同單詞出現次數（不區分大小寫，去除標點）。
import java.util.*;public class WordCount {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String text = sc.nextLine().toLowerCase().replaceAll("[^a-z ]", " ");String[] words = text.split("\\s+");Map<String, Integer> count = new HashMap<>();for (String word : words) {if (!word.isEmpty()) {count.put(word, count.getOrDefault(word, 0) + 1);}}count.forEach((k, v) -> System.out.println(k + ": " + v));}
}
? 二、模擬 - 示例題：“排隊打水”
題目描述：n 個人排隊，每個人打水需要 t[i] 分鐘，問最小總等待時間。
import java.util.*;public class WaterQueue {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] t = new int[n];for (int i = 0; i < n; i++) t[i] = sc.nextInt();Arrays.sort(t); // 排序是貪心核心long res = 0;for (int i = 0; i < n; i++) {res += (long) t[i] * (n - i - 1); // 模擬等待時間}System.out.println(res);}
}
? 三、哈希 - 示例題：“出現次數統計”
題目描述：輸入 n 個整數，輸出每個數的出現次數。
import java.util.*;public class FrequencyCount {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {int x = sc.nextInt();map.put(x, map.getOrDefault(x, 0) + 1);}for (int key : map.keySet()) {System.out.println(key + ": " + map.get(key));}}
}
? 四、排序 - 示例題：“按得分排序”
題目描述：輸入學生姓名與分數，按分數從高到低排序輸出。
import java.util.*;public class ScoreSort {static class Student {String name; int score;Student(String n, int s) { name = n; score = s; }}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();List<Student> list = new ArrayList<>();for (int i = 0; i < n; i++)list.add(new Student(sc.next(), sc.nextInt()));list.sort((a, b) -> b.score - a.score); // 自定義排序for (Student s : list)System.out.println(s.name + " " + s.score);}
}
? 五、并查集 - 示例題：“朋友圈數量”
題目描述：有 n 個人，m 對朋友關系，問總共有多少個朋友圈（連通塊）。
import java.util.*;public class UnionFindFriends {static int[] fa;static int find(int x) {if (fa[x] != x) fa[x] = find(fa[x]);return fa[x];}static void union(int x, int y) {fa[find(x)] = find(y);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt();fa = new int[n + 1];for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 0; i < m; i++) union(sc.nextInt(), sc.nextInt());Set<Integer> roots = new HashSet<>();for (int i = 1; i <= n; i++) roots.add(find(i));System.out.println(roots.size()); // 連通塊個數}
}
? 六、圖 - 示例題：“最短路徑 BFS”
題目描述：無權圖從點 A 到點 B 的最短路徑長度。
import java.util.*;public class BFSShortestPath {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt();List<List<Integer>> g = new ArrayList<>();for (int i = 0; i <= n; i++) g.add(new ArrayList<>());for (int i = 0; i < m; i++) {int u = sc.nextInt(), v = sc.nextInt();g.get(u).add(v); g.get(v).add(u);}int[] dist = new int[n + 1];Arrays.fill(dist, -1);Queue<Integer> q = new LinkedList<>();q.offer(1); dist[1] = 0;while (!q.isEmpty()) {int cur = q.poll();for (int nei : g.get(cur)) {if (dist[nei] == -1) {dist[nei] = dist[cur] + 1;q.offer(nei);}}}System.out.println(dist[n]);}
}
? 七、動態規劃（DP）- 示例題：“背包問題”
import java.util.*;public class ZeroOneKnapsack {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), W = sc.nextInt();int[] w = new int[n + 1], v = new int[n + 1];for (int i = 1; i <= n; i++) {w[i] = sc.nextInt(); v[i] = sc.nextInt();}int[] dp = new int[W + 1];for (int i = 1; i <= n; i++) {for (int j = W; j >= w[i]; j--) {dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);}}System.out.println(dp[W]);}
}
? 八、貪心 - 示例題：“活動安排問題”
題目描述：選擇最多不重疊的活動。
import java.util.*;public class GreedyActivitySelect {static class Act {int start, end;Act(int s, int e) { start = s; end = e; }}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();List<Act> list = new ArrayList<>();for (int i = 0; i < n; i++)list.add(new Act(sc.nextInt(), sc.nextInt()));list.sort(Comparator.comparingInt(a -> a.end)); // 按結束時間排序int cnt = 0, lastEnd = 0;for (Act a : list) {if (a.start >= lastEnd) {cnt++; lastEnd = a.end;}}System.out.println(cnt);}
}
藍橋杯萬字攻略：算法模板大放送！-Java 版
主要內容
由數據范圍反推算法復雜度以及算法內容
一般ACM或者筆試題的時間限制是1秒或2秒。在這種情況下，Java代碼中的操作次數控制在 (10^7 \sim 10^8) 為最佳。
下面給出在不同數據范圍下，代碼的時間復雜度和算法該如何選擇：
| 數據范圍 | 時間復雜度 | 算法 |
|---|---|---|
| (n \le 30) | 指數級別 | dfs+剪枝，狀態壓縮dp |
| (n \le 100) | (O(n^3)) | Floyd，dp，高斯消元 |
| (n \le 1000) | (O(n2))，(O(n2logn)) | dp，二分，樸素版Dijkstra、樸素版Prim、Bellman-Ford |
| (n \le 10000) | (O(n * \sqrt n)) | 塊狀鏈表、分塊、莫隊 |
| (n \le 100000) | (O(nlogn)) | 各種sort，線段樹、樹狀數組、set/map、heap、拓撲排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整體二分、后綴數組、樹鏈剖分、動態樹 |
| (n \le 1000000) | (O(n)), 以及常數較小的 (O(nlogn)) 算法 | 單調隊列、 hash、雙指針掃描、并查集，kmp、AC自動機，常數比較小的 (O(nlogn)) 的做法：sort、樹狀數組、heap、dijkstra、spfa |
| (n \le 10000000) | (O(n)) | 雙指針掃描、kmp、AC自動機、線性篩素數 |
| (n \le 10^9) | (O(\sqrt n)) | 判斷質數 |
| (n \le 10^{18}) | (O(logn)) | 最大公約數，快速冪，數位DP |
| (n \le 10^{1000}) | (O((logn)^2)) | 高精度加減乘除 |
| (n \le 10^{100000}) | (O(logk \times loglogk)，k表示位數) | 高精度加減、FFT/NTT 由數據范圍反推算法 |
基礎算法
快速排序算法模板
import java.util.Arrays;public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[low + (high - low) / 2];int i = low - 1;int j = high + 1;while (true) {while (arr[++i] < pivot);while (arr[--j] > pivot);if (i >= j) {return j;}swap(arr, i, j);}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}
歸并排序算法模板
import java.util.Arrays;public class MergeSort {private static int[] temp;public static void mergeSort(int[] arr) {temp = new int[arr.length];mergeSort(arr, 0, arr.length - 1);}private static void mergeSort(int[] arr, int l, int r) {if (l >= r) {return;}int mid = l + (r - l) / 2;mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);merge(arr, l, mid, r);}private static void merge(int[] arr, int l, int mid, int r) {System.arraycopy(arr, l, temp, l, r - l + 1);int i = l, j = mid + 1, k = l;while (i <= mid && j <= r) {if (temp[i] <= temp[j]) {arr[k++] = temp[i++];} else {arr[k++] = temp[j++];}}while (i <= mid) {arr[k++] = temp[i++];}while (j <= r) {arr[k++] = temp[j++];}}
}
整數二分算法模板
public class BinarySearch {public static int bsearch_1(int[] arr, int target) {int l = 0, r = arr.length - 1;while (l < r) {int mid = l + (r - l) / 2;if (arr[mid] >= target) {r = mid;} else {l = mid + 1;}}return l;}public static int bsearch_2(int[] arr, int target) {int l = 0, r = arr.length - 1;while (l < r) {int mid = l + (r - l + 1) / 2;if (arr[mid] <= target) {l = mid;} else {r = mid - 1;}}return l;}
}
浮點數二分算法模板
public class BinarySearchFloat {public static double bsearch_3(double l, double r) {final double eps = 1e-6;while (r - l > eps) {double mid = (l + r) / 2;if (check(mid)) {r = mid;} else {l = mid;}}return l;}private static boolean check(double x) {return false;}
}
高精度加法
import java.util.ArrayList;
import java.util.List;public class HighPrecisionAddition {public static List<Integer> add(List<Integer> A, List<Integer> B) {if (A.size() < B.size()) {return add(B, A);}List<Integer> C = new ArrayList<>();int t = 0;for (int i = 0; i < A.size(); i++) {t += A.get(i);if (i < B.size()) {t += B.get(i);}C.add(t % 10);t /= 10;}if (t != 0) {C.add(t);}while (C.size() > 1 && C.get(C.size() - 1) == 0) {C.remove(C.size() - 1);}return C;}
}
高精度減法
import java.util.ArrayList;
import java.util.List;public class HighPrecisionSubtraction {public static List<Integer> sub(List<Integer> A, List<Integer> B) {List<Integer> C = new ArrayList<>();int t = 0;for (int i = 0; i < A.size(); i++) {t = A.get(i) - t;if (i < B.size()) {t -= B.get(i);}C.add((t + 10) % 10);if (t < 0) {t = 1;} else {t = 0;}}while (C.size() > 1 && C.get(C.size() - 1) == 0) {C.remove(C.size() - 1);}return C;}
}
高精度乘低精度
import java.util.ArrayList;
import java.util.List;public class HighPrecisionMultiplication {public static List<Integer> mul(List<Integer> A, int b) {List<Integer> C = new ArrayList<>();int t = 0;for (int i = 0; i < A.size() || t != 0; i++) {if (i < A.size()) {t += A.get(i) * b;}C.add(t % 10);t /= 10;}while (C.size() > 1 && C.get(C.size() - 1) == 0) {C.remove(C.size() - 1);}return C;}
}
高精度除以低精度
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class HighPrecisionDivision {public static List<Integer> div(List<Integer> A, int b, int[] r) {List<Integer> C = new ArrayList<>();int remainder = 0;for (int i = A.size() - 1; i >= 0; i--) {remainder = remainder * 10 + A.get(i);C.add(remainder / b);remainder %= b;}Collections.reverse(C);while (C.size() > 1 && C.get(C.size() - 1) == 0) {C.remove(C.size() - 1);}r[0] = remainder;return C;}
}
一維前綴和
import java.util.ArrayList;
import java.util.List;public class PrefixSum1D {public static List<Integer> getPrefixSum(List<Integer> arr) {List<Integer> prefixSum = new ArrayList<>();prefixSum.add(0);for (int num : arr) {prefixSum.add(prefixSum.get(prefixSum.size() - 1) + num);}return prefixSum;}public static int querySum(List<Integer> prefixSum, int l, int r) {return prefixSum.get(r) - prefixSum.get(l - 1);}
}
二維前綴和
import java.util.ArrayList;
import java.util.List;public class PrefixSum2D {public static List<List<Integer>> getPrefixSum(List<List<Integer>> matrix) {int rows = matrix.size();int cols = matrix.get(0).size();List<List<Integer>> prefixSum = new ArrayList<>();for (int i = 0; i <= rows; i++) {List<Integer> row = new ArrayList<>();for (int j = 0; j <= cols; j++) {row.add(0);}prefixSum.add(row);}for (int i = 1; i <= rows; i++) {for (int j = 1; j <= cols; j++) {prefixSum.get(i).set(j, matrix.get(i - 1).get(j - 1) + prefixSum.get(i - 1).get(j) + prefixSum.get(i).get(j - 1) - prefixSum.get(i - 1).get(j - 1));}}return prefixSum;}public static int querySum(List<List<Integer>> prefixSum, int x1, int y1, int x2, int y2) {return prefixSum.get(x2).get(y2) - prefixSum.get(x1 - 1).get(y2) - prefixSum.get(x2).get(y1 - 1) + prefixSum.get(x1 - 1).get(y1 - 1);}
}
一維差分
import java.util.ArrayList;
import java.util.List;public class Difference1D {public static List<Integer> getDifference(List<Integer> arr) {List<Integer> diff = new ArrayList<>();diff.add(arr.get(0));for (int i = 1; i < arr.size(); i++) {diff.add(arr.get(i) - arr.get(i - 1));}return diff;}public static void applyDifference(List<Integer> arr, int l, int r, int c) {arr.set(l, arr.get(l) + c);if (r + 1 < arr.size()) {arr.set(r + 1, arr.get(r + 1) - c);}}
}
二維差分
import java.util.ArrayList;
import java.util.List;public class Difference2D {public static List<List<Integer>> getDifference(List<List<Integer>> matrix) {int rows = matrix.size();int cols = matrix.get(0).size();List<List<Integer>> diff = new ArrayList<>();for (int i = 0; i < rows; i++) {List<Integer> row = new ArrayList<>();row.add(matrix.get(i).get(0));for (int j = 1; j < cols; j++) {row.add(matrix.get(i).get(j) - matrix.get(i).get(j - 1));}diff.add(row);}return diff;}public static void applyDifference(List<List<Integer>> diff, int x1, int y1, int x2, int y2, int c) {diff.get(x1).set(y1, diff.get(x1).get(y1) + c);diff.get(x1).set(y2 + 1, diff.get(x1).get(y2 + 1) - c);diff.get(x2 + 1).set(y1, diff.get(x2 + 1).get(y1) - c);diff.get(x2 + 1).set(y2 + 1, diff.get(x2 + 1).get(y2 + 1) + c);}
}
位運算
public class BitOperations {public static int getKthBit(int n, int k) {return (n >> k) & 1;}public static int lowbit(int n) {return n & -n;}
}
雙指針算法
import java.util.ArrayList;
import java.util.List;public class TwoPointers {public static List<Integer> twoSum(List<Integer> nums, int target) {int i = 0, j = nums.size() - 1;while (i < j) {int sum = nums.get(i) + nums.get(j);if (sum < target) {i++;} else if (sum > target) {j--;} else {return List.of(i, j);}}return List.of();}
}
離散化
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class Discretization {public static List<Integer> discretize(List<Integer> arr) {List<Integer> sortedArr = new ArrayList<>(arr);Collections.sort(sortedArr);sortedArr = new ArrayList<>(sortedArr.stream().distinct().toList());List<Integer> res = new ArrayList<>();for (int num : arr) {int idx = Collections.binarySearch(sortedArr, num);res.add(idx + 1);}return res;}
}
區間合并
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;public class IntervalMerge {public static List<int[]> merge(List<int[]> intervals) {List<int[]> res = new ArrayList<>();if (intervals.isEmpty()) {return res;}intervals.sort(Comparator.comparingInt(a -> a[0]));int start = intervals.get(0)[0];int end = intervals.get(0)[1];for (int i = 1; i < intervals.size(); i++) {int[] interval = intervals.get(i);if (end < interval[0]) {res.add(new int[]{start, end});start = interval[0];end = interval[1];} else {end = Math.max(end, interval[1]);}}res.add(new int[]{start, end});return res;}
}
)
