OJ 竞赛 Java 新手入门：从快读、数组二分到集合、字符串和常见坑一篇打通

本文目录

• • 一、阅读定位
  • 二、Java 输入输出：快读模板与常见读入坑
  • • 1. 为什么 OJ 不建议优先用 Scanner
    • 2. 快读模板
    • 3. 常见输入格式
    • 4. 读到 EOF
    • 5. 输出也要注意性能
  • 三、数组、排序、Comparator 与二分查找
  • • 1. Arrays 常用方法
    • 2. Arrays.sort 基础用法
    • 3. int[] 不能直接传 Comparator
    • 4. Comparator 和 Lambda
    • 5. Arrays.binarySearch 返回值
    • 6. lowerBound 和 upperBound
    • 7. Arrays.asList 的坑
  • 四、二维数组、矩阵模拟、String 与 StringBuilder
  • • 1. 二维数组的行和列
    • 2. 字符矩阵输入
    • 3. 二维数组深拷贝
    • 4. 方向数组
    • 5. 矩阵转置和旋转
    • 6. String 和 StringBuilder
    • 7. 字符串常用方法
  • 五、集合框架：List、Set、Map、Queue 怎么选
  • • 1. 集合选择速查
    • 2. ArrayList
    • 3. Queue 和 Deque
    • 4. HashSet
    • 5. HashMap
    • 6. 自定义对象作为 key
  • 六、数值类型、Math、位运算与 return 常见坑
  • • 1. 数值类型怎么选
    • 2. 自动转换和强制转换
    • 3. 溢出问题
    • 4. Math 常见方法
    • 5. 位运算常用套路
    • 6. return 的作用
  • 七、CSP 常见案例：字符串轮转与循环节
  • • 1. 判断字符串轮转
    • 2. 寻找最短循环节
  • 八、总复习速查表
  • 常见坑总结
  • 总结

这篇文章整理的是 Java 刷 OJ 时最容易反复用到的基础内容：快读模板、数组排序、二分查找、二维数组、字符串、集合、数值类型、Math、位运算和 return。

一、阅读定位

• 刚开始用 Java 刷竞赛题目的人。
• 代码能写出来，但经常卡在输入输出、API 使用、类型溢出的人。
• 想准备一份 Java 刷题基础速查模板的人。

这篇文章不讲复杂算法，而是先把 Java 刷题基础工具打稳。很多新手不是算法思路完全不会，而是被输入、排序、集合、字符串和边界细节拖住。

二、Java 输入输出：快读模板与常见读入坑

1. 为什么 OJ 不建议优先用 Scanner

Scanner 写起来简单，但它会做较多解析工作。输入规模较大时，Scanner 可能比 BufferedReader 慢很多，容易因为输入输出超时。

新手可以这样选：

Scanner 不是不能用，而是正式刷题时要优先考虑速度和稳定性。

2. 快读模板

OJ 中类名通常必须写成 Main。下面这份模板适合大多数整数、字符串输入题。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
static class FastScanner {
private final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private StringTokenizer st;

String next() throws IOException {
while (st == null || !st.hasMoreTokens()) {
String line = br.readLine();
if (line == null) return null;
st = new StringTokenizer(line);
}
return st.nextToken();
}

int nextInt() throws IOException {
return Integer.parseInt(next());
}

long nextLong() throws IOException {
return Long.parseLong(next());
}

double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}

public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner();
int n = fs.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = fs.nextInt();
}

StringBuilder ans = new StringBuilder();
for (int x : a) {
ans.append(x).append(' ');
}
System.out.println(ans);
}
}

这份模板的核心是 next()：当前行 token 用完后继续读下一行；如果已经没有下一行，就返回 null。

3. 常见输入格式

第一行给 n，后面给 n 个数：

int n = fs.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = fs.nextInt();
}

第一行给 n 和 m，后面是 n 行 m 列矩阵：

int n = fs.nextInt();
int m = fs.nextInt();
int[][] grid = new int[n][m];

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = fs.nextInt();
}
}

记住：i 通常表示行，j 通常表示列。

4. 读到 EOF

有些题没有给测试组数，需要一直读到输入结束。

String token;
while ((token = fs.next()) != null) {
int x = Integer.parseInt(token);
// 继续读本组后续数据
}

如果每组固定两个整数：

String first;
while ((first = fs.next()) != null) {
int a = Integer.parseInt(first);
int b = fs.nextInt();
System.out.println(a + b);
}

