OJ (在线判题) Java 提交避坑总结,持续补充
文章目录
- 提交格式
- 输入
- 多实例
- Scanner 优化
- 避免循环中创建对象
- 避免超时
- 避免内存超限
- 避免大数溢出
- 遵循格式输出
提交格式
无需 package 关键字,但需要 import
import java.util.Date;
public class Main {
public static void main(String[] args) {
System.out.println(new Date());
}
}
具体要看平台和题目的要求,LeetCode Problem 1 (Two Sum) 要求格式如下
class Solution {
public int[] twoSum(int[] nums, int target) {
}
}
输入
字符串输入尽量用 next(),而不是 nextLine()
避免 next()、nextXxx() 和 nextLine() 混用,尤其是在 next() 或 nextXxx() 后使用 nextLine(),会导致变量赋值错误
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入:line1、line2、line3
String s1 = sc.next();
String s2 = sc.nextLine();
String s3 = sc.next();
System.out.println(s1); // line1
System.out.println(s2); // 空串,期望是 line2
System.out.println(s3); // line2,期望是 line3
}
}
s2 读取了 s1 输入内容的换行,导致赋值错位
解决方法 1
对于 String,s2 改用 next()
String s1 = sc.next();
// String s2 = sc.nextLine();
String s2 = sc.next();
对于其它基本数据类型,比如 int,用 Integer.parseInt 包装
// int n = sc.nextInt();
int n = Integer.parseInt(sc.nextLine());
String s = sc.nextLine();
同理,对于有包装类的数据类型,格式如下
包装类.parseXxx(sc.nextLine())
解决方法 2
String s1 = sc.next();
// 读取并丢弃输入缓冲区中的剩余内容,通常用于处理换行符
sc.nextLine();
String s2 = sc.nextLine();
解决方法 3
String s = sc.nextLine();
String[] split = s.split(" ");
int n = split[0];
String s1 = split[1];
String s2 = split[2];
一行接收全部参数
多实例
1.指定测试用例数量
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
// TODO
}
}
}
2.不指定测试用例数量(处理 EOF)
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
// TODO
}
}
}
Java 终端是 Ctrl + D 结束程序,而不是 Ctrl + C
3.不指定测试用例数量,但以某标识结束,比如 0 或 END
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
int n = sc.nextInt();
if (n == 0) break;
// TODO
}
}
}
另一种写法
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n;
while ((n = sc.nextInt()) != 0) {
// TODO
}
}
}
Scanner 优化
Scanner 和 System.out.println 的使用比较方便,但它们在处理大量输入输出时速度较慢,可能导致超时(TLE: Time Limit Exceeded)
优化输入:BufferedReader
BufferedReader 比 Scanner 快得多,尤其是在处理大量输入时
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int n = Integer.parseInt(line);
// 接下来的逻辑处理
}
}
优化输出:BufferedWriter
BufferedWriter 的输出比 System.out.println() 要快,因为它使用了缓冲机制,可以减少系统调用
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write("Hello World\n");
bw.flush(); // 必须调用 flush,确保输出被打印
}
}
进一步优化:PrintWriter
PrintWriter 提供了一种灵活且高效的输出方式,且不需要手动调用 flush()
import java.io.PrintWriter;
public class Main {
public static void main(String[] args) {
PrintWriter out = new PrintWriter(System.out);
out.println("Hello World");
// OJ 中通常不需要手动 flush 或 close,PrintWriter 默认支持自动刷新
out.close();
}
}
避免循环中创建对象
在 OJ 中频繁创建对象(如在循环中创建 Scanner 或 StringTokenizer)会导致性能问题
解决方法:尽量在循环外创建一次对象,循环内部重复使用
while (t-- > 0) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 处理逻辑...
}
改进后
Scanner sc = new Scanner(System.in);
while (t-- > 0) {
int n = sc.nextInt();
// 处理逻辑...
}
避免超时
Java 的算法运行时间比 C/C++ 慢不少,因此选择合适的算法和数据结构尤为重要
(1) 使用合适的数据结构
数组:访问速度快,适合在已知数据范围固定的情况下使用。但对于 OJ,避免动态扩展数组的操作。
HashMap 和 HashSet:在 OJ 中非常有用,查找和插入的时间复杂度为 O(1),适合处理大量无序数据。
TreeMap 和 TreeSet:按顺序存储元素,时间复杂度为 O(log n),适合处理需要顺序存储的数据。
(2) 双指针与滑动窗口
当需要处理数组或字符串的子区间时,双指针和滑动窗口技术可以避免重复计算,减少时间复杂度。
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int left = 0, right = 0, sum = 0;
int target = 9;
while (right < arr.length) {
sum += arr[right++];
while (sum > target) {
sum -= arr[left++];
}
if (sum == target) {
System.out.println("Found subarray");
break;
}
}
}
}
避免内存超限
OJ 系统通常会对内存使用设置严格的限制,尤其是处理大数据集时,容易出现内存溢出。以下是常见的内存优化方法:
(1) 使用基本数据类型
Java 中的基本类型(如 int、long)相比包装类(如 Integer、Long)占用更少的内存,且运算更快。应尽量避免使用 List,而优先选择基本类型的数组 int[ ]
(2) 避免不必要的对象创建
在 OJ 系统中,大量对象的创建和垃圾回收会导致内存和时间浪费。因此,尽量复用对象,减少临时对象的生成
(3) 用 StringBuilder 处理字符串
当需要频繁操作字符串时,使用 StringBuilder 代替 String,避免因字符串不可变特性导致大量临时对象的创建
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 100; i++) {
sb.append(i).append(" ");
}
System.out.println(sb.toString());
避免大数溢出
在处理涉及大量数字的题目时,要注意防止整数溢出。Java 中的 int 最大值为 2^31-1,当值可能超出这个范围时,应使用 long 类型。此外,某些题目可能需要使用 BigInteger 来处理非常大的数
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
BigInteger a = new BigInteger("12345678901234567890");
BigInteger b = new BigInteger("98765432109876543210");
BigInteger result = a.add(b);
System.out.println(result);
}
}
遵循格式输出
OJ 系统对输入输出格式有严格要求,输出时应按照题目描述精确打印。例如:
- 浮点数的输出精度,保留 n 位小数
- 输出格式中的空格、换行符位置
- 注意区分大小写,如 Yes、YES、No、NO