当前位置：首页 > news >正文

Java刷题必备：集合框架、字符串与位运算实战技巧

news 2026/8/2 3:25:06

1. 项目缘起：为什么我们需要一份Java刷题“兵器谱”

如果你正在准备技术面试，或者想系统性地提升自己的算法和编程能力，LeetCode几乎是绕不开的平台。但很多朋友，尤其是Java开发者，在刷题时常常会遇到一个尴尬的局面：题目思路想明白了，代码逻辑也清晰了，但就是写不快、写不优雅，甚至在一些边界条件处理上栽跟头。问题出在哪？很多时候，不是算法本身，而是对Java这门语言的标准库（API）和常用数据结构不够熟悉。

我自己在带新人、面试候选人以及日常刷题时，发现一个普遍现象：大家花大量时间研究动态规划的状态转移方程，琢磨回溯的剪枝策略，这当然没错。但与此同时，却对Arrays.sort()如何自定义排序、PriorityQueue的初始容量和比较器、StringBuilder和StringBuffer在并发场景下的细微差别、Map的computeIfAbsent方法如何简化代码等“基本功”掌握得模棱两可。结果就是，一个简单的哈希表去重操作，可能要写五六行代码，而熟练的开发者一两行就能搞定，这中间的效率差在笔试或面试的紧张环境下会被无限放大。

这份总结，就是我想为你整理的Java刷题“兵器谱”。它不教你具体的算法思想，那是算法导论和各类教程的任务。它的核心目标只有一个：当你确定了解题思路后，能让你用Java语言最快、最稳、最专业地把代码写出来。我会把LeetCode刷题中最高频、最实用的API和数据结构用法，结合具体的题目场景，掰开揉碎了讲清楚，并附上我踩过的坑和总结的技巧。这份文档是“活”的，我会根据大家的反馈和新的题目类型持续更新。

2. 集合框架：你的算法“弹药库”深度解析

Java集合框架是刷题时使用频率最高的部分，没有之一。但会用ArrayList和HashMap只是入门，理解其内部机制和特性才能让你在关键时刻做出最优选择。

2.1 List家族：ArrayList与LinkedList的抉择

几乎所有需要动态数组的场景，ArrayList都是首选。它的底层是数组，支持O(1)时间的随机访问，这是巨大优势。但在刷题中，有几点必须注意：

初始化与容量：很多人在刷题时习惯List<Integer> list = new ArrayList<>();就完事了。如果提前知道数据规模，一定要指定初始容量。例如，你知道最终要存放大约1000个元素，那么new ArrayList<>(1000)。这能避免多次扩容带来的性能损耗和数据拷贝。虽然对于单次运行影响不大，但在追求极致性能的解法或处理大数据量时，这是一个好习惯。

遍历与修改：这是经典的坑。在遍历ArrayList并尝试删除元素时，直接使用for循环配合索引删除，会导致后续元素索引错乱。正确做法是使用Iterator的remove方法，或者从后往前遍历删除。更现代和简洁的做法是使用removeIf方法：

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5)); list.removeIf(num -> num % 2 == 0); // 删除所有偶数 System.out.println(list); // 输出: [1, 3, 5]

LinkedList的应用场景：在LeetCode中，LinkedList作为双向链表，其用武之地相对特定。当你需要频繁在列表头部或尾部进行插入和删除操作，并且不需要随机访问时，它就是最佳选择。典型的题目是实现LRU缓存淘汰算法的双向链表部分，或者某些BFS中用于队列（但通常更推荐ArrayDeque）。记住，LinkedList的get(int index)方法是O(n)的，切忌把它当数组用。

2.2 Map家族：HashMap、TreeMap与LinkedHashMap

HashMap是哈希表题的绝对主力，O(1)时间复杂度的查找、插入是其核心价值。

自定义对象作为Key：这是面试常考点。如果你自定义的类（比如一个点的坐标Point）要作为HashMap的键，必须重写hashCode()和equals()方法。hashCode决定了对象被放入哪个桶，equals用于在哈希冲突时比较桶内的对象是否真正相等。IDE通常可以自动生成这两个方法，但你需要理解其必要性。

computeIfAbsent与merge：让代码更简洁：这两个方法是Java 8之后提升代码表达力的神器。看一个统计词频的例子：

