★ FEATURED ARTICLE 刷题刷到一定阶段你就会发现一个绕不开的坎ACM模式。这个词在Java面试题和算法题库里反复出现很多在IDE里写惯了LeetCode式核心代码的朋友第一次在笔试系统里碰见要自己处理输入输出的题目时当场就懵了。键盘倒是敲了结果连第一行数据怎么读进来都没搞明白。ACM模式说白了就是要求你自己搭好程序的“大门”和“出口”——从标准输入读数据往标准输出写结果。它是算法竞赛的遗产如今也是各大笔试平台的主流考察方式。这篇文章就是把ACM模式下Java选手必会的那些点掰开揉碎讲清楚各种输入输出写法怎么选、Scanner凭什么慢、快读模板怎么背、高频算法模板怎么套、边界条件在哪挖坑。无论你是准备春招秋招还是刚开始刷题这一篇都能当你的案头手册。1. 先搞明白ACM模式到底考你什么1.1 核心代码模式与ACM模式的本质区别LeetCode那种给你把函数签名、参数类型、返回值都定死的写法叫核心代码模式。你只需要实现函数体测试数据由平台自动传进来断言由平台自动比对。这种模式对新手友好因为它帮你屏蔽了“程序如何与测试环境交互”这件事。ACM模式则是另一套玩法平台把测试数据放在一个个文件里运行时重定向到你的程序标准输入你的程序读入、计算再把结果打到标准输出平台拿你输出的文本和答案文件做逐字符比对。这意味着输入格式解析、多组用例循环、输出格式控制全都算你代码的一部分。任何一个环节出了偏差哪怕算法思路完全正确也是零分。实际面试时很多公司用自家笔试系统虽然界面长得像LeetCode但要求的却是ACM模式。原因也简单ACM模式更接近真实工程里“从外部数据源读取、处理、输出”的工作流能考察考生对数据流的理解和对边界情况的敏感度。我见过不少算法水平不差的人面试挂在简单题上不是因为不会算而是因为没读明白“第一行是一个整数N”这句话。1.2 一个最简单例子的完整数据流拿最经典的“ab问题”来说ACM模式下的完整程序长这样import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); while (in.hasNextInt()) { int a in.nextInt(); int b in.nextInt(); System.out.println(a b); } in.close(); } }这个例子看着简单但信息量很大类名必须叫Main这是绝大多数OJ平台和笔试系统的硬性要求。类名错了直接编译失败属于低级且致命的失误。hasNextInt()是在等待输入流中还有没有下一个整数常见于“多组测试数据每行两个整数读到文件末尾结束”的题目描述。System.out.println()每执行一次会输出一行并换行正好匹配题目要求的“每个结果占一行”。如果题目说“第一行是测试用例组数T接下来T行数据”那就得改成先读T再循环T次而不是用hasNextInt()死循环。理解了这个最基础的数据流形态后面所有复杂输入输出都是它的变体。这也是我强烈建议每个新手把Scanner里常用方法背熟的原因——不是因为它性能好而是它语义直观适合让你在起步阶段摸清“读一行、读一个词、读一个数”的区别。2. Java读入方式选型Scanner、BufferedReader与自写快读2.1 Scanner为什么慢以及什么时候可以用Scanner的便捷性毋庸置疑nextInt()读整数nextDouble()读小数next()读单词nextLine()读整行遇到空白字符自动跳过。它的工作原理是先用正则表达式对输入流做模式匹配再逐个解析token。正则带来的开销加上每个token都走一次解析流程导致它在海量数据下慢得离谱。实测过一种常见情况10万条数据每行5个整数Scanner完整读下来大约需要几百毫秒到1秒多而BufferedReader配合字符串切割通常能把时间压缩到几十毫秒。数据量翻倍后差距会进一步拉大。笔试平台普遍有1到3秒的时间限制如果题目数据量大你用了Scanner可能在读写阶段就已经把预算耗掉一大半留给算法的余量就很少了。所以我的建议是分场景数据量小比如几百行或者你只是本地写个小工具Scanner完全没问题。数据量中等或不确定优先用BufferedReader 字符串split。数据量明确很大题目说N最大到10^5、10^6直接上带缓冲的自定义FastReader。2.2 BufferedReader的读法和它好在哪里BufferedReader的思路是“先把一大块数据从磁盘搬进内存缓冲区再按需从缓冲区取字符”。它避免了频繁触发底层IO这是它快的根本原因。用它的标准姿势是配InputStreamReaderBufferedReader br new BufferedReader(new InputStreamReader(System.in)); String line br.readLine();readLine()返回的是去掉换行符的整行字符串接下来怎么解析就看你手里有什么牌。行内多个整数可以用StringTokenizer也可以用split( )。很多老手偏爱StringTokenizer因为它在“只关心取第几个token”的场景下更直观而且不产生额外数组性能略优。下面两种写法都常见StringTokenizer st new StringTokenizer(br.readLine()); int a Integer.parseInt(st.nextToken()); int b Integer.parseInt(st.nextToken());String[] parts br.readLine().split( ); int a Integer.parseInt(parts[0]); int b Integer.parseInt(parts[1]);split的正则是编译好的处理一行几十个字段完全够用。我自己的习惯是字段少用split字段多且层次复杂才考虑StringTokenizer可读性优先。2.3 自写FastReader模板什么时候值得上如果你打比赛或者刷题量大强烈建议在本地维护一个FastReader类随取随用。它结合了BufferedReader的缓冲能力和StreamTokenizer的解析速度也能避免重复造轮子。我常用的模板长这样import java.io.*; import java.util.StringTokenizer; class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st null || !st.hasMoreTokens()) { try { st new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine() { String str ; try { str br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } }这几个方法分别对应整数、长整数、浮点数、整行的读取。需要注意nextLine()和next()混用时如果前面刚用nextInt()再调nextLine()可能读到空字符串因为nextInt()不会吞掉行尾的换行符。这是经典的坑我在第3章会展开讲。StreamTokenizer是另一个方向它直接对字符流做词法分析跳过空白识别数字。用起来稍微绕但性能确实猛。下面的代码演示了怎么读两个整数StreamTokenizer tokenizer new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); tokenizer.nextToken(); int a (int) tokenizer.nval; tokenizer.nextToken(); int b (int) tokenizer.nval;实战中FastReader已经够用StreamTokenizer因为要手动管理nextToken()调用写复杂题时容易漏掉反而不如FastReader稳。快读的本质就是降低IO等待时间不是让你炫技。稳定性优先。2.4 输出端的取舍与正确姿势输出同样有讲究。System.out.println()每次调用都会触发一次输出操作在循环里频繁调用性能跟Scanner配一脸都属于“慢速通路”。三种常见改法把要输出的内容拼接成一个大字符串最后一次性println。适合输出量中等的情况。用StringBuilder累计循环结束后一次性输出。这个最常用也好控制格式。用BufferedWriter包裹OutputStreamWriter每次write()数据最后flush()。适合超大输出的情况。StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { sb.append(result[i]).append(\n); } System.out.print(sb);BufferedWriter bw new BufferedWriter(new OutputStreamWriter(System.out)); for (int i 0; i n; i) { bw.write(String.valueOf(result[i])); bw.newLine(); } bw.flush();这两种我都常用。后缀带\n拼接的方式适合“每行一个数”BufferedWriter适合“输出内容本身是长文本、需要精确控制换行”的场景。注意flush()别忘了忘了的话数据可能滞留在缓冲区里平台那边等到超时才收到你的输出一样判错。3. 高频输入场景实战行内多值、矩阵、不定行数与EOF3.1 单行多值的两种解析法笔试里最常出现的就是“一行两个整数”或者“一行三个整数”。比如输入N M代表节点数和边数。解析方式就看你用了哪个读取器Scanner模式下int n in.nextInt(); int m in.nextInt();FastReader模式下int n in.nextInt(); int m in.nextInt();表面上看一模一样因为FastReader仿的就是Scanner的API。区别在于底层实现前者走正则解析后者走StringTokenizer。如果题目给的是“一行可以有很多个整数数量不确定但保证不超过某个范围”这时可以读整行再处理String[] parts br.readLine().trim().split(\\s); int[] arr new int[parts.length]; for (int i 0; i parts.length; i) { arr[i] Integer.parseInt(parts[i]); }trim()去掉首尾空白split(\\s)按一个或多个空白字符切分能兼容空格和Tab。这个写法在处理“数组长度在下一行给出”时很实用因为你能先把长度读了再按长度初始化数组再来一行把数据填进去。3.2 矩阵读入固定行数与不确定行数矩阵类题目比如迷宫、动态规划表格、图像处理输入格式一般是“第一行两个整数R和C表示行数和列数接下来R行每行C个整数”。代码模板int r in.nextInt(); int c in.nextInt(); int[][] matrix new int[r][c]; for (int i 0; i r; i) { for (int j 0; j c; j) { matrix[i][j] in.nextInt(); } }这里有个细节有些题目的矩阵元素之间用空格分隔有些题目是连续字符串比如001010这种还有些是字符矩阵。字符串矩阵的处理方式不同逐行读字符串后转成char数组char[][] grid new char[r][c]; for (int i 0; i r; i) { String line br.readLine(); grid[i] line.toCharArray(); }如果每行是101010这种0/1串你需要在读入后手动把字符0、1换算成整数0、1。别直接拿char去做数值运算否则你会得到ASCII码值排查半天才发现全错在48这个偏差上。还有一种“直到EOF才结束”的矩阵输入常见于图像处理的题不告诉你行列数只告诉你每行是一组数据读完为止。这时要边读边记录行数动态扩展。我建议用ArrayList暂存等读完了再统一转二维数组避免频繁扩容二维数组。3.3 不定行数与EOF判断的各种情形EOFEnd Of File是输入流的终点。笔试平台重定向输入文件后程序读完最后一个字节再读就会遇到EOF。Scanner里对应hasNext()、hasNextInt()BufferedReader里对应readLine()返回null。场景一多组输入每组格式相同读到EOF结束。while (in.hasNext()) { int a in.nextInt(); int b in.nextInt(); // 处理 }场景二第一行一个整数T代表组数后面T组数据。int t in.nextInt(); for (int i 0; i t; i) { // 处理每一组 }场景三每组第一行是“接下来要处理几个数”读到0表示结束。这类题目很多比如某些排序题、合并区间题。循环条件要这样写while (in.hasNextInt()) { int n in.nextInt(); if (n 0) break; // 继续读n个数 }场景四纯字符串行读到一行是特定标记比如#或end就停止。这时用readLine()判断String line; while ((line br.readLine()) ! null) { if (line.equals(end)) break; // 处理line }这个模式一定要记牢while ((line br.readLine()) ! null)。它兼顾了“读到EOF”和“遇到特殊行终止”两种需求。3.4 nextInt与nextLine混用为什么会出鬼故事很多新手在准备笔试时都撞上过这个诡异现象明明输入的是2 hello world代码先int n in.nextInt()再String s in.nextLine()结果读出来的是空字符串。原因是nextInt只读取了2这个token输入流里剩下的换行符\n还留在那里紧接着的nextLine直接把空行读走了于是程序看起来像“跳过了一行”。三个解决办法在nextInt之后主动吃掉换行in.nextLine()然后再读真正的下一行。全部统一用nextLine读整行自己解析数字。这种方法最适合混合数字和字符串的场景。用FastReader时同样要小心nextInt()和nextLine()混用也有这个坑。我印象最深的一次翻车是某场模拟笔试里有道题需要边读边判断字符串中是否含某个子串。我写int type in.nextInt(); String name in.nextLine();结果所有字符串都读成了空串整个过程还以为是算法错了排查了半天才注意到是nextLine吞了换行。从那以后凡是涉及“先数字后字符串”的输入我都老老实实先多写一行in.nextLine()把残留换行吃干净。4. 常见算法在ACM模式下的Java实现4.1 归并排序的手写模板与调用思路归并排序是分治思想的经典代表也是笔试常考的“手写排序”答案之一。它的核心是把数组对半拆拆到单元素再把有序段两两合并。Java里Arrays.sort()底层是快速排序的变种但面试官就是想看你能否徒手实现一个稳定排序。public class MergeSort { private static int[] temp; public static void mergeSort(int[] arr) { temp new int[arr.length]; mergeSort(arr, 0, arr.length - 1); } private static void mergeSort(int[] arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } private static void merge(int[] arr, int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (i left; i right; i) { arr[i] temp[i]; } } }这里面藏着两个实用细节mid left (right - left) / 2是防止(leftright)溢出虽然Java的数组长度导致leftright很难溢出但养成好习惯总没错。合并时要先判断arr[i] arr[j]还是arr[i] arr[j]。等号决定了稳定性虽然排序纯数字时稳定性无所谓但在排序对象是对象数组时稳定性的语义差别会导致完全不同的结果。辅助数组temp先一次性分配好不要每次都new否则大量创建数组会拖慢效率。这也是归并排序手写优化的关键点。4.2 手写堆排序与PriorityQueue的区别堆排序考察点在于“建堆”和“调整堆”。手写它的时候很多人的痛点是分不清shiftUp和shiftDown容易在边界条件上写错。public class HeapSort { public static void heapSort(int[] arr) { int n arr.length; // 建大顶堆 for (int i n / 2 - 1; i 0; i--) { shiftDown(arr, i, n); } // 逐个交换 for (int i n - 1; i 0; i--) { swap(arr, 0, i); shiftDown(arr, 0, i); } } private static void shiftDown(int[] arr, int i, int n) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { swap(arr, i, largest); shiftDown(arr, largest, n); } } private static void swap(int[] arr, int i, int j) { int t arr[i]; arr[i] arr[j]; arr[j] t; } }笔试现场如果只是需要“得到前K个最大值”这种功能直接用PriorityQueue没必要手写堆PriorityQueueInteger minHeap new PriorityQueue(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() k) { minHeap.poll(); } }PriorityQueue默认是小顶堆想变成大顶堆要传比较器Collections.reverseOrder()。这里有个容易被坑的点PriorityQueue的迭代器不保证顺序如果你把它直接toString打印出来看到的不是有序排列而是堆的层次结构很多新手会误以为堆坏了。手写堆和PriorityQueue到底选哪个我的建议是面试官明确让你手写堆排序时老老实实写堆排序题目只是借用堆的特性直接用PriorityQueue省时间去做算法主逻辑。两种能力都得有但不能在考场上分不清轻重。4.3 KMP算法的标准Java写法KMP的热度一直很高因为字符串匹配在很多题目里是前置步骤。它的核心是next数组也就是“当前位置字符不匹配时模式串指针应该退回到哪里”。public class KMP { public static int[] buildNext(String pattern) { int m pattern.length(); int[] next new int[m]; int j 0; for (int i 1; i m; i) { while (j 0 pattern.charAt(i) ! pattern.charAt(j)) { j next[j - 1]; } if (pattern.charAt(i) pattern.charAt(j)) { j; } next[i] j; } return next; } public static int kmpSearch(String text, String pattern) { int[] next buildNext(pattern); int j 0; for (int i 0; i text.length(); i) { while (j 0 text.charAt(i) ! pattern.charAt(j)) { j next[j - 1]; } if (text.charAt(i) pattern.charAt(j)) { j; } if (j pattern.length()) { return i - j 1; } } return -1; } }这里特别容易出问题的是next[j - 1]和j的更新顺序。如果你发现自己写的KMP在某些匹配场景下死循环大概率是回退逻辑写成了j next[j]。next数组当前位置的含义是“当前字符之前的最长相等前后缀长度”回退时必须用next[j-1]。我自己也在这里栽过一次排查了很久才意识到是索引差一。字符串匹配如果不用KMPJava里直接用indexOf()也是可以的笔试不限制你用现成API。但面试聊到算法时你如果能讲清next数组的构建原理至少能说明你真正理解了字符串匹配的本质而不是只会调库。4.4 贪心、二分、DP在ACM模式里的核心要点高频算法不只是排序和字符串笔试里贪心、二分、动态规划出现的频率同样高。贪心算法最难的步骤是“证明局部最优能推导出全局最优”。ACM笔试里很多贪心题会给出“无法贪心反例存在”的干扰情况。比如区间调度问题经典解法是先按结束时间升序排列再贪心选择。选排序依据时一旦选错整个答案全盘皆输。这种题目的关键一眼就能看出来在纸上列两三个反例试一下自己的排序策略会不会翻车再动笔写代码。二分的代码框架在笔试中属于必须背熟的基础因为它变体多容易写错。标准模板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; }写二分最容易错的地方是循环条件是left right还是left right以及退出后是返回left还是right。我给自己定的规矩是查找某个确切值用left right查找“第一个大于等于target的位置”用left right退出后left就是答案。你自己需要一套固定的模板把变体从模板演化出来千万别每次现推。动态规划在ACM模式下读入和初始化同样重要。最经典的情况是“第一行N和M接下来M行每行是转移条件”。DP数组的边界初始化往往藏在输入格式里比如“数组下标从1开始”还是“从0开始”这直接决定了你的状态转移方程需不需要偏移。读题时第一件事就是在草稿纸上标注清楚下标范围。5. 边界、格式与环境的坑笔试前必须排查的细节5.1 数组越界的典型场景和自检方法数组越界是Java选手在ACM模式下的高频报错。通常是因为没考虑到下标边界循环里用i 1访问数组却没判断i n - 1。动态规划状态数组按n1大小申请但遍历时习惯从0开始导致越界。矩阵题里上下左右四个方向遍历不检查边界就访问邻居。我自己常用的防越界模板是方向数组配合坐标检查int[] dx {0, 1, 0, -1}; int[] dy {1, 0, -1, 0}; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx rows || ny 0 || ny cols) { continue; } // 处理邻格 }这套写法比单独写四个if分支要干净得多而且不容易漏边界。在做岛屿数量、迷宫搜索这类题时它是标准模板。5.2 输出格式错误多空格、少换行与行尾多余输出格式的判定是逐字符的。以下三类错误最常见多打了行尾空格。比如你用for循环打印数组每个元素后面都跟一个空格最后一行末尾就多了一个平台判错。解决办法是前n-1个元素打印元素 空格最后一个元素单独输出换行。少换行。题目要求“每个结果占一行”结果你用了System.out.print所有结果挤在一行里。空行数量不对。有些题目在多个用例之间要求空行有些则不要求。读题时一定要看清楚。我踩过最典型的一次是输出一行里既是“Case #x: y”格式又要在每组后额外空行。题面英文描述里有个“blank line between cases”我忽略了关键词结果格式分全扣算法正确也没用。自检方法很简单拿到样例输入后把程序输出的每个字符和样例输出逐字节比对。用System.out.print(Arrays.toString(arr))这类调试输出没事但提交前务必删掉。5.3 常见Java环境问题和本地配置陷阱热词里出现了很多“java环境变量配置”“源发行版17需要目标发行版17”这类问题。这些虽然不算算法内容但笔试前如果环境没配好直接在编译阶段就挂了非常冤。“警告: 源发行版 17 需要目标发行版 17”这类信息出现时说明本地Java编译级别跟IDE的语言级别不一致。要么你装的是高版本JDK但项目设置的source/target还停留在较低版本要么恰恰相反。解决办法是统一项目SDK版本。命令行编译时可以用javac -source 17 -target 17 Main.java如果环境变量配过java -version能正常输出就说明JDK基本可用。笔试前最好确认三件事java -version能跑、javac能编译、默认编码是UTF-8某些平台对中文输出有编码要求。类名和文件名不一致的问题在OJ系统里通常会直接判编译错误所以Main类名一定要记牢。5.4 现场自测的步骤不管题目看起来多简单提交前都建议走一遍固定自测流程用题目给的样例输入跑一遍逐字比对输出。自己构造一个最小边界数据。比如N1、N0、数组长度为1、矩阵只有一行或一列。自己构造一个最大数据量的输入检查运行时长是否合理。检查输出末尾是否有正确换行是否有多余空格。检查核心循环里是否残留调试输出。很多新手挂在边界数据上不是因为想不到而是因为懒得动手构造。笔试时构造极端输入是个习惯问题练得多了自然就形成条件反射。尤其是“N0”这种情况一旦没处理有的代码直接越界崩溃有的代码输出错位。6. 构建自己的ACM模式Java工具箱6.1 把输入输出模板沉淀成自己的代码块你不可能每一道题都从头推断输入怎么处理。聪明做法是维护一套自己的模板平时刷题时不断打磨它让它成为肌肉记忆。我的编辑器里常年存着这几个模板FastReader类一套完整的nextInt/nextLong/nextDouble/nextLine方法。输出用的StringBuilder 一次性打印模板。处理“先数字后字符串”时的残留换行处理模板。矩阵方向遍历模板。归并排序、堆排序、KMP、二分查找的手写版本。这些东西不用背但要练到“看到题目输入描述马上知道用哪个模板”的程度。听起来很玄其实练多了就是条件反射看到“第一行一个整数T”就拿出组数循环模板看到“读到EOF”就拿出while hasNext模板看到“字符串矩阵”就拿出toCharArray模板。6.2 刷题中培养的两种关键能力ACM模式带给你最大的收获不是背会了多少模板而是培养了两种能力第一种是把把杂乱的输入文本在脑内还原成结构化数据的能力。题目说“每行三个整数分别代表城市、目的地、花费”你要能立刻联想出一组三元组数据想清楚后面算法需要的是什么数据结构。第二种是主动构造边界用例的能力。写工程代码时你天然能容忍一些健壮性问题因为用户可能不会输入极端数据但在ACM模式下测试用例专门挑边界打所以你必须自己先想一遍最极端的情况。我见过太多算法能力不差的人倒在了读题和输入输出的细节上。考完后一看题解拍大腿说自己“思路全对就是没读明白输入”。这种遗憾明明可以避免就看你在刷题时有没有刻意练习“从输入到代码”的完整链路。6.3 最终建议从今天开始每道题都用ACM模式练如果你还在用核心代码模式刷题建议从今天开始切换成自建Main 标准输入输出的方式。刚开始会觉得很麻烦连读一个数组都要写好几行但坚持十道题以后你会发现自己对“数据如何流进程序”有了新的理解。这种理解能让你在笔试时更镇定在面试聊系统设计时也更清楚数据入口在哪。我个人在无数次踩坑之后养成的习惯是拿到任何一道题先花30秒扫一眼输入输出说明在草稿纸上写清楚“有几行数据、每行几个字段、以什么分隔、有没有EOF、输出时需要什么格式”然后才动代码。这30秒看起来不起眼却能避免绝大多数格式类翻车。ACM模式下的Java知识远不止输入输出但输入输出是你和判题系统对话的唯一方式。把这条链路打通剩下的才能拼算法、拼数据结构、拼临场心态。希望这份从实战里总结出来的经验能让你下一次打开笔试系统时心里多一分笃定少一分手忙脚乱。
阅读完成 · 觉得有帮助？