5. 输出也要注意性能

大量输出时，不要在循环里频繁 System.out.println()。可以先拼到 StringBuilder，最后一次输出。

StringBuilder sb = new StringBuilder();
for (int i = 1; i <= 100000; i++) {
sb.append(i).append('\\n');
}
System.out.print(sb);

三、数组、排序、Comparator 与二分查找

1. Arrays 常用方法

刷题常用 java.util.Arrays。

import java.util.Arrays;

public class Main {
public static void main(String[] args) {
int[] a = {5, 2, 8, 1, 3};

Arrays.sort(a);
System.out.println(Arrays.toString(a)); // [1, 2, 3, 5, 8]

int[] b = {1, 2, 3, 5, 8};
System.out.println(Arrays.equals(a, b)); // true
}
}

常用方法：

2. Arrays.sort 基础用法

基本类型数组默认升序排序。

int[] nums = {50, 10, 25, 1, 99};
Arrays.sort(nums);
System.out.println(Arrays.toString(nums)); // [1, 10, 25, 50, 99]

也可以只排序一段范围，左闭右开：

Arrays.sort(nums, 1, 4); // 只排序下标 1, 2, 3

3. int[] 不能直接传 Comparator

基本类型数组不能直接自定义排序规则。

int[] a = {3, 1, 2};
Arrays.sort(a); // 可以，升序

// Arrays.sort(a, (x, y) -> y – x); // 错误：int[] 不能传 Comparator

如果要降序，常见做法是改成包装类数组 Integer[]。

import java.util.Arrays;
import java.util.Comparator;

public class Main {
public static void main(String[] args) {
Integer[] a = {3, 1, 2};
Arrays.sort(a, Comparator.reverseOrder());
System.out.println(Arrays.toString(a)); // [3, 2, 1]
}
}

如果题目对性能要求很高，优先考虑 int[] 升序排序，然后从后往前遍历。

4. Comparator 和 Lambda

自定义对象排序时，不要写 a.age – b.age，极端数据下可能溢出。推荐使用 Integer.compare。

import java.util.Arrays;

public class Main {
static class Student {
String name;
int age;

Student(String name, int age) {
this.name = name;
this.age = age;
}
}

public static void main(String[] args) {
Student[] students = {
new Student("Tom", 20),
new Student("Jerry", 18)
};

Arrays.sort(students, (a, b) -> Integer.compare(a.age, b.age));
}
}

多字段排序，例如先按分数降序，分数相同按编号升序：

list.sort((a, b) -> {
if (a.score != b.score) {
return Integer.compare(b.score, a.score);
}
return Integer.compare(a.id, b.id);
});

5. Arrays.binarySearch 返回值

Arrays.binarySearch(a, target) 的前提是数组已经有序。

int[] a = {1, 3, 5, 7};
int index = Arrays.binarySearch(a, 5);
System.out.println(index); // 2

如果没找到，返回值是：

-(插入点) – 1

还原插入点：

int result = Arrays.binarySearch(a, target);
int pos = result >= 0 ? result : –(result + 1);

也可以写成：

int pos = result >= 0 ? result : ~result;

重复元素时，binarySearch 不保证返回第一个或最后一个。要找边界，建议手写二分。

6. lowerBound 和 upperBound

lowerBound：找第一个 >= target 的位置。