// 传统写法 Map<String, Integer> countMap = new HashMap<>(); for (String word : words) { if (countMap.containsKey(word)) { countMap.put(word, countMap.get(word) + 1); } else { countMap.put(word, 1); } } // 使用 merge 方法 (更简洁) Map<String, Integer> countMap2 = new HashMap<>(); for (String word : words) { countMap2.merge(word, 1, Integer::sum); // 如果key存在，将旧值和1相加；不存在，则放入1 } // 使用 computeIfAbsent 和 put (在某些复杂value时好用) Map<String, List<String>> groupMap = new HashMap<>(); for (String item : items) { String key = getKey(item); groupMap.computeIfAbsent(key, k -> new ArrayList<>()).add(item); }

computeIfAbsent特别适合value是集合的场景，它实现了“如果key不存在，则创建一个新集合放入；如果存在，则直接返回该集合”的原子操作。

TreeMap：需要有序Key时使用：当题目要求你按照键的自然顺序或自定义顺序进行遍历时，TreeMap就派上用场了。它的增删查改操作都是O(log n)。例如，LeetCode上“数据流的中位数”、“我的日程安排表”等题目，利用TreeMap的ceilingKey（返回大于等于给定键的最小键）、floorKey等方法可以优雅求解。记住，它的有序性是靠红黑树实现的。

LinkedHashMap：记住插入顺序或访问顺序：它继承自HashMap，但额外维护了一个双向链表来记录条目顺序。默认是插入顺序，也可以构造为访问顺序（最近访问的放在最后）。这使其成为实现LRU缓存的绝佳选择，无需自己从头构建双向链表。

2.3 Set家族：HashSet、TreeSet与去重艺术

Set用于去重和快速存在性检查。HashSet基于HashMap，TreeSet基于TreeMap，所以它们的特性与对应的Map一致。

去重的陷阱：对于自定义对象，放入HashSet同样需要正确重写hashCode和equals。TreeSet则需要对象实现Comparable接口，或者在构造时传入Comparator。

TreeSet的导航方法：和TreeMap类似，TreeSet提供了ceiling(e),floor(e),higher(e),lower(e)等方法，在需要找到集合中某个元素“附近”的元素时非常有用，例如在“包含重复元素的有序集合中找上下界”这类题目中。

2.4 Queue与Deque：算法中的“流水线”

队列在BFS（广度优先搜索）中是核心数据结构。LinkedList实现了Deque接口，可以作为队列使用，但通常更推荐ArrayDeque。

为什么推荐ArrayDeque作为队列？ArrayDeque底层是循环数组，它在大多数操作上的性能都优于LinkedList，因为避免了链表节点的内存开销。无论是作为普通队列（FIFO）还是栈（LIFO），ArrayDeque都是更好的选择。除非你需要频繁在中间插入删除，或者需要用到LinkedList的特定API。

// BFS 模板中使用 ArrayDeque Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); // 入队，推荐使用 offer 而不是 add（后者在容量限制队列中会抛异常） while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); // 出队 // ... 处理当前节点 ... if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } }

PriorityQueue：堆的实现：这是解决Top K问题、求中位数、Dijkstra算法等问题的利器。关键在于构造时传入正确的比较器（Comparator）。

// 最小堆（默认） PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 最大堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 或者 Comparator.reverseOrder() // 自定义对象堆，按某个属性排序 PriorityQueue<Person> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.age));

注意：PriorityQueue的iterator()遍历不保证顺序。只有通过poll()或remove()方法取出的元素才是有序的。

3. 数组与字符串：基础中的战斗机

虽然基础，但相关的API和技巧往往能决定代码的简洁度和效率。

3.1 数组工具类：`java.util.Arrays`

Arrays类充满了宝藏方法。

排序与二分查找：Arrays.sort()可以对数组排序，对于对象数组，可以传入Comparator。Arrays.binarySearch()在有序数组上进行二分查找，返回索引（找到）或插入点（未找到，为-（插入点）- 1）。切记，必须在调用binarySearch前确保数组已排序，否则结果未定义。

数组填充、复制与比较：

Arrays.fill(arr, value)：快速填充数组。
Arrays.copyOf(arr, newLength)：复制数组，可以扩容或缩容。
Arrays.equals(arr1, arr2)：比较两个数组内容是否相等。对于多维数组，使用Arrays.deepEquals。
Arrays.toString(arr)/Arrays.deepToString(multiArr)：调试神器，快速打印数组内容。

