Java--ACM常用语句

行止AC

288人浏览 · 2025-11-07 16:23:52

行止AC · 2025-11-07 16:23:52 发布

Java–ACM常用语句

一、输入输出处理

1、快速输入（替代Scanner，处理大量数据）

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" "); // 读取一行并分割
        int n = Integer.parseInt(parts[0]);
        
        // 读取多组数据（按行读取）
        String line;
        while ((line = br.readLine()) != null) {
            if (line.isEmpty()) continue; // 跳过空行
            int x = Integer.parseInt(line);
            // 处理逻辑
        }
    }
}

2、快速输出（避免System.out.println频繁调用）

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write("Hello\n"); // 写入字符串，手动加换行
        bw.write(String.valueOf(123) + "\n"); // 写入数字
        bw.flush(); // 必须刷新，否则可能不输出
    }
}

3、格式化输出（String.format）

// 保留2位小数
double pi = 3.14159;
System.out.println(String.format("%.2f", pi)); // 输出 3.14

// 整数补零（共3位）
int num = 5;
System.out.println(String.format("%03d", num)); // 输出 005

二、常用数据结构

1、数组（Array）与动态数组（ArrayList）

// 数组初始化
int[] arr = new int[10]; // 长度10的int数组
int[] arr2 = {1, 2, 3}; // 直接赋值

// ArrayList（动态扩容，替代数组）
import java.util.ArrayList;
ArrayList<Integer> list = new ArrayList<>();
list.add(1); // 添加元素
list.get(0); // 获取索引0的元素
list.remove(0); // 删除索引0的元素
list.size(); // 长度

2、哈希表（HashMap）与哈希集（HashSet）

import java.util.HashMap;
import java.util.HashSet;

// HashMap：键值对计数
HashMap<Integer, Integer> cnt = new HashMap<>();
cnt.put(5, cnt.getOrDefault(5, 0) + 1); // 计数（不存在则默认0）
int val = cnt.getOrDefault(3, 0); // 获取值，默认0

// HashSet：去重、判断存在
HashSet<Integer> set = new HashSet<>();
set.add(1);
set.contains(1); // 返回true
set.remove(1);

3、队列（Queue）与双端队列（Deque）

import java.util.LinkedList;
import java.util.Queue;
import java.util.Deque;

// 队列（FIFO，适合BFS）
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 入队
queue.poll(); // 出队（队首）
queue.peek(); // 查看队首

// 双端队列（Deque，支持首尾操作）
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(0); // 队首入队
deque.addLast(2); // 队尾入队
deque.pollFirst(); // 队首出队
deque.pollLast(); // 队尾出队

4、堆（PriorityQueue，优先队列）

import java.util.PriorityQueue;

// 小根堆（默认，队首为最小元素）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 大根堆（通过比较器实现）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

maxHeap.offer(3); // 入堆
maxHeap.poll(); // 出堆（队首最大元素）
maxHeap.peek(); // 查看堆顶

三、算法模版

1、排序与二分查找

import java.util.Arrays;

// 数组排序（升序）
int[] arr = {3, 1, 2};
Arrays.sort(arr); // 排序后：[1, 2, 3]

// 二分查找（Arrays.binarySearch，返回索引，不存在则返回负数）
int idx = Arrays.binarySearch(arr, 2); // 返回1
if (idx < 0) {
    // 不存在，插入位置为 -idx - 1
}

// 自定义二分查找（找目标值）
public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

2、前缀和（快速求区间和）

// 一维前缀和
int n = arr.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}
int sumLR = prefix[r + 1] - prefix[l]; // 求arr[l..r]的和（0<=l<=r <n）

3、差分（快速区间更新）

// 一维差分：对[l..r]加val，最后求前缀和得结果
int n = 10;
int[] diff = new int[n + 2]; // 避免越界
int l = 2, r = 5, val = 3;
diff[l] += val;
diff[r + 1] -= val;

// 还原数组
int[] res = new int[n];
res[0] = diff[0];
for (int i = 1; i < n; i++) {
    res[i] = res[i - 1] + diff[i];
}

4、并查集（Union-Find，处理连通性）

class UnionFind {
    int[] parent;
    int[] rank;
    
    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始化父节点为自身
            rank[i] = 0;
        }
    }
    
    // 路径压缩
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // 按秩合并
    public void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot) return;
        
        if (rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;
        } else {
            parent[yRoot] = xRoot;
            if (rank[xRoot] == rank[yRoot]) {
                rank[xRoot]++;
            }
        }
    }
}

5、DFS与BFS

import java.util.*;

// DFS（递归，邻接表为例）
public static void dfs(int u, List<List<Integer>> adj, boolean[] visited) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

// BFS（队列，邻接表为例）
public static void bfs(int start, List<List<Integer>> adj, boolean[] visited) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                queue.offer(v);
            }
        }
    }
}

四、优化技巧

1、避免超时

用 BufferedReader/BufferedWriter 替代 Scanner/System.out，尤其大数据量时。
数组比 ArrayList 快，能确定大小的场景优先用数组。
字符串拼接用 StringBuilder，避免 + 运算符（效率低）：

StringBuilder sb = new StringBuilder();
sb.append("a").append(123).append("\n");
System.out.println(sb.toString());

2、处理多组测试用例

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
    // 每组测试用例逻辑
}

3、常量与静态方法

频繁使用的变量定义为 static final（如 INF = 0x3f3f3f3f），工具方法定义为 static，减少对象创建开销。

五、常见情景示例

统计数字出现次数：

import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] parts = br.readLine().split(" ");
        HashMap<String, Integer> cnt = new HashMap<>();
        for (String s : parts) {
            cnt.put(s, cnt.getOrDefault(s, 0) + 1);
        }
        // 输出结果
        for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}

最长递增子序列（LIS）：

import java.util.*;
public class Main {
    public static int lis(int[] arr) {
        List<Integer> tails = new ArrayList<>();
        for (int num : arr) {
            int idx = Collections.binarySearch(tails, num);
            if (idx < 0) idx = -idx - 1; // 计算插入位置
            if (idx == tails.size()) {
                tails.add(num);
            } else {
                tails.set(idx, num);
            }
        }
        return tails.size();
    }
}