static int lowerBound(int[] a, int target) {
int left = 0;
int right = a.length;
while (left < right) {
int mid = left + (right – left) / 2;
if (a[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

upperBound：找第一个 > target 的位置。

static int upperBound(int[] a, int target) {
int left = 0;
int right = a.length;
while (left < right) {
int mid = left + (right – left) / 2;
if (a[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

统计某个数出现次数：

int count = upperBound(a, x) – lowerBound(a, x);

7. Arrays.asList 的坑

Arrays.asList 对基本类型数组非常容易误用。

int[] a = {1, 2, 3};
// List<int[]> bad = Arrays.asList(a); // 得到的是一个只包含 int[] 的 List

正确把 int[] 转成 List<Integer>：

List<Integer> list = new ArrayList<>();
for (int x : a) {
list.add(x);
}

四、二维数组、矩阵模拟、String 与 StringBuilder

1. 二维数组的行和列

二维数组最常见写法：

int[][] grid = new int[n][m];

其中：

• grid.length 是行数，也就是 n。
• grid[0].length 是列数，也就是 m。
• grid[i][j] 表示第 i 行第 j 列。

固定习惯：外层循环写行 i，内层循环写列 j。

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(grid[i][j] + " ");
}
System.out.println();
}

2. 字符矩阵输入

如果输入是字符矩阵：

3 4
….
.#..
….

可以按行读成字符串：

char[][] grid = new char[n][m];
for (int i = 0; i < n; i++) {
String s = fs.next();
for (int j = 0; j < m; j++) {
grid[i][j] = s.charAt(j);
}
}

3. 二维数组深拷贝

二维数组不能只复制外层引用。

int[][] copy = grid.clone(); // 只复制外层，里面每一行仍然共享

正确写法是逐行复制：

int[][] copy = new int[n][m];
for (int i = 0; i < n; i++) {
copy[i] = Arrays.copyOf(grid[i], m);
}

4. 方向数组

矩阵题经常需要向上下左右移动。建议用方向数组统一处理。

int[] dx = {–1, 1, 0, 0};
int[] dy = {0, 0, –1, 1};

for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
// 处理合法位置 (nx, ny)
}

八方向：

int[] dx = {–1, –1, –1, 0, 0, 1, 1, 1};
int[] dy = {–1, 0, 1, –1, 1, –1, 0, 1};

5. 矩阵转置和旋转

转置就是把 a[i][j] 变成 b[j][i]。

int[][] b = new int[m][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[j][i] = a[i][j];
}
}

顺时针旋转 90 度：

int[][] b = new int[m][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[j][n – 1 – i] = a[i][j];
}
}

6. String 和 StringBuilder

String 是不可变对象。频繁拼接字符串时，每次都可能创建新对象。

不推荐：

String ans = "";
for (int i = 0; i < n; i++) {
ans += i;
}

推荐：

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(i);
}
String ans = sb.toString();

OJ 中如果需要构造大量输出，基本都建议用 StringBuilder。

7. 字符串常用方法

String s = "hello";

int len = s.length();
char c = s.charAt(0);
String part = s.substring(1, 4); // 下标 1 到 3
boolean ok = s.contains("ell");
String[] arr = "1 2 3".split(" ");

注意 substring(l, r) 是左闭右开，不包含 r。

字符串反转：

String s = "abc";
String reversed = new StringBuilder(s).reverse().toString();
System.out.println(reversed); // cba

五、集合框架：List、Set、Map、Queue 怎么选

1. 集合选择速查

2. ArrayList

import java.util.ArrayList;
import java.util.List;

public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);

System.out.println(list.get(1)); // 20
list.set(1, 99);
System.out.println(list.size()); // 3
}
}

如果频繁判断是否存在，不要用 ArrayList.contains，改用 HashSet。

3. Queue 和 Deque

Java 里刷 BFS 推荐用 ArrayDeque。

import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
public static void main(String[] args) {
Queue<Integer> q = new ArrayDeque<>();
q.offer(1);
q.offer(2);

while (!q.isEmpty()) {
int x = q.poll();
System.out.println(x);
}
}
}

常用方法：

Deque 可以当栈使用：

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2

4. HashSet

HashSet 适合去重和快速判断存在。

import java.util.HashSet;
import java.util.Set;

public class Main {
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
set.add(3);
set.add(3);
set.add(5);

System.out.println(set.contains(3)); // true
System.out.println(set.size()); // 2
}
}

常见场景：

• 判断某个数字是否出现过。
• 字符串去重。
• 两数之和里保存已经遍历过的数。
• BFS/DFS 中记录访问状态。

5. HashMap

HashMap 常用于统计次数和保存映射关系。

import java.util.HashMap;
import java.util.Map;

public class Main {
public static void main(String[] args) {
int[] a = {1, 2, 1, 3, 2, 1};
Map<Integer, Integer> count = new HashMap<>();

for (int x : a) {
count.put(x, count.getOrDefault(x, 0) + 1);
}

System.out.println(count); // {1=3, 2=2, 3=1}
}
}

常用方法：

遍历 Map 推荐用 entrySet()：

for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
System.out.println(key + " " + value);
}

6. 自定义对象作为 key

如果把自定义对象放进 HashSet 或作为 HashMap 的 key，必须重写 equals 和 hashCode。

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Main {
static class Point {
int x;
int y;

Point(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point)) return false;
Point point = (Point) o;
return x == point.x && y == point.y;
}