将数组转为List：Arrays.asList(T... a)。这里有一个大坑：它返回的List是一个固定大小的视图，不支持add或remove操作，会抛出UnsupportedOperationException。如果需要一个可变的ArrayList，应该new ArrayList<>(Arrays.asList(...))。

3.2 字符串：`String`、`StringBuilder`与`StringBuffer`

不可变性与性能：String的不可变性是Java的基础设计。这意味着任何对String的修改（拼接、替换）都会产生新的对象。在循环中进行字符串拼接是性能杀手。

// 错误示范：在循环中拼接字符串 String result = ""; for (String str : stringList) { result += str; // 每次循环都创建新的StringBuilder和String对象！ } // 正确示范：使用 StringBuilder StringBuilder sb = new StringBuilder(); for (String str : stringList) { sb.append(str); } String result = sb.toString();

StringBuildervsStringBuffer：两者API几乎一样。StringBuffer是线程安全的（方法加了synchronized关键字），但因此有性能损耗。在LeetCode刷题这种单线程场景下，永远使用StringBuilder。

常用API点睛：

charAt(int index),length()：基础访问。
substring(int beginIndex, int endIndex)：取子串。注意参数是前闭后开[begin, end)。
indexOf(String str),lastIndexOf(String str)：查找子串位置。
split(String regex)：按正则分割，注意正则元字符（如.、|）需要转义。
toCharArray()：转为字符数组，便于修改和遍历。
String.format(String format, Object... args)：格式化字符串，在构造复杂输出时比拼接更清晰。

字符串转换：

数字与字符串：Integer.parseInt(str),String.valueOf(num)。
字符数组与字符串：new String(charArray),str.toCharArray()。

4. 数学、随机与位运算：隐藏的利刃

这类工具不常用，但一旦用到，就是解决问题的关键。

4.1`Math`类与`Random`类

Math类提供了基本的数学运算常量和方法：Math.PI,Math.E,abs,max,min,pow,sqrt,log,sin,cos等。在图形、几何或需要数学计算的题目中会用到。

Random类用于生成伪随机数。刷题中常用于打乱数组（洗牌算法）、随机选择等。注意，可以指定种子（seed）以保证可重复性，这在调试时很有用。

Random rand = new Random(12345); // 固定种子 int randomNum = rand.nextInt(100); // 生成 [0, 100) 的随机整数 // 洗牌算法 (Fisher-Yates Shuffle) for (int i = arr.length - 1; i > 0; i--) { int j = rand.nextInt(i + 1); // 生成 [0, i] 的随机整数 // 交换 arr[i] 和 arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

Java中更现代的洗牌可以使用Collections.shuffle(List<?> list)。

4.2 位运算：高效与技巧并存

位运算在部分算法题中能极大提升性能，也是面试高频考点。

基本操作：

&(与)：同1为1。常用场景：判断奇偶（n & 1），取特定位。
|(或)：有1为1。常用场景：将特定位设为1。
^(异或)：相同为0，不同为1。重要性质：任何数与自身异或为0（a ^ a = 0），与0异或为自身（a ^ 0 = a）。这是解决“只出现一次的数字”系列题目的核心。
~(取反)：0变1，1变0。
<<(左移)：相当于乘以2的n次方。低位补0。
>>(右移)：相当于除以2的n次方（向下取整）。高位补符号位（算术右移）。
>>>(无符号右移)：高位补0。

常用技巧：

判断奇偶：(n & 1) == 1为奇数。
交换两个数：a ^= b; b ^= a; a ^= b;（无需临时变量，但可读性差，谨慎使用）。
取最低位的1：lowbit = n & (-n)。这是树状数组（Binary Indexed Tree）的核心操作。
消去最低位的1：n = n & (n - 1)。常用于统计二进制中1的个数（Brian Kernighan算法）。
判断是否是2的幂：n > 0 && (n & (n - 1)) == 0。
对2的幂取模：n % (2^k)等价于n & ((1 << k) - 1)。

BigInteger与BigDecimal：当题目涉及远超long范围的大整数运算（比如某些数学题、高精度计算）时，就需要用到BigInteger。它提供了任意精度的整数运算。BigDecimal用于高精度的浮点数运算，避免double的精度损失。使用时注意，它们的对象是不可变的，运算方法返回新对象。

