Java 常用 API 分类总结（算法竞赛考前速记篇）- 适用于算法竞赛（如 CCF CSP、蓝桥杯、NOI）

以下是Java 常用 API 的系统性总结，特别适用于算法竞赛（如 CCF CSP、蓝桥杯、NOI）场景。按照功能分类，并给出代表性方法及简要用法说明，方便复习与带入考场：

✅ Java 常用 API 分类总结（算法竞赛篇）

常见数据类型的数据范围与默认值

当然可以！以下是 Java 中常见数据类型的数据范围与默认值总结，适合你背诵、练习和面试使用：

✅ 一、Java 基本数据类型总结（8种）

✅ 二、常用封装类与常量（用于边界判断）

✅ 三、如何选择数据类型？（实用建议）

✅ 四、经典面试题：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 类）

2️⃣ 高效字符串拼接（StringBuilder / StringBuffer）

⚠️ StringBuilder 非线程安全，StringBuffer 线程安全（但慢）。

3️⃣ 数学计算（Math 类）

4️⃣ 数组处理（Arrays 工具类）

5️⃣ 集合框架

List（ArrayList / LinkedList）

Set（HashSet / TreeSet）

✅ 一、常见 Set 实现类对比

✅ 二、常用 Set API 汇总

✅ 三、典型代码模板

📌 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]

✅ 四、适配题型速查

✅ 五、背诵口诀：“增删查，去重快，TreeSet 排序不带盖！”

✅ 六、你可以练习的题目（推荐）

Map（HashMap / TreeMap）

频次统计（CSP常见）

map.put(x, map.getOrDefault(x, 0) + 1);

6️⃣ Collections 工具类（操作集合）

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 类）

9️⃣ 大数处理

BigInteger

BigInteger a = new BigInteger("123456789");
BigInteger b = new BigInteger("987654321");
a.add(b).toString(); // 字符串输出

BigDecimal

🔟 时间函数

🔟+1 正则表达式处理

🔟+2 输入输出（Scanner, BufferedReader, PrintWriter）

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() 有什么区别？

🚫 不可以这样混用：

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() 返回的是一个固定长度的列表，不能增删元素，只能排序或修改已有元素。

✅ 四、初学者建议记忆总结

✨ 五、通用排序封装函数（建议记忆）

// 通用对象排序（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;
    }

    @Override
    public 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 示例等，帮助你快速定位解题方案。

✅ 一、速查表概览（按题型分类）

✅ 二、各类型题型详解与模板

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()); // 字典序逆序

✅ 三、优先队列（堆）排序应用速查

✅ 四、常用 Java API 排序参考

📌 附：CCF CSP 排序常见题目清单（历年）

🔐 五、哈希/计数

• 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();

🧮 十一、常用工具类

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) 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

基础算法

快速排序算法模板

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;
    }
}