算法题常用技巧

前面几篇讲了 Java 的语法和数据结构，已经够你看懂大部分代码了。这篇补充一些在刷算法题时经常会用到的实用技巧，都是一些零散但重要的知识点。

¶输入输出

前面在基础语法那篇已经介绍过 Scanner 的基本用法。这里补充一下算法竞赛中常见的输入输出模式。

¶ACM 模式 I/O 模板

很多 OJ 平台（包括本站）使用 ACM 模式，需要你自己处理输入输出。最常见的模式是循环读取，直到输入结束：

另一种常见模式是不知道有多少行输入，用 hasNext 判断：

Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
    int a = sc.nextInt();
    int b = sc.nextInt();
    System.out.println(a + b);
}

¶BufferedReader 高性能读取

当输入数据量很大时，Scanner 可能会比较慢，导致超时。这时候可以用 BufferedReader，读取速度快很多：

BufferedReader 只能按行读取字符串，需要自己做分割和类型转换，写起来比 Scanner 麻烦。一般先用 Scanner，遇到超时再换 BufferedReader。

¶排序与比较

¶数组排序

基本类型数组用 Arrays.sort，前面已经见过了。这里讲一下如何自定义排序规则。

对于对象数组或 ArrayList，可以传入一个比较器（Comparator）来指定排序规则：

(a, b) -> a - b 是 Lambda 表达式，你可以把它理解为一个简写的匿名函数：接收两个参数 a 和 b，返回 a - b 的结果。如果结果为负数，a 排在前面；为正数，b 排在前面。所以 a - b 是升序，b - a 是降序。Lambda 的详细语法会在进阶篇讲解。

注意：a - b 在极端情况下可能整数溢出（比如 a = Integer.MIN_VALUE, b = 1）。更安全的写法是 Integer.compare(a, b)（升序）和 Integer.compare(b, a)（降序）。一般刷题时数据范围不会那么极端，但如果题目明确说数值范围很大，就用 Integer.compare。

注意：Arrays.sort 对基本类型数组（如 int[]）不支持自定义比较器，只能升序排列。如果需要降序排 int[]，要么先升序再反转，要么转成 Integer[]。

¶多级排序

有时需要按多个条件排序，比如先按年龄排序，年龄相同再按名字排序：

¶Comparable 接口

如果你自定义了一个类，希望它的对象能直接排序，可以让类实现 Comparable 接口：

¶常用数学操作

¶整数边界值

int 和 long 都有范围限制，超出范围会溢出：

算法题中最常见的溢出场景是两个 int 相加或相乘，结果超出 int 范围。遇到这种情况，把其中一个操作数转成 long 就行：

int a = 100000, b = 100000;
// 错误：int * int 结果还是 int，会溢出
int wrong = a * b;
// 正确：先转 long 再乘
long right = (long) a * b;

¶类型转换与包装类

¶基本类型与包装类

Java 的集合类（ArrayList、HashMap 等）只能存引用类型，不能存基本类型。所以每个基本类型都有对应的包装类：

Java 会自动在两者之间转换，叫做自动装箱（boxing）和拆箱（unboxing）：

// 自动装箱：int -> Integer
Integer a = 10;
// 自动拆箱：Integer -> int
int b = a;

大多数情况下你不用关心这个，Java 自动处理。但有一个坑要注意。

¶== vs equals 的陷阱

原因是 Java 缓存了 -128 到 127 之间的 Integer 对象，这个范围内 == 比较的碰巧是同一个对象，所以返回 true。超出范围就是不同的对象了，== 比较的是对象地址，自然是 false。

记住：比较引用类型永远用 equals()，不要用 ==。这对 String、Integer 等都适用。

¶字符串与数字的转换

¶进制转换

有些算法题会涉及进制相关的问题，了解标准库提供的进制转换方法，就不需要自己手搓转换逻辑了。Java 提供了一组静态方法，可以在十进制和其他进制之间互相转换：

刷题中最常用的是 Integer.toBinaryString() 和 Integer.parseInt(s, 2)，在位运算相关的题目中经常用到。Integer.bitCount(n) 可以直接统计二进制中 1 的个数，不需要自己写循环。

¶小结

这篇介绍的技巧在刷题中会反复用到。输入输出方面，先用 Scanner，超时了换 BufferedReader。排序用 (a, b) -> a - b 表示升序，b - a 表示降序。计算结果可能越界时记得转 long。比较引用类型永远用 equals()，不要用 ==。

学到这里，Java 刷题所需的基础知识就全部介绍完了。接下来就可以开始刷题了，边刷边查，很快就能熟练起来。

后面两篇是进阶特性，包括继承、接口、泛型、多线程等。在设计模式的代码中会大量使用，如果你暂时只想刷算法题，可以先跳过。