5. 输入输出与调试：刷题的“后勤保障”

LeetCode虽然帮我们处理了输入输出，但了解Java的标准I/O对于理解代码、本地调试和应对其他OJ平台至关重要。

5.1 快速输入输出：`Scanner`与`BufferedReader`

对于数据量较大的输入，Scanner虽然方便，但比较慢。BufferedReader+StringTokenizer或String.split()是更高效的选择。

// 高效读入示例 (适用于本地测试或某些OJ) import java.io.*; import java.util.*; public class FastIO { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); // 或者使用 split String[] parts = br.readLine().split(" "); int a = Integer.parseInt(parts[0]); int b = Integer.parseInt(parts[1]); // 快速输出 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); bw.write("结果: " + (a + b)); bw.newLine(); bw.flush(); // 记得刷新缓冲区 } }

5.2 调试与格式化输出

System.out.println是最常用的调试输出，但在循环中大量调用会影响性能。在需要输出大量数据时，可以考虑使用StringBuilder拼接后一次性输出。

格式化输出：除了String.format，System.out.printf也支持类似C语言的格式化输出，对于控制输出格式非常方便。

double value = 3.1415926; System.out.printf("Value: %.2f, Integer: %d%n", value, 100); // 输出: Value: 3.14, Integer: 100

6. 实战场景串联：API与数据结构的组合拳

理论知识需要结合题目才能融会贯通。我们来看几个经典场景，看看如何运用这些“兵器”。

6.1 场景一：统计频率与Top K问题

题目特征：需要统计元素出现次数，并可能根据频率进行排序或选取。

核心武器：HashMap+PriorityQueue或Bucket Sort（桶排序）。

示例（前K个高频元素）：

使用HashMap统计每个数字出现的频率。
使用PriorityQueue（最小堆）维护频率最高的K个元素。堆内按频率排序，堆顶是频率最小的元素。
遍历HashMap的条目集（entrySet），若堆大小小于K，直接加入；否则，比较当前元素频率与堆顶频率，若更大，则弹出堆顶，加入当前元素。
最后，堆中剩下的就是频率最高的K个元素。

