Java刷题API与算法模板
Java 刷题 API 与算法模板
这篇只保留高频、容易写错、能直接用于刷题的 Java API 和算法骨架。完整题型路线见 算法 MindMap,JDK 实现细节见 源码。
0. Hot 100 数据结构速查
刷完 Hot 100 回头看,真正用到的结构就这一张表。第三列是对应的源码精读,弄懂底层之后 API 的各种行为(扩容时机、null 语义、迭代顺序)就不用死记了。
| 结构 | Hot 100 里的用武之地 | 源码精读 |
|---|---|---|
int[] / char[] | 绝大多数题的地基;int[26] 计数数组是字母题里 HashMap 的轻量替身(字母异位词、找异位词子串) | |
String / StringBuilder | 拼接、反转、字符串解码 | String、StringBuilder |
ArrayList | 收集答案、回溯的 path、图的邻接表 | ArrayList |
HashMap | 两数之和、前缀和计数、异位词分组 | HashMap |
HashSet | 最长连续序列、判重 | HashSet |
LinkedHashMap | LRU 缓存一题的官方外挂 | LinkedHashMap |
ArrayDeque | 栈(有效括号、每日温度、字符串解码)、队列(层序遍历、腐烂的橘子)、单调队列(滑动窗口最大值) | ArrayDeque |
PriorityQueue | 前 K 个高频元素、合并 K 个有序链表、数据流中位数 | PriorityQueue |
LinkedList | 需要 List 和 Deque 双接口、或存 null 时;其余场景让位给 ArrayDeque | LinkedList |
Integer 等包装类 | 到处都在用,坑在装箱缓存和拆箱 NPE | Integer |
1. 数组与字符串
数组初始化、填充与复制
代码块收起展开
int[] nums = new int[n];
Arrays.fill(nums, -1);
Arrays.fill(nums, from, to, value); // [from, to)
int[] copy = Arrays.copyOf(nums, nums.length);
int[] range = Arrays.copyOfRange(nums, from, to); // [from, to)字符串高频 API
代码块收起展开
char ch = text.charAt(i);
int n = text.length();
String part = text.substring(left, right); // [left, right)
char[] chars = text.toCharArray();
String rebuilt = new String(chars);
StringBuilder builder = new StringBuilder();
builder.append(value);
builder.deleteCharAt(index);
builder.reverse();
String result = builder.toString();字符转索引时要明确基准:
代码块收起展开
int index = ch - 'a'; // 小写字母映射到 0..25
int digit = ch - '0'; // 数字字符映射到 0..9直接把 char 当数组下标使用的是 Unicode 码值,通常会浪费空间或越界。
2. List、Set 与迭代器
List
代码块收起展开
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(0, 5);
int value = list.get(0);
list.set(0, 7);
int size = list.size();删除整数时注意重载:
代码块收起展开
list.remove(1); // 删除下标 1
list.remove(Integer.valueOf(1)); // 删除值 1遍历时删除必须使用迭代器:
代码块收起展开
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
int current = it.next();
if (current < 0) it.remove();
}增强 for 中直接调用 list.remove 会触发快速失败,通常抛出 ConcurrentModificationException。
Set
代码块收起展开
Set<Integer> seen = new HashSet<>();
if (!seen.add(value)) {
// add 返回 false，说明 value 已经存在
}- 只判断存在性:
HashSet。 - 需要有序遍历:
TreeSet,操作通常为 $O(\log n)$。 - 需要保留插入顺序:
LinkedHashSet。
3. Queue、Deque 与栈
刷题时优先使用 ArrayDeque,不要用旧的 Stack。
代码块收起展开
Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(1); // 队尾入队
deque.pollFirst(); // 队头出队，无元素返回 null
deque.peekFirst(); // 查看队头
deque.offerFirst(0); // 队头插入
deque.pollLast(); // 队尾弹出作为栈:
代码块收起展开
deque.push(value); // 等价于 addFirst
int top = deque.peek();
int out = deque.pop();add/remove/get 失败时抛异常,offer/poll/peek 失败时返回 false/null。算法代码通常用后一组更容易处理空结构。
LinkedList 同时实现 List 和 Deque,但大多数队列/栈场景下 ArrayDeque 缓存局部性更好、额外对象更少。
两个实现的底层对比见 ArrayDeque 源码:环形数组靠”永远留一个空槽”区分空和满,这也是它禁止存 null 的原因(null 被征用为”队列空”的信号)。
单调栈与单调队列
Hot 100 里 Deque 的进阶用法。单调栈解”下一个更大元素”一族(每日温度、柱状图最大矩形):栈里只留还没找到答案的下标,新元素把比它小的全部结算出栈。
代码块收起展开
Deque<Integer> stk = new ArrayDeque<>(); // 存下标, 栈内温度单调递减
for (int i = 0; i < n; i++) {
while (!stk.isEmpty() && t[i] > t[stk.peek()]) {
int j = stk.pop();
ans[j] = i - j; // i 就是 j 等的那个更大值
}
stk.push(i);
}单调队列解滑动窗口最大值:队头是当前窗口最大值的下标,新元素从队尾把比自己小的全部挤掉(它们再无出头之日),队头滑出窗口范围就弹掉。每个元素至多进出一次,整体 $O(n)$。
4. HashMap 高频写法
计数
代码块收起展开
Map<Integer, Integer> count = new HashMap<>();
count.merge(value, 1, Integer::sum);
int frequency = count.getOrDefault(value, 0);按键创建容器
代码块收起展开
Map<String, List<Integer>> groups = new HashMap<>();
groups.computeIfAbsent(key, ignored -> new ArrayList<>()).add(value);computeIfAbsent 返回现有或新建的 value,不是返回整个 Map。
遍历
代码块收起展开
for (Map.Entry<Integer, String> entry : map.entrySet()) {
int key = entry.getKey();
String value = entry.getValue();
}遍历中删除同样要用 entrySet().iterator() 的 remove()。
包装类的两个坑
代码块收起展开
Integer a = 127, b = 127;
a == b; // true, 命中 IntegerCache(-128~127)
Integer c = 128, d = 128;
c == d; // false! 缓存外是两个对象从 Map/List 里拿出来的 Integer 比大小一律用 equals 或先拆箱成 int,== 在 128 以上随缘。
另一个坑是拆箱 NPE:int v = map.get(key) 在 key 不存在时对 null 拆箱直接炸,查不准就用 getOrDefault。
缓存池的实现见 Integer 源码。
LinkedHashMap 实现 LRU
LRU 缓存那题手写双向链表 + HashMap 是主线答案,但 LinkedHashMap 本身就内置了这套结构,两个开关拧开即是 LRU:
代码块收起展开
class LRUCache extends LinkedHashMap<Integer, Integer> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true); // 第三个参数 accessOrder: get 也会把节点挪到链表尾
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value); // int 参数是重载不是重写, 编译没有冲突
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity; // put 后超容量, 自动淘汰链表头(最久未访问)
}
}accessOrder = true 让每次访问都把节点移到尾部,removeEldestEntry 是 put 完的回调钩子。
底层就是”HashMap 定位 + 双向链表记序”,和手写版一模一样,细节见 LinkedHashMap 源码。
5. PriorityQueue 与 Top K
Java 的 PriorityQueue 默认是小根堆,且不允许加入 null。
代码块收起展开
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Comparator.reverseOrder());
minHeap.offer(value);
int smallest = minHeap.peek();
int removed = minHeap.poll();比较器不要写 a - b,极值相减可能溢出:
代码块收起展开
PriorityQueue<int[]> heap = new PriorityQueue<>(
(a, b) -> Integer.compare(a[1], b[1])
);维护最大的 $k$ 个元素通常使用大小不超过 $k$ 的小根堆:
代码块收起展开
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int value : nums) {
heap.offer(value);
if (heap.size() > k) heap.poll();
}
// heap.peek() 是第 k 大数据流中位数用双堆:大根堆存较小的一半,小根堆存较大的一半,维持两堆大小差不超过 1,中位数就在堆顶。合并 K 个有序链表则把 K 个头节点全放进小根堆,每次 poll 最小的并把它的 next 补进来。
堆的底层是数组编码的完全二叉树,offer 放末尾上浮、poll 末元素补顶下沉,迭代顺序并非有序,remove(Object) 是 $O(n)$,这些行为的来龙去脉见 PriorityQueue 源码。
6. 排序与比较器
默认选择
代码块收起展开
Arrays.sort(intArray); // 原始类型数组
Arrays.sort(objectArray); // 元素实现 Comparable
Arrays.sort(objectArray, comparator); // 对象数组自定义顺序
list.sort(comparator); // List 原地排序int[] 不能传对象比较器。需要自定义顺序时,可转为 Integer[],或重新设计键和算法。
代码块收起展开
intervals.sort(
Comparator.comparingInt((int[] a) -> a[0])
.thenComparingInt(a -> a[1])
);不要一看到顺序就全排序
| 目标 | 优先考虑 | 复杂度 |
|---|---|---|
| 全部有序 | 比较排序 | $O(n\log n)$ |
| 值域很小的整数 | 计数/桶排序 | $O(n+V)$ |
| 第 $k$ 大/小 | 堆或 quickselect | $O(n\log k)$ / 平均 $O(n)$ |
| 只有 0、1、2 | 三路划分 | $O(n)$ |
| 区间合并 | 按起点排序后扫描 | $O(n\log n)$ |
计数排序模板
代码块收起展开
static void countingSort(int[] nums) {
if (nums.length < 2) return;
int min = nums[0], max = nums[0];
for (int value : nums) {
min = Math.min(min, value);
max = Math.max(max, value);
}
long range = (long) max - min + 1;
if (range > 1_000_000L) {
Arrays.sort(nums); // 值域过大时避免巨大计数数组
return;
}
int[] count = new int[(int) range];
for (int value : nums) count[value - min]++;
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i]-- > 0) nums[index++] = i + min;
}
}这段是计数排序,不是基数排序;它同时处理负数,并防止值域过大造成内存浪费。
7. 二分查找
精确查找
统一使用闭区间 [left, right]:
代码块收起展开
static int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}第一个大于等于 target 的位置
使用左闭右开区间 [left, right):
代码块收起展开
static int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}二分最重要的不是背代码,而是保证:搜索区间定义始终一致,每次循环都排除 mid 或缩小区间,终止时指针含义明确。
8. 前缀和与差分
一维前缀和
令 prefix[i] 表示前 i 个元素的和:
代码块收起展开
long[] prefix = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
long rangeSum = prefix[right + 1] - prefix[left]; // 闭区间 [left, right]和可能超过 int 时使用 long。
差分
对多个闭区间 [left, right] 增加 delta:
代码块收起展开
diff[left] += delta;
if (right + 1 < diff.length) diff[right + 1] -= delta;
for (int i = 1; i < diff.length; i++) {
diff[i] += diff[i - 1];
}前缀和适合频繁查询区间和;差分适合频繁更新区间、最后一次性还原每个位置的值。
9. Lambda 与 Stream:刷题中的使用边界
代码块收起展开
List<Integer> positives = nums.stream()
.filter(x -> x > 0)
.distinct()
.sorted()
.toList();常用函数式接口:
| 接口 | 含义 |
|---|---|
Predicate<T> | 输入 T,返回条件真假 |
Function<T,R> | 把 T 转成 R |
Consumer<T> | 消费 T,无返回值 |
Supplier<T> | 无参数,提供一个 T |
刷题时 Stream 适合清晰的数据转换、分组和统计;对性能敏感的嵌套循环、复杂指针移动、原地修改和提前退出,普通循环往往更直接。系统性的 Lambda、方法引用、闭包和 Stream 笔记见 Java 函数式编程。
10. 高频正确性检查
- 下标区间到底是闭区间还是半开区间?
- 空数组、单元素、全部相同、目标不存在是否正确?
int相加、相乘或比较器相减是否溢出?- HashMap 的键是否正确实现
equals/hashCode? - PriorityQueue 的堆顶语义是否与 Top K 目标相反?
- 遍历集合时是否进行了非法结构修改?
- 递归深度是否可能导致栈溢出?
- 时间复杂度是否匹配数据规模?