当前位置：首页 > article >正文

OJ (在线判题) Java 提交避坑总结，持续补充

article 2024/10/26 19:29:54

文章目录

提交格式
输入
多实例
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);
    }
}