数据结构与算法概览

这一课你将能做到

1. 说清楚数据结构与算法在编程中的位置和作用
2. 理解在线判题系统的基本流程：提交 → 编译 → 运行 → 比对结果
3. 写出第一个能 AC（Accepted）的 Java 程序

为什么要学

数据结构与算法是程序员的内功。你写的每一行业务代码——从数据库查询到缓存设计——底层都是它们在支撑。不会数据结构，遇到性能问题只能干瞪眼；不会算法，面试连第一轮都过不去。

人话：数据结构是「怎么存数据」，算法是「怎么处理数据」。就像做菜，数据结构决定你用碗、盘还是锅装食材，算法决定你是炒、煮还是蒸。

先建立图像

在线判题系统的工作流程：

你的代码 ──→ 判题服务器 ──→ 编译 ──→ 运行测试用例 ──→ 比对输出
                ↑                                    ↓
           时间限制 2s                          内存限制 256MB

一个最简单的 A+B 问题：

输入: 1 2
输出: 3

跟着做

步骤 1：认识判题输入输出

本站判题使用标准输入输出（stdin/stdout）。Java 中读取输入用 Scanner 或 BufferedReader，输出用 System.out.println。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a + b);
    }
}

步骤 2：处理多组测试数据

很多题目有多组输入，读到文件末尾为止：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(a + b);
        }
    }
}

步骤 3：高性能输入输出

数据量大时（10^5 以上），必须用 BufferedReader 和 StringBuilder：

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String line;
        while ((line = br.readLine()) != null && !line.isEmpty()) {
            StringTokenizer st = new StringTokenizer(line);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(a + b).append("\n");
        }
        System.out.print(sb);
    }
}

BufferedReader 每次读一行，StringTokenizer 按空格分割，比 Scanner 快 5-10 倍。

步骤 4：了解判题状态

提交后可能出现的状态：

状态	含义
AC (Accepted)	通过所有测试用例
WA (Wrong Answer)	输出结果错误
TLE (Time Limit Exceeded)	超出时间限制
MLE (Memory Limit Exceeded)	超出内存限制
RE (Runtime Error)	运行时崩溃（如数组越界）
CE (Compile Error)	编译失败

步骤 5：本地模拟判题

把测试数据保存到文件 input.txt，用重定向测试：

javac Main.java
java Main < input.txt

步骤 6：提交到本站判题系统

点击题目页的「提交」按钮，粘贴代码，选择 Java 17，等待判题结果。

步骤 7：常见输入格式速查

// 读 n 个数
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

// 读 n 行，每行两个数
for (int i = 0; i < n; i++) {
    int a = sc.nextInt();
    int b = sc.nextInt();
}

// 读字符串
String s = sc.next();

// 读到文件末尾
while (sc.hasNext()) { ... }

讲清楚要点

1. 标准输入输出是桥梁：判题系统不关心你的代码长什么样，只关心输入输出是否符合预期。
2. 时间就是金钱：本站默认 2 秒时限，Java 大约能执行 10^8 次基本操作。超过这个量级就要优化算法。
3. 内存是硬约束：256MB 大约能开 5000 万个 int。开太多会直接 MLE。
4. 边界数据是杀手：判题系统专门构造极端数据（空输入、最大输入、重复数据），必须考虑周全。

你可能会懵的地方

• Scanner 和 BufferedReader 用哪个？ 数据量小（<10^5）用 Scanner 就行；数据量大必须用 BufferedReader，否则 TLE。

• 为什么本地对了，提交就 WA？ 多半是没处理多组输入，或者输出格式多了空格/换行。

• Java 的 int 够用吗？ int 范围约 ±21 亿。如果结果可能超过，要用 long。

• Main 类名必须叫 Main 吗？ 是的，本站判题系统要求主类必须是 public class Main。

• 静态方法和实例方法有区别吗？ 判题场景下没区别，直接全部用 static 更省事。

错法对照

错法	问题	正解
只读一组数据就结束	多组数据题目 WA	用 while (sc.hasNext()) 循环读
输出多余的提示文字	判题系统比对的是精确输出	只输出题目要求的内容
用 int 存大数	溢出导致 WA	预估范围，必要时用 long
数组开太小	越界 RE	按题目给的最大范围开数组
递归太深	栈溢出 RE	改迭代或增大 JVM 栈空间

卡点急救

1. TLE 了：先把 Scanner 换成 BufferedReader，再把 System.out.println 换成 StringBuilder 攒起来一次输出。
2. WA 了：检查边界条件——n=0、n=1、所有数相同、所有数递增/递减。
3. RE 了：检查数组是否越界、除数是否为 0、递归深度是否超过 10^5。

面试常问

• 数据结构和算法为什么重要？ 数据结构决定存储效率，算法决定计算效率。两者共同决定程序能否在有限资源内解决问题。

• 在线判题系统的核心设计是什么？ 沙箱隔离（安全）、资源限制（公平）、多测试用例（正确性）、自动比对（效率）。

• Java 在判题中的优劣势？ 优势：生态丰富、内存安全；劣势：启动慢、常数大。需要更注意 IO 优化。

自测三问

1. 判题系统如何判断你的程序是否正确？
2. 为什么 Scanner 在数据量大时会导致 TLE？
3. Java 中 int 和 long 的取值范围分别是多少？

小结一句话

数据结构与算法是编程的地基，判题系统是检验地基的试金石；掌握标准输入输出和常见判题状态，就迈出了刷题第一步。

延伸

• Oracle Java 官方文档
• 下一课：基本数据结构——数组、链表、栈、队列、哈希表。