1. 项目概述为什么我们需要一份Java刷题“兵器谱”刷LeetCode对很多Java开发者来说就像一场漫长的修行。你肯定有过这样的经历题目思路清晰逻辑也捋顺了但一动手写代码就卡在了某个细节上——这个集合该用ArrayList还是LinkedList字符串拼接用还是StringBuilder二维数组怎么快速初始化这些看似不起眼的“API选择”和“数据结构理解”往往是决定你代码能否一次通过、运行效率是高是低的关键。更不用说在面试的紧张环境下对这些工具的熟练程度直接体现了你的代码功底和工程素养。这份总结就是为你准备的Java刷题“兵器谱”。它不教你算法思想那是内功心法它专注于为你打磨趁手的“兵器”——那些在LeetCode战场上最高频、最实用的Java API和数据结构核心知识。我的目标是当你看到一道题能立刻反应出该用什么数据结构作为基石该调用哪个API来简化操作从而把精力完全集中在算法逻辑本身。这份总结源于我个人刷题和面试官经验会持续更新力求覆盖你从新手到高手路上遇到的所有“工具性”问题。无论你是正在备战面试还是想系统性提升编码能力这里的内容都能让你少走弯路写代码时更加得心应手。2. 核心数据结构深度解析与选用指南数据结构是算法的载体选错了数据结构再精妙的算法也可能事倍功半。在LeetCode的语境下我们不需要掌握所有数据结构的复杂实现但必须深刻理解其特性、时间复杂度和适用场景。2.1 线性结构数组、链表与双端队列数组 (int[],String[]) 与动态数组 (ArrayList)数组是效率的基石。访问O(1)但大小固定。在LeetCode中涉及频繁按索引访问、数据规模明确且不变的场景原生数组是首选。例如需要原地操作的题目如#26删除有序数组中的重复项使用int[]能避免自动装箱开销代码更简洁。ArrayList是动态数组封装了数组的扩容逻辑。当题目涉及动态添加元素且需要随机访问时它就是最佳选择。关键要明白其扩容成本默认容量10每次扩容为1.5倍。因此在能预估最大数据量的情况下如#1两数之和你知道答案最多两个数使用ArrayList时最好用new ArrayList(initialCapacity)指定初始容量避免多次扩容。注意ArrayList的remove(int index)方法是O(n)的因为它需要移动后续所有元素。在需要频繁从中间删除元素的场景这是一个性能陷阱。链表 (LinkedList)LinkedList实现了双向链表。它的优势在于头尾的插入删除都是O(1)。在需要实现栈、队列、或频繁在序列中间进行插入删除操作时尤其是当这些操作无法通过索引直接定位需要遍历查找时LinkedList比ArrayList更有优势。例如#146LRU缓存机制的一种实现就需要在链表中快速移动节点。 但它的劣势同样明显随机访问需要遍历是O(n)。所以除非题目特性与链表操作强相关否则在需要按索引频繁访问的场景下应避免使用。双端队列 (ArrayDeque)这是被严重低估的利器。ArrayDeque是一个基于可扩容循环数组实现的双端队列。它既可以在两端高效地添加/删除元素O(1)也支持栈push/pop和队列offer/poll的操作。在LeetCode中它的应用场景极广实现栈完全可以用ArrayDeque替代Stack类后者是线程安全的但性能较差不推荐。push(E e)和pop()方法完美对应。实现队列用于BFS广度优先搜索时offer(E e)入队poll()出队。滑动窗口最大值/最小值#239这是它的高光场景。你需要一个能在两端操作且能快速访问最大/最小值的结构。ArrayDeque可以存储索引或值配合单调队列思想能在线性时间内解决问题。2.2 集合框架Set与Map的实战抉择哈希集合 (HashSet) 与哈希映射 (HashMap)这是使用频率最高的两个数据结构核心在于O(1)时间复杂度的查找。HashSet用于快速判断元素是否存在。例如#217存在重复元素直接遍历加入HashSet利用add方法返回false的特性即可判断。HashMap用于存储键值对建立映射关系。经典应用是#1两数之和遍历数组将(target - nums[i], i)存入Map后续查找补数是否存在。选用要点自定义对象作为Key必须正确重写hashCode()和equals()方法。这是面试高频考点。在刷题中如果要用一个int[2]数组如坐标或List作为Key更常见的做法是将其转换为字符串如”x,y”或者使用Map嵌套如MapInteger, MapInteger, V。初始化容量和ArrayList类似如果能预估大小最好在构造函数中指定初始容量减少扩容rehash带来的性能损耗。例如已知数组长度n用于存储其元素的HashMap可以初始化为new HashMap(n)。树形集合 (TreeSet) 与树形映射 (TreeMap)它们基于红黑树实现元素是有序的按自然顺序或自定义Comparator。查找、插入、删除的时间复杂度是O(log n)。适用场景需要维护一个动态有序集合并频繁进行范围查询、获取最大/最小值时。例如#220存在重复元素 III可以利用TreeSet的ceiling(e)和floor(e)方法在O(log k)时间内找到滑动窗口内与当前值最接近的元素。与HashSet/HashMap的权衡除非题目明确要求有序性或者需要用到ceiling/floor/higher/lower这些有序操作否则优先选择Hash系列以获得O(1)的常数级性能。2.3 优先队列 (PriorityQueue)理解其堆的本质PriorityQueue是一个基于优先级堆的无界队列。默认是小顶堆最小元素在队头。这是解决“Top K”、“数据流中位数”、“最短路径”等问题的核心工具。核心操作offer(E e)和poll()是O(log n)peek()是O(1)。自定义排序通过传入Comparator可以轻松实现大顶堆或复杂排序。例如#347前K个高频元素我们需要一个按频率排序的小顶堆可以这样初始化PriorityQueueMap.EntryInteger, Integer pq new PriorityQueue((a, b) - a.getValue() - b.getValue());性能陷阱PriorityQueue的remove(Object o)方法是O(n)的因为它需要线性扫描来定位元素。所以不要用它来做需要频繁删除非队头元素的操作。对于Dijkstra算法一旦节点的距离被更新需要先删除旧节点再插入新节点或者采用“惰性删除”策略标记旧节点无效遇到时跳过。3. Java常用API精讲与避坑指南掌握了数据结构就像有了好兵器但还得精通招式——也就是API。Java标准库提供了丰富的API用对了事半功倍用错了或理解不透就会掉进坑里。3.1 字符串 (String) 操作不可变性的利与弊String的不可变性是Java设计的核心之一也带来了独特的用法和坑点。拼接性能String的拼接在循环中会产生大量中间String对象性能极差。绝对禁止在循环中使用str1 str2。正确的做法是使用StringBuilder单线程或StringBuffer多线程。例如反转字符串#344或者构建路径时StringBuilder的append()和reverse()方法是首选。相等比较比较的是对象引用equals()比较的是内容。在刷题中除了极少数需要判断是否是同一个对象的场景一律使用equals()。对于字符串字面量Java会将其放入常量池有时可能碰巧成立但这绝不是可靠的写法。常用方法charAt(int index) O(1) 访问比先转char[]再访问在某些场景下更直观。substring(int beginIndex, int endIndex) 注意参数是前闭后开区间[begin, end)。在JDK 7之后substring会创建新字符串而非共享原字符数组不用担心内存泄漏但也要注意其O(n)的时间复杂度需要复制。toCharArray() 当需要对字符串中每个字符进行频繁修改或访问时先转为char[]数组进行操作最后再new String(charArray)构造结果通常比直接操作String更高效。3.2 数组工具类 (Arrays) 与集合工具类 (Collections)这两个工具类提供了大量静态方法能极大简化代码。Arrays类sort(int[] a) 对数组排序刷题基础中的基础。对于对象数组可以传入Comparator。binarySearch(int[] a, int key) 二分查找。重要前提数组必须是有序的返回值找到则返回索引未找到则返回-(插入点) - 1。这个“插入点”信息有时很有用。fill(int[] a, int val) 填充数组。copyOfRange(int[] original, int from, int to) 复制数组指定范围同样是前闭后开。asList(T... a) 将数组转为List。巨坑警告这个方法返回的List如Arrays.asList(1,2,3)是一个固定大小的列表不支持add()和remove()等结构性修改操作会抛出UnsupportedOperationException。如果需要一个可变的List请使用new ArrayList(Arrays.asList(...))。Collections类sort(ListT list) 对List排序。reverse(List? list) 反转列表。swap(List? list, int i, int j) 交换列表中两个位置的元素。在需要原地操作List的算法中如洗牌算法#384非常方便。max(Collection? extends T coll)/min(...) 获取集合中的最大/最小值。对于自定义对象需实现Comparable或传入Comparator。3.3 数学与随机数 (Math,Random)Math类 提供了基本的数学运算常量和方法。刷题常用Math.max(int a, int b)/min(...) 快速比较。Math.abs(int a) 取绝对值。注意对Integer.MIN_VALUE取绝对值结果仍是负数因为补码表示这是一个潜在的边界条件坑点。Math.pow(double a, double b) 幂运算。返回double注意精度和类型转换。Random类 生成伪随机数。在需要随机化的算法中如快速排序的随机化分区非常有用。Random rand new Random(); int randomIndex left rand.nextInt(right - left 1); // 生成[left, right]范围内的随机整数注意nextInt(n)返回的是[0, n)范围的整数。3.4 输入输出与格式化 (Scanner,System.out)虽然LeetCode的核心是写解决方法但有时你需要本地测试。Scanner是常用的输入工具但要注意其性能不如BufferedReader。对于大量数据输入建议使用BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String line; while ((line br.readLine()) ! null) { // 处理每一行 }输出则简单使用System.out.println()即可。对于需要格式化输出的场景如保留小数String.format()或System.out.printf()是更好的选择。4. 刷题场景下的高效编码模式与模板知道用什么和怎么用之后我们需要形成一些肌肉记忆将常用的操作模式化、模板化以提升编码速度和准确性。4.1 集合的初始化与遍历初始化并填充数据// 列表 ListInteger list new ArrayList(Arrays.asList(1, 2, 3, 4, 5)); // 或者动态添加 for (int i 0; i n; i) { list.add(i); } // 映射 MapCharacter, Integer map new HashMap(); for (char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) 1); // 经典计数模式 }getOrDefault(key, defaultValue)方法在计数、频率统计等场景下极其常用避免了冗长的if-else判断。遍历Map// 遍历键值对最常用 for (Map.EntryInteger, Integer entry : map.entrySet()) { int key entry.getKey(); int value entry.getValue(); // ... } // 仅遍历键或值 for (int key : map.keySet()) { /* ... */ } for (int value : map.values()) { /* ... */ }4.2 数组与列表的转换这是刷题中的高频操作。// 1. 基本类型数组转List麻烦需要装箱 int[] arr {1, 2, 3}; ListInteger list new ArrayList(); for (int num : arr) { list.add(num); } // Java 8 流式操作简洁但效率略低刷题中可接受 ListInteger list2 Arrays.stream(arr).boxed().collect(Collectors.toList()); // 2. List转数组 Integer[] boxedArray list.toArray(new Integer[0]); // 推荐使用 new T[0] 的写法性能最佳 int[] primitiveArray list.stream().mapToInt(i - i).toArray(); // 转回基本类型数组 // 3. 二维列表初始化 ListListInteger result new ArrayList(); // 添加一个新行 result.add(new ArrayList()); result.get(0).add(1);4.3 字符串与字符数组的互操作String s hello; // String - char[] char[] charArray s.toCharArray(); // 修改charArray charArray[0] H; // char[] - String String newStr new String(charArray); // Hello // 使用StringBuilder构建 StringBuilder sb new StringBuilder(); for (char c : charArray) { sb.append(c); } String finalStr sb.toString();4.4 自定义排序的几种写法排序是算法核心自定义Comparator必须熟练掌握。// 1. 对数组排序例如按绝对值大小降序 Integer[] nums {3, -1, -5, 2}; Arrays.sort(nums, (a, b) - Integer.compare(Math.abs(b), Math.abs(a))); // 2. 对List排序 Listint[] intervals ...; // 假设每个int[]是[start, end] // 按起点升序起点相同按终点降序 intervals.sort((a, b) - a[0] ! b[0] ? a[0] - b[0] : b[1] - a[1]); // 3. 定义PriorityQueue的排序规则大顶堆 PriorityQueueInteger maxHeap new PriorityQueue((a, b) - b - a); // 注意b-a可能导致溢出更安全的写法是 PriorityQueueInteger maxHeapSafe new PriorityQueue(Collections.reverseOrder()); // 或者 PriorityQueueInteger maxHeapSafe2 new PriorityQueue((a, b) - Integer.compare(b, a));5. 内存、性能与边界问题实战排查即使算法正确也可能因为内存溢出、性能低下或边界条件处理不当而失败。这部分是区分普通通过和优雅通过的关键。5.1 警惕自动装箱与拆箱ListInteger、HashMapInteger, ...中存储的是Integer对象而非int基本类型。频繁的装箱int-Integer和拆箱Integer-int会带来额外的性能开销和内存占用。在性能要求极高的循环内部如深度优先搜索DFS的递归中可以考虑使用原生数组int[]代替ListInteger或者使用Trove、FastUtil等第三方库但LeetCode环境不支持。一个常见的优化点是在需要将int作为Map的Key时如果Key的范围有限且连续可以考虑用数组替代Map用索引映射Key值存储在该索引位置。5.2 递归的深度与栈溢出Java的栈深度是有限的通常由-Xss参数设定默认可能只有几百KB到1MB。在进行深度递归如树的深度遍历、复杂的回溯时很容易引发StackOverflowError。对策对于可能很深的递归考虑能否用迭代显式栈Deque的方式改写。例如二叉树的中序遍历递归写法简洁但迭代写法使用栈更安全。对于回溯算法如果解空间非常大也需要留意递归深度。5.3 循环中的字符串拼接前文已强调这里再列为一个独立问题。在任何循环中拼接字符串必须使用StringBuilder。错误示范String result ; for (String str : list) { result str; // 每次循环都创建新的StringBuilder和String对象 }正确做法StringBuilder sb new StringBuilder(); for (String str : list) { sb.append(str); } String result sb.toString();5.4 边界条件与特殊输入这是面试官考察代码健壮性的重点。空值 (null) 方法接收的String、int[]、List是否为null如果题目没说明通常假设不为空但自己写工具方法时要考虑。空集合/空字符串 输入是””、[]、new int[0]时你的算法能否正确处理返回值应该是什么整数溢出 这是最隐蔽的坑。例如计算两个int的平均值使用(a b) / 2在ab超过Integer.MAX_VALUE时会溢出。应使用a (b - a) / 2或(a b) ((a ^ b) 1)。在计算中间结果可能很大时如阶乘、组合数考虑使用long。索引越界 在访问数组、字符串、列表之前务必检查索引i是否满足0 i length。特别是在使用while循环移动指针如快慢指针、滑动窗口时循环条件要仔细设计。浮点数比较 不要用比较double或float由于精度问题应判断两者差的绝对值是否小于一个极小值如1e-6。// 错误 if (a b) { ... } // 正确 if (Math.abs(a - b) 1e-6) { ... }5.5 利用位运算进行优化在一些特定场景位运算能极大提升性能并简化代码。判断奇偶(n 1) 1为奇 0为偶。比n % 2更快。取最低位的1lowbit n (-n)。常用于树状数组。判断是否是2的幂n 0 (n (n - 1)) 0。交换两个数a ^ b; b ^ a; a ^ b;炫技但不一定比用临时变量快且可读性差慎用。乘除2的幂n 1等价于n * 2n 1等价于n / 2对于正数。在性能敏感的循环中可以考虑。6. 结合算法思想的API与数据结构应用实例理论知识需要结合实战。下面我们看几个经典问题如何将合适的API和数据结构应用到具体算法中。6.1 哈希表在“两数之和”类问题中的核心地位#1两数之和是哈希表的招牌题。其核心思想是“用空间换时间”将查找时间从O(n)降到O(1)。public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement)) { return new int[]{map.get(complement), i}; } map.put(nums[i], i); // 存放的是数值 索引 } return new int[0]; }要点为什么先查找再放入为了避免同一个元素被使用两次。例如nums [3, 3], target 6如果先放入在检查第二个3时会找到自己。6.2 双端队列实现单调队列解“滑动窗口最大值”#239滑动窗口最大值是单调队列的经典应用。我们需要一个数据结构能快速获取窗口内的最大值同时能在窗口滑动时高效地添加新元素和移除旧元素。ArrayDeque完美胜任。public int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0) return new int[0]; int n nums.length; int[] result new int[n - k 1]; DequeInteger deque new ArrayDeque(); // 存储的是索引方便判断是否在窗口内 for (int i 0; i n; i) { // 1. 移除队首不在窗口内的元素 while (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } // 2. 维护队列单调递减从队尾移除所有小于当前值的元素索引 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 3. 将当前索引入队 deque.offerLast(i); // 4. 当窗口形成时队首元素即为当前窗口最大值 if (i k - 1) { result[i - k 1] nums[deque.peekFirst()]; } } return result; }要点Deque里存的是索引而不是值这样才能判断元素是否还在滑动窗口内。维护的是一个“索引值单调递减”的队列。6.3 优先队列在“Top K”与“数据流中位数”问题中的应用#215数组中的第K个最大元素可以用快速选择算法O(n)平均但用堆更直观。思路维护一个大小为K的小顶堆。遍历数组当堆大小小于K时直接加入否则如果当前数大于堆顶堆中最小的数则弹出堆顶加入当前数。遍历完成后堆顶就是第K大的数。public int findKthLargest(int[] nums, int k) { PriorityQueueInteger minHeap new PriorityQueue(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() k) { minHeap.poll(); // 弹出最小的 } } return minHeap.peek(); }对于#295数据流的中位数则需要维护两个堆一个大顶堆left存储较小的一半一个小顶堆right存储较大的一半。始终保持两个堆的大小平衡相等或left比right多一个中位数就可以从堆顶快速获得。添加数字时需要根据当前数字与堆顶的大小关系决定放入哪个堆并动态调整平衡。6.4 并查集Union-Find的数据结构实现并查集不是Java标准库的一部分但在解决连通性、分组问题如#547省份数量、#200岛屿数量时极其高效。我们需要自己实现。class UnionFind { private int[] parent; private int[] rank; // 按秩合并优化树高 private int count; // 连通分量个数 public UnionFind(int n) { parent new int[n]; rank new int[n]; count n; for (int i 0; i n; i) { parent[i] i; // 初始时每个节点自成一派 } } // 查找根节点带路径压缩 public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩 } return parent[x]; } // 合并两个集合 public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; } public int getCount() { return count; } }要点find操作中的路径压缩以及union操作中的按秩合并是保证并查集接近常数时间复杂度的关键。这个模板需要背熟。7. 持续更新与进阶资源指引刷题是一个持续的过程Java的API和最佳实践也在不断演进。这里列出一些值得持续关注和深入学习的点Java 8 的Stream API与Lambda表达式 在现代Java开发中Stream API可以极大简化集合操作。虽然在算法题中为了极致的性能和控制力我们可能仍多用传统循环但了解它们是有益的。例如用一行代码完成数组求和、过滤、映射等操作可以让代码更简洁。// 计算数组中偶数的平方和 int sum Arrays.stream(nums) .filter(n - n % 2 0) .map(n - n * n) .sum();关注java.util包下的新工具 例如Objects.equals()用于安全的空值比较Map.of()、List.of()、Set.of()用于创建不可变集合Java 9它们在编写测试用例或配置数据时很方便。深入理解JCFJava Collections Framework的源码 时间允许的话阅读ArrayList、HashMap、PriorityQueue的源码。你会真正理解扩容机制、哈希冲突解决、红黑树化JDK8的HashMap、堆调整等过程这对你分析算法时空复杂度、做出最优选择有根本性的帮助。建立自己的代码片段库 将本文提到的以及你在刷题过程中总结出的高效模板如快速排序、二分查找、DFS/BFS框架、并查集、树状数组、线段树等保存下来。定期回顾形成肌肉记忆。最后记住工具是为人服务的。不要为了使用某个酷炫的API或数据结构而强行使用。始终从问题本身出发分析其数据特性和操作需求选择最朴素、最直接、最高效的工具。这份总结会持续更新希望能成为你LeetCode之旅中一份可靠的随行参考。当你对某个API的用法犹豫不决时回来看看或许能找到答案。