1. 整体思路工程代码和竞赛代码到底差在哪1.1 为什么工程开发者看竞赛题解会觉得别扭我一直有个感受做过几年Java后端再回头刷算法题第一反应不是这题不会做而是同样的功能为什么竞赛选手的写法让我不认识了。举个很常见的例子。你在业务代码里往HashMap里塞一个List惯用写法一定是先判断key存不存在MapString, ListInteger map new HashMap(); if (!map.containsKey(key)) { map.put(key, new ArrayList()); } map.get(key).add(value);这套逻辑写起来顺手读起来也清楚。但竞赛选手一行就搞定了map.computeIfAbsent(key, k - new ArrayList()).add(value);函数式接口、lambda、默认方法全都怼在一起。不是说它装而是竞赛场景里每一行代码都在为代码量和可读性之间找平衡整个编码习惯和工程开发完全不是一套思维模式。好在这篇文章不是教你打比赛而是站在工程开发者的视角把竞赛里最常用的Java数据结构和操作整理成一份助记版笔记。你不需要为了刷题去改变自己多年的工程习惯只需要建立一张映射表这个常见需求在竞*赛代码里通常怎么写背后用到了哪个类的哪个方法边界条件在哪。理解了这个对应关系再去看题解代码障碍就消掉了一大半。1.2 Java在算法竞赛里的优劣势Java在算法竞赛里其实是能打但不占便宜的语言。优势在于容器类库非常完善HashMap、TreeMap、PriorityQueue都是开箱即用比C的STL某些时候还直观劣势在于常数比较大同样一个O(NlogN)的排序C可能跑0.5秒Java跑到1秒出头很正常再加上JVM启动时间线上比赛的体验确实不占优。但换个角度看Java刷算法题有一个工程开发者无法拒绝的理由面试要考。现在大厂的技术面试圈子里白板写题的主流语言就是Java用Java刷题等于把面试语言、工程语言、刷题语言统一成了一种切换成本最低。而且Java的容器类在工程代码里也普遍使用多熟悉一层竞赛场景的用法对写业务代码里的复杂逻辑也有帮助。1.3 助记的核心原则整理这份笔记时我给自己定了三条原则按操作需求分类而不是按类名硬记。比如需要有序的键值对对应TreeMap需要自动排序的队列对应PriorityQueue先有需求再找工具而不是反过来背API。工程写法和竞赛写法做对照。每个操作都给出两种写法你只要曾经写过工程代码就能从对照中快速理解竞赛写法的来源。把时间复杂度放在最显眼的位置。竞赛代码的核心是在规定时间内跑完任何一个数据结构的选择都跟复杂度强相关这个思维必须建立起来。下文所以内容都用Java 8的语法这也是目前线上算法题环境最通用的版本。2. 容器类竞赛里高频操作的速记手册2.1 ArrayList不只是自动扩容的数组ArrayList在工程开发里是List接口的默认实现大多数人拿它当可变的数组用。在竞赛场景里它的角色其实更微妙因为竞赛题绝大多数是静态数据读入后就不再增删理论上用原生数组是最快的但原生数组不方便扩容、不方便传参、没有丰富的方法所以ArrayList反而成了高频妥协方案。竞赛中几个容易忽视的ArrayList操作// 排序 ListInteger list new ArrayList(); Collections.sort(list); // 升序 Collections.sort(list, Collections.reverseOrder()); // 降序 // 列表间批量添加 list.addAll(otherList); // 转为数组注意参数是new Integer[0]不是new Integer[n] Integer[] arr list.toArray(new Integer[0]); // 需要注意list.toArray()返回的是Object[]直接强转会报错这里有个真正值得记住的点toArray(new Integer[0])这个写法不少工程开发者会写成list.toArray(new Integer[list.size()])性能上是前者更好。原因在JVM的优化机制——new Integer[0]只需要一个空数组做类型标记JDK内部判断后直接新建正确大小的数组返回逻辑更清爽。还有ensureCapacity这个方法平时几乎没人用。但如果你提前知道最终容量比如读数据时已经知道行数调用list.ensureCapacity(n)可以避免中间多次扩容的数组拷贝。数据量上了百万以后这个微优化在竞赛场景里能省下几十毫秒值得养成习惯。ArrayList和LinkedList的选择也是竞赛新手最容易纠结的。我把结论说透绝大多数情况下选ArrayList。LinkedList的随机访问是O(N)在需要按下标操作的题里完全没法用而ArrayList哪怕是做头部插入如果数据量小也看不出差别数据量大时LinkedList的节点对象本身又吃内存。真正需要使用Deque双端队列语义时用ArrayDeque不要用LinkedList。2.2 HashMap默认方法才是竞赛的灵魂HashMap在工程开发里最常用的就是put、get、containsKey、size这几个。但在竞赛代码里几个Java 8引入的默认方法才是真正拉高效率的地方它们能把三行样板代码缩成一行而且语义清晰。我列一下刷题中出镜率最高的三个computeIfAbsent(key, mappingFunction)key不存在时才执行函数并放入返回当前key对应的值。最常用于分组、建邻接表。// 需求把每个节点的邻接节点塞进列表 MapInteger, ListInteger graph new HashMap(); for (int[] edge : edges) { graph.computeIfAbsent(edge[0], k - new ArrayList()).add(edge[1]); graph.computeIfAbsent(edge[1], k - new ArrayList()).add(edge[0]); }merge(key, value, remappingFunction)key不存在时放入value存在时用函数合并。最经典的是计数。// 需求统计每个字符出现次数 MapCharacter, Integer count new HashMap(); for (char c : s.toCharArray()) { count.merge(c, 1, Integer::sum); }getOrDefault(key, defaultValue)有值取值无值取默认值。这句其实在JDK 8之前就有但竞赛里很多选手依然习惯先判断再取其实一行能搞定。还有一个细节很多人踩坑HashMap的遍历顺序是无序的。如果你需要按插入顺序或访问顺序遍历要用LinkedHashMap如果确信数据量很小比如不超过100个keyHashMap和LinkedHashMap的性能没有本质差别但LinkedHashMap能帮你省掉调试时为什么顺序不对的烦恼。在竞赛里HashMap最常见的场景是去重和计数。去重完全可以用HashSet但计数需要HashMap。这里有个工程开发者也容易忽略的特性HashMap的key如果是自定义对象必须同时重写hashCode和equals否则查不到也是正常的。竞赛中为了避开这个坑绝大多数人会把key设计成String、Integer这些基础包装类——这也是为什么你看题解代码时他们总是在绕着弯子把复杂对象转成字符串再塞进Map。2.3 TreeMap和TreeSet有序性的威力TreeMap和TreeSet的核心能力是键有序底层红黑树所有操作O(logN)。竞赛题中只要出现找比某个数大的最小值或找比某个数小的最大值这类最近邻查询这几个类就是标准答案。TreeMap的常用方法TreeMapInteger, String map new TreeMap(); map.firstKey(); // 最小的key map.lastKey(); // 最大的key map.ceilingKey(5); // 大于等于5的最小key没有返回null map.floorKey(5); // 小于等于5的最大key没有返回null map.higherKey(5); // 严格大于5的最小key map.lowerKey(5); // 严格小于5的最大key记住ceiling是向上取取的是不小于给定值floor是向下取取的是不大于给定值。中文翻译成天花板和地板就很好记了。这一组方法在处理区间合并、滑动窗口、日程冲突检查区间是否重叠时特别好用。TreeSet和TreeMap用法对称只是没有value。比如说维护一个有序集合随时取出最大/最小元素并删除TreeSet可以做到TreeSetInteger set new TreeSet(); set.add(10); set.add(3); set.add(7); int max set.last(); // 10 set.remove(set.last()); // 移除最大 int min set.first(); // 3和PriorityQueue不一样的是TreeSet不止能取最值还能查询在集合中哪个范围内的元素这是堆做不到的。代价是插入和删除的常数比堆略大一些。2.4 PriorityQueue默认是小顶堆这一点别记反PriorityQueue这个类名特别容易被工程开发者想当然Priority不是优先级吗那不应该是大的先出不对Java的PriorityQueue默认是小顶堆也就是值最小的元素在队头。这个点我见过太多人搞反一写就错。自定义顺序有两种方式。一种是用Collections.reverseOrder()// 大顶堆 PriorityQueueInteger maxHeap new PriorityQueue(Collections.reverseOrder());另一种是自己实现Comparator// 小顶堆默认 PriorityQueueInteger minHeap new PriorityQueue(); // 自定义比如按绝对值大小 PriorityQueueInteger absHeap new PriorityQueue((a, b) - Math.abs(a) - Math.abs(b));堆在竞赛里的出场频率极高TopK问题、合并K个有序链表、Dijkstra、Prim、任务调度等等全都是堆的经典应用。核心操作就三个offer入堆、poll出堆头、peek看堆头全部O(logN)。工程开发者和竞赛选手在堆的思维上一个很大的差异是工程开发者倾向完整实现一个类竞赛选手习惯只关心数据进出顺序。举一个高频的TopK写法// 求数组里最大的K个数维护一个大小为K的小顶堆 PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : nums) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } // 堆里剩下的就是最大的K个数注意堆里的元素数量如果一直没超过K不需要poll只有超过或者peek值比当前数小才更新。这个题用大顶堆也能做但复杂度高因为得把全部数据都放进堆再来K次poll用小顶堆每次只淘汰堆内最小的最终堆里留着最大的K个两者相比差距就出来了。3. 字符串、数组与类型转换竞赛里最常见的暗坑3.1 StringBuilder字符串操作的第一选择Java里的String是不可变的所以循环里直接拼字符串等于每拼一次都创建一个新对象O(N^2)的时间逃不掉。这个话我在工程代码评审里讲过无数遍在竞赛场景里更是致命的——数据量一大TLE超时就来了。竞赛里StringBuilder的最高频场景有三个第一是拼接StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { sb.append(arr[i]); } String result sb.toString();第二是反转。String本身没有reverse方法StringBuilder有String reversed new StringBuilder(s).reverse().toString();注意reverse()是反转整个字符序列不是反转单词顺序两者别搞混。第三是修改某个位置的字符。String这个操作几乎做不了——要转字符数组再改再转回String而StringBuilder直接用setCharAtsb.setCharAt(i, x);这里我再多提醒一句StringBuilder的初始容量默认是16如果提前知道要累积大量内容构造时传入初始容量比如new StringBuilder(totalLength)能省掉扩容时内部数组拷贝的开销。这个和ArrayList的ensureCapacity是同一个思路。3.2 字符串与数值转换的几种写法竞赛题里把数字字符串转成int或者把int变成字符串这种操作太频繁了但写法上有几个易错的细节。字符串转数字String s 12345; int a Integer.parseInt(s); // 推荐 long b Long.parseLong(s); // 用long接更大范围 // 二进制解析 int bin Integer.parseInt(1010, 2); // 10数字转字符串int num 123; String s1 Integer.toString(num); String s2 String.valueOf(num); String s3 num ; // 能用但不优雅而且会在循环里产生额外对象字符串转字符数组以及字符转数字这两个操作也极其高频char[] chars s.toCharArray(); // 遍历时要注意char是不能直接参与算术的要想清楚要不要-0 int digit s.charAt(i) - 0;这里有一个竞赛新手特别容易忘记的点char类型本质上是无符号整数9 - 0才是数字9直接用Integer.parseInt(String.valueOf(s.charAt(i)))效率极低还容易出错。同理把一个小写字母转成它在字母表中的序号时c - a起步是0转大写是c - A。3.3 字符数组与字符串互转单纯是字符串层面解决不了问题时工程思维马上就会想到转成可变结构——在Java里这个可变结构通常是char数组。String s acbd; char[] arr s.toCharArray(); Arrays.sort(arr); // 原地排序O(NlogN) String sorted new String(arr); // 排序后的字符串这个字符串转字符数组、排序、再转回字符串的组合是判断两个字符串是否由相同字符组成字母异位词的经典解法之一另一套是用HashMap计数两者各有适用场景。字符数组的优势在于它不产生额外存储对象的开销排序后直接得到一个规整的String。我多次用到字符数组后总结出一个习惯只要题目需要操作字符串中的单个字符且不止一次修改——就先转成char[]处理完再用new String(arr)转回来。工程代码里写这个会被人吐槽风格奇怪但竞赛场景里这是最直观的写法了。3.4 BigInteger工程开发者容易忽略的大数解法Java的BigInteger在竞赛题里是保底方案。它最纯粹的价值在于不管整数多大都能精确表示不会溢出。但代价是慢而且不慢一点点是比原生long慢几个数量级。适合用BigInteger的场景有两类第一类是题目明确给的数值范围超出了long约9.2×10^18比如求高精度幂、超大数的加减乘除。第二类是涉及超大范围的素性判断或求最大公约数。BigInteger内置了isProbablePrime和gcd用起来比手写Miller-Rabin踏实得多。BigInteger a new BigInteger(123456789012345678901234567890); BigInteger b new BigInteger(987654321098765432109876543210); BigInteger sum a.add(b); BigInteger prod a.multiply(b); BigInteger g a.gcd(b); boolean prime a.isProbablePrime(100); // 100是确定性参数越大越精确但耗时也越高BigInteger的构造函数也值得注意new BigInteger(String)是十进制new BigInteger(String, 2)可以读二进制。还有一种常用的构造是BigInteger.valueOf(long)可以直接传入long。我踩过的坑是用BigInteger做循环时顺手写了一堆new BigInteger(1)然后加结果慢到我怀疑人生。大数据场景建议直接预先把常量的BigInteger存成静态变量复用private static final BigInteger ONE BigInteger.ONE; private static final BigInteger ZERO BigInteger.ZERO;4. 竞赛常用算法操作与实用模板4.1 排序与自定义比较器排序是整个算法竞赛里最基础的基础设施。Java给两种排序数组用Arrays.sortList用Collections.sort底层都是TimSort性能稳定。但有一个Java独有的坑必须高度警惕Arrays.sort对基本类型数组和对象数组的处理逻辑完全不同。基本类型数组int[]、long[]等的sort用的是快速排序算法只能升序不接受Comparator参数对象数组比如Integer[]的sort用的是归并排序的变体可以传Comparator。这就导致了一个让无数人困扰的现象// 这会编译报错int[] 无法搭配lambda Arrays.sort(arr, (a, b) - b - a);正确做法是转成Integer[]Integer[] arr {3, 1, 4, 1, 5}; Arrays.sort(arr, (a, b) - b - a); // 降序或者使用Arrays.stream的装箱再排序但那样开销更大。竞赛中如果不想装箱有一个实用技巧——先升序排再手动反转前一半但通常多此一举。个人建议数据量不超过10^5时直接转包装类排序完全够用。自定义对象排序在竞赛里多为二维数组按某个维度排序。最常见的写法int[][] intervals new int[n][2]; Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); // 按第一维升序 // 注意不要写成 a[0] - b[0]如果差值超过int范围会溢出这个Integer.compare比直接减法的好处就是防止溢出。很多人在大数排序时莫名其妙出错最后定位到就是这里。4.2 二分查找会用Arrays.binarySearch更要会手写Java的Arrays.binarySearch和Collections.binarySearch是现成的二分查找工具但工程思维容易忽略一个关键点这个方法在找不到目标时返回的不是-1而是-(插入点) - 1。举个具体例子int[] arr {1, 3, 5, 7}; int idx Arrays.binarySearch(arr, 4); // 返回 -3因为它应该插在下标2的位置结果是 -(2) - 1 -3很多题解里会用到这个返回值来定位插入点但把它当普通查找用就会出错。如果你只想判断是否存在那 0检查一下就行。竞赛里更常见的需求其实是找左边界和找右边界也就是lowerBound和upperBound。Arrays.binarySearch没法直接解决这类问题所以很多选手会选择手写static int lowerBound(int[] arr, int target) { int l 0, r arr.length - 1; while (l r) { int mid l (r - l) / 2; // 防溢出写法 if (arr[mid] target) { r mid; } else { l mid 1; } } return arr[l] target ? l : arr.length; }这个模板的记忆方式很简单lowerBound找的是第一个target的位置upperBound找的是第一个target的位置只需要把arr[mid] target改成arr[mid] target即可。手写时我还想额外提醒mid用l (r - l) / 2而不是(l r) / 2因为后者在l和r都特别大时可能溢出。这个坑虽然竞赛题给的数据范围不一定能触发但养成习惯没有坏处。4.3 位运算助记位运算在竞赛里像暗器一样平时不用用到就要命一样好使。工程开发者可能一年写不了几处位运算但刷题时必须知道几个高频模板。判断奇偶if ((n 1) 1) { // 奇数 }乘2除2int x n 1; // n*2注意溢出风险 int y n 1; // n/2向下取整负数会出问题提取最右边的1lowbitint lowbit n (-n);这句话看起来简单它背后是取反加一两步操作把符号位利用起来的效果。lowbit在树状数组里是核心操作只要涉及区间和查询这一行就能派上大用场。异或运算的性质a ^ a 0a ^ 0 a。最经典的题就是数组里只有一个数出现一次其余都出现两次用这个性质一遍循环就能找出来int result 0; for (int num : nums) { result ^ num; } return result;位运算还有一个工程开发者容易忽略的优势它就是为底层性能而生的比加减乘除都快。4.4 快读快写模板Java在竞赛里最大的劣势就是I/O慢。Scanner读1万行数据没问题但读100万行就会明显拖慢整个程序。如果你决定用Java打比赛或应对面试里的OJ环境强烈建议直接用快读模板。我用过的最顺手的快读方案是BufferedReaderStringTokenizerStringBuilder的组合BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); // 循环读大量数据时用StringBuilder收集输出 StringBuilder sb new StringBuilder(); while (st.hasMoreTokens()) { int a Integer.parseInt(st.nextToken()); sb.append(a).append(\n); } System.out.print(sb);这里有几个优化的细节不要用System.out.println直接逐行输出它在每次调用时都有一次IO操作。积少成多数据量大时比StringBuilder攒着统一输出慢一个数量级。StringTokenizer比String.split()快后者基于正则开销大得多。如果题目数据量特别大甚至可以直接用BufferedReader逐字节读入再手动解析这个就属于进阶玩法正常快读模板已经够用。也有人会封装一个FastScanner类把nextInt、nextLong、nextDouble都实现进去。这个class在竞赛圈基本人手一个核心思想就是维护一个buffered char数组用下标扫描。我一般比赛时用一个稍微精简的版本来回复用。5. 常见问题与排查技巧实录5.1 超时的几个隐蔽根源Java提交后显示TLETime Limit Exceeded大多数问题不在算法复杂度而在IO或常数上。这是我多次实战后总结的几个高频超时原因建议按顺序排查。第一Scanner读入。这个最快暴露数据量超过10^6时Scanner比BufferedReader慢5到10倍是最大的常数瓶颈。第二System.out.println逐行输出。这个比Scanner更隐蔽因为输出量少时感受不到一旦大量输出就立刻卡住。第三无意识的装箱拆箱。比如把int放进List 时反复自动装箱在小数据量没事大数据量的循环里会产生大量对象。第四String拼接。循环里用拼接就是灾难。排查时有个经验法则先检查IO再检查是否有高频创建对象最后再看算法复杂度是不是真的错了。我自己就有过算法是对的却反复TLE的经历最后定位在Scanner上换成快读后直接压线通过。5.2 容器拷贝与内存陷阱工程开发里List的拷贝大家都习惯用new ArrayList(original)或者Map用putAll这都没问题。但竞赛里有一个特别致命的陷阱这种拷贝是浅拷贝。如果原List里装的是自定义对象那么新List里的元素和旧List指向的是同一个对象引用。修改其中一个会影响另一个。如果你需要复制一个列表然后改一版再对比必须想清楚深层拷贝要不要做。另外还有一个很隐蔽的内存陷阱Arrays.asList生成的List是固定大小调用add或remove会抛UnsupportedOperationException但很多人会拿它当普通List使报错了才反应过来。竞赛中如果你只是想快速初始化一个List用这个可以但别修改它。内存溢出场景最典型的还是数组开太大。有些人在方法内部声明int[][] dp new int[100000][100000]这种在Java里肯定OutOfMemoryError因为二维数组每个一维数组都是一个对象对象头还有额外开销。处理办法是把二维拍扁成一维索引用i * cols j定位。5.3 比较器相关的三个坑比较器这块是Java竞赛代码里翻车率最高的我逐一记录一下。坑一基本类型数组传不了Comparator。前面提过了Arrays.sort(int[], (a,b)-...)编译不过这是Java的设计限制。尽量用包装类数组或者提前转类型。坑二Comparator的返回值含义容易被记反。a.compareTo(b)返回负数是a在前注意是很绕的Comparator的compare(a, b)返回负数表示a排在b前面。这个可以这么助记返回负数就往前排返回正数就往后排返回0就俩一样。如果你排出来顺序反了就把a和b对调一下即可。坑三return a - b有溢出风险。一个极其极端的例子Integer.MIN_VALUE - Integer.MAX_VALUE会溢出成一个很大的数。推荐永远用Integer.compare(a, b)或Long.compare(a, b)这两个方法内部用的是不溢出的比较逻辑而且代码也简洁清晰。5.4 数据结构操作速查助记表最后放一张我实际刷题时用得很频繁的速查表你可以存下来想不起来的时候翻一眼需求推荐结构核心操作时间复杂度动态数组/随机访问ArrayListadd, get, set, sortO(1)按索引频繁头尾增删ArrayDequeofferFirst, pollLastO(1)键值对统计HashMapmerge, getOrDefault平均O(1)需要有序的键值对TreeMapceilingKey, floorKey, firstKeyO(logN)去重HashSetadd, contains, size平均O(1)有序去重集合TreeSetfirst, last, ceilingO(logN)取最小/最大值PriorityQueueoffer, poll, peekO(logN)字符串拼接/反转StringBuilderappend, reverse均摊O(1)大数运算BigIntegeradd, multiply, gcd位数相关这张表的记忆逻辑其实很简单需要单点随机访问就选ArrayList需要按大小顺序访问就选Tree系列需要最值快速进出就选堆需要一键去重计数就选Hash系列。数据结构选型这件事本质就是把操作需求翻译成对应结构的时间复杂度。写在最后的一点经验我整理这份助记版的初衷其实来源于刷题群里经常看到的一句话代码我都认识合在一起就不知道什么意思。Java的容器类API非常多但竞赛真正高频的就那么十几个方法。与其继续记API手册不如做减法把二十多个最常用的方法固化成肌肉记忆。实际操作中最想强调的是不要试图把所有方法背下来再去刷题而是用几道经典题带出自己的盲区。我自己的路径就是先从HashMap和PriorityQueue入手把TopK、分组、滑动窗口这类基础题跑通然后再逐步引入TreeMap和高级位运算。每遇到一个新需求就查一次表查完用一次两三次之后自然就记住了。如果这篇文章能帮你在面对竞赛题解时少一点陌生感那这个助记版就算达到目的了。最后再补一句题外话工程思维和竞赛思维完全可以共存理解两者差异本身就是一种复合能力这个能力在写复杂业务逻辑时反而会转化成你的优势。