@Override
public int hashCode() {
return Objects.hash(x, y);
}
}

public static void main(String[] args) {
Set<Point> set = new HashSet<>();
set.add(new Point(1, 2));
System.out.println(set.contains(new Point(1, 2))); // true
}
}

刷题时也可以把坐标编码成字符串或整数：

String key = x + "#" + y;
int id = x * m + y;

六、数值类型、Math、位运算与 return 常见坑

1. 数值类型怎么选

刷题最常用的是：

只要题目里有“大数相乘”“求和很多次”“答案可能超过 21 亿”，优先考虑 long。

long sum = 0;
for (int x : a) {
sum += x;
}

2. 自动转换和强制转换

小范围类型可以自动转成大范围类型：

int a = 10;
long b = a;
double c = b;

大范围转小范围需要强制转换，但可能丢失信息：

double x = 3.14;
int y = (int) x; // 3

整数除法会直接舍弃小数：

int a = 5;
int b = 2;
System.out.println(a / b); // 2
System.out.println(1.0 * a / b); // 2.5

3. 溢出问题

即使最后赋值给 long，中间如果先用 int 计算，也可能已经溢出。

错误示例：

int a = 100000;
int b = 100000;
long ans = a * b; // 已经在 int 里溢出了

正确写法：

long ans = 1L * a * b;

1L 会让整个表达式按 long 计算。

4. Math 常见方法

int a = Math.abs(–10);
double b = Math.sqrt(16);
double c = Math.pow(2, 10);
int d = Math.max(3, 5);
int e = Math.min(3, 5);

注意：

• Math.sqrt 返回 double。
• Math.pow 返回 double。
• Math.abs 的返回类型和参数有关。

如果题目需要整数幂，且指数不大，可以自己循环乘，避免浮点误差。

long pow = 1;
for (int i = 0; i < k; i++) {
pow *= base;
}

5. 位运算常用套路

判断奇偶：

if ((x & 1) == 1) {
System.out.println("odd");
} else {
System.out.println("even");
}

找唯一出现一次的数：

int ans = 0;
for (int x : nums) {
ans ^= x;
}
System.out.println(ans);

判断 2 的幂：

static boolean isPowerOfTwo(int x) {
return x > 0 && (x & (x – 1)) == 0;
}

左移和右移：

int a = 3;
System.out.println(a << 1); // 6
System.out.println(a >> 1); // 1

竞赛中不必为了“快”强行用位移替代乘除，除非题目本身就是位运算或状态压缩。

6. return 的作用

return 有两个常见作用：

static int max(int a, int b) {
if (a > b) {
return a;
}
return b;
}

在 main 中，return; 可以提前结束程序：

public static void main(String[] args) {
int n = 0;
if (n == 0) {
return;
}
System.out.println("不会执行到这里");
}

注意：return 只结束当前函数，不会自动结束所有外层逻辑。

七、CSP 常见案例：字符串轮转与循环节

1. 判断字符串轮转

如果 b 是 a 的某种轮转，那么 b 一定会出现在 a + a 中。

static boolean isRotation(String a, String b) {
if (a.length() != b.length()) {
return false;
}
return (a + a).contains(b);
}

例如：

a = "abcde"
b = "cdeab"
a + a = "abcdeabcde"

cdeab 出现在 abcdeabcde 中，所以是轮转。

2. 寻找最短循环节

可以枚举长度 len，只考虑能整除原串长度的 len。

static int minPeriod(String s) {
int n = s.length();
for (int len = 1; len <= n; len++) {
if (n % len != 0) {
continue;
}

boolean ok = true;
for (int i = len; i < n; i++) {
if (s.charAt(i) != s.charAt(i % len)) {
ok = false;
break;
}
}

if (ok) {
return len;
}
}
return n;
}

这个模板适合新手理解循环节。更高级的做法可以用 KMP，但入门阶段先把暴力枚举写稳。

八、总复习速查表

常见坑总结

总结

Java 刷 OJ，基础阶段最重要的不是背很多高级算法，而是先把语言工具写稳。输入输出、数组排序、二分、二维数组、字符串、集合、数值类型这些内容看起来基础，但每一块都可能影响能不能 AC。

建议新手先把本文里的模板和坑点整理成自己的代码片段，后面刷题时反复使用、反复修正。等这些基础写法足够熟，再去学枚举、模拟、贪心、搜索、动态规划，会顺很多。