public int[] topKFrequent(int[] nums, int k) { // 1. 统计频率 Map<Integer, Integer> frequencyMap = new HashMap<>(); for (int num : nums) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1); } // 2. 使用最小堆（按频率排序） PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>( Comparator.comparingInt(Map.Entry::getValue) ); // 3. 维护大小为K的堆 for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) { minHeap.offer(entry); if (minHeap.size() > k) { minHeap.poll(); // 弹出频率最小的 } } // 4. 提取结果 int[] result = new int[k]; for (int i = k - 1; i >= 0; i--) { result[i] = minHeap.poll().getKey(); // 注意堆顶是频率最小的，所以倒序放入 } return result; }

技巧：这里使用Map.Entry直接放入堆中，避免了创建额外类。Comparator.comparingInt(Map.Entry::getValue)是Java 8的函数式写法，非常简洁。

6.2 场景二：区间合并与日程安排

题目特征：给出一组区间，需要合并重叠区间、插入新区间或查找空闲时间。

核心武器：排序 + 线性扫描，或TreeMap。

示例（合并区间）：

将所有区间按照起始时间排序（Arrays.sort(intervals, (a, b) -> a[0] - b[0])）。
初始化一个结果列表，放入第一个区间。
从第二个区间开始遍历，比较当前区间与结果列表中最后一个区间：
- 如果当前区间起始时间 <= 最后一个区间的结束时间，说明重叠，则更新最后一个区间的结束时间为两者结束时间的最大值（last[1] = Math.max(last[1], current[1])）。
- 否则，不重叠，将当前区间加入结果列表。

public int[][] merge(int[][] intervals) { if (intervals.length <= 1) return intervals; // 按起始时间排序 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> merged = new ArrayList<>(); merged.add(intervals[0]); for (int i = 1; i < intervals.length; i++) { int[] last = merged.get(merged.size() - 1); int[] current = intervals[i]; if (current[0] <= last[1]) { // 重叠 last[1] = Math.max(last[1], current[1]); // 合并，取最大的结束时间 } else { merged.add(current); // 不重叠，直接加入 } } return merged.toArray(new int[merged.size()][]); }

技巧：对于更复杂的日程安排问题（如LeetCode 729, 731），TreeMap（键为时间点，值为状态）或TreeSet（存储已安排的区间起点）能提供floorKey/ceilingKey等高效查询，是更优解。

6.3 场景三：字符串的排列、子串与滑动窗口

题目特征：在字符串中寻找满足某些条件的子串或排列。

核心武器：滑动窗口 +HashMap（或数组）记录字符频率。

示例（找到字符串中所有字母异位词）：

使用一个固定长度的滑动窗口（长度等于目标词p的长度）。
用两个int[26]数组（或HashMap）分别记录窗口内字符计数和目标词p的字符计数。
初始时，统计p的计数，并初始化第一个窗口的计数。
滑动窗口：每次右移一位，移除左边出去的字符，加入右边新进入的字符，并比较当前窗口计数是否与目标计数相等。

public List<Integer> findAnagrams(String s, String p) { List<Integer> result = new ArrayList<>(); if (s.length() < p.length()) return result; int[] pCount = new int[26]; int[] windowCount = new int[26]; // 初始化p的计数和第一个窗口的计数 for (int i = 0; i < p.length(); i++) { pCount[p.charAt(i) - 'a']++; windowCount[s.charAt(i) - 'a']++; } if (Arrays.equals(pCount, windowCount)) { result.add(0); } // 滑动窗口 for (int i = p.length(); i < s.length(); i++) { // 移除窗口左端字符 windowCount[s.charAt(i - p.length()) - 'a']--; // 加入窗口右端新字符 windowCount[s.charAt(i) - 'a']++; // 比较计数数组 if (Arrays.equals(pCount, windowCount)) { result.add(i - p.length() + 1); } } return result; }

技巧：使用长度为26的数组代替HashMap来统计小写字母频率，效率更高。Arrays.equals用于快速比较两个数组内容是否一致。

7. 性能优化与避坑指南

知道API怎么用只是第一步，用得好、用得对才是关键。这里总结一些实战中容易忽略的性能陷阱和最佳实践。

7.1 集合初始化与容量

预估容量：如前所述，为ArrayList、HashMap、HashSet等预估并设置初始容量（initialCapacity）和负载因子（loadFactor，对于HashMap），能有效避免扩容带来的开销。对于HashMap，如果你知道大概有100个元素，设置new HashMap<>(128)（找一个大于100的2的幂）比默认的16要好。
谨慎使用LinkedList：除非确需频繁的中间插入删除，否则优先使用ArrayList或ArrayDeque。
遍历选择：遍历ArrayList用索引或forEach；遍历LinkedList用Iterator或forEach，避免用get(index)。

7.2 字符串操作

无脑用StringBuilder：在循环内或复杂逻辑中拼接字符串，永远首选StringBuilder。
警惕substring的内存持有：在旧版本Java中，substring会共享原字符串的char[]，可能导致内存泄漏（如果原字符串很大，截取很小一段却无法被GC）。Java 7以后通常已优化，但了解这个历史问题有益无害。在极端性能敏感场景，可以考虑new String(str.substring(...))来强制拷贝。
split的极限情况：String.split()的参数是正则表达式。像split(".")、split("|")会出错，因为.和|是正则元字符，需要转义：split("\\.")、split("\\|")。

7.3 自动装箱与拆箱

集合类（如List<Integer>,Map<Integer, ...>）存储的是对象（Integer），而我们的操作常常是int。这中间涉及自动装箱（int->Integer）和拆箱（Integer->int）。在循环中频繁操作可能会产生大量临时对象，影响性能。在性能瓶颈处，可以考虑使用原始类型数组（如int[]）代替List<Integer>。

7.4 比较器与相等性

Comparator的链式调用：Java 8引入了Comparator.comparing、thenComparing等方法，可以轻松构建复杂的比较逻辑。

// 按年龄升序，年龄相同按姓名降序 people.sort(Comparator.comparingInt(Person::getAge) .thenComparing(Comparator.comparing(Person::getName).reversed()));

重写equals必须重写hashCode：这是HashMap、HashSet正确工作的铁律。两个equals的对象必须有相同的hashCode；但hashCode相同的对象不一定equals。

7.5 并发修改异常

在使用Iterator遍历集合（如ArrayList,HashMap）时，如果直接调用集合自身的add或remove方法修改集合，会抛出ConcurrentModificationException。正确的做法是使用Iterator自身的remove方法，或者使用Java 8的Collection.removeIf方法。