做了四五年算法题Java 从入门到刷穿最深的体会是大部分字符串题和排序题卡人的根本不是思路而是 API 记不熟、边界处理踩坑。明明知道这题该用哈希表统计频率结果在charAt和toCharArray之间犹豫半天明明排序思路已经写出来了Comparator 的返回值写反直接 WA 到怀疑人生。这篇文章我把刷题这些年积累的 Java 字符串和排序常用语法做一次系统整理全部是可直接抄的模板和踩坑实录面向正在刷 LeetCode、蓝桥杯、牛客或者准备 Java 面试的朋友希望能帮你省下查文档的时间把精力留给真正的逻辑思考。1. 字符串处理先记住这套最常用的 API字符串在 Java 里是一个很特殊的类型它是不可变对象每次修改都会生成新对象。刷题时如果不注意这一点经常会在循环里写出O(n^2)的拼接代码而不自知。下面这套 API 是按使用频率排的优先级最高的是遍历和子串操作。1.1 基础读写与遍历先说一下怎么拿字符串里的字符。str.charAt(i)是最基础的返回 char 类型。str.length()拿长度这里注意是方法不是属性很多从 C 转过来的朋友会下意识写成str.length编译直接报错。遍历字符串有两种常用姿势// 方式一charAt 下标需要访问相邻字符时用这个 for (int i 0; i s.length(); i) { char c s.charAt(i); } // 方式二转字符数组需要频繁读写或交换字符时用这个 char[] chars s.toCharArray(); for (char c : chars) { System.out.println(c); }这两种方式我都有大量使用场景。比如判断括号匹配、回文串检查用下标方式方便同时操作left和right两个指针而字符统计、替换、排序字符直接转数组更方便。实测下来toCharArray在性能上略优于反复charAt因为省去了每次越界检查的损耗但在一般算法题里差距可以忽略选自己顺手的方式就行。substring 是另一个高频操作注意它是左闭右开区间String s hello world; // 从下标 0 开始取到下标 5不含结果是 hello String sub s.substring(0, 5); // 只有一个参数时取到字符串末尾 String tail s.substring(6); // world我在这里踩过不止一次坑substring(0, 5)取的是 0 到 4 这五个字符不是到下标 5。写边界时建议先心里默念一遍“左闭右开”特别是做二分、滑动窗口这类题目时边界错一个全盘皆输。1.2 值判断与控制流字符串比较是个经典考点。内容比较用equals忽略大小写用equalsIgnoreCase千万别用。比较的是引用地址只有 JVM 字符串常量池里的字面量才可能相等运行时 new 出来的字符串哪怕内容相同也是 false。这在面试里几乎是必问题。判断空串或 null 时推荐用 Apache Commons 的StringUtils但刷题环境下我们直接用 JDK 自带方法// 判空长度为 0 或内容为空的字符串 if (s null || s.isEmpty()) { // 注意顺序先判 null 再判 isEmpty避免空指针 } // 判断是否包含子串 if (s.contains(abc)) { } // 判断前缀 / 后缀 if (s.startsWith(prefix)) { } if (s.endsWith(.java)) { }还有一个使用频率特别高的方法是字符类型判断。判断一个字符是不是数字、字母以前我还手写过正则去匹配后来发现 JDK 的 Character 类直接就有Character.isDigit(c); // 是否是数字 Character.isLetter(c); // 是否是字母 Character.isLetterOrDigit(c); // 是否是字母或数字 Character.isUpperCase(c); // 是否大写 Character.isLowerCase(c); // 是否小写 Character.isWhitespace(c); // 是否空白这里的坑点在于isLetter和isLetterOrDigit对中文字符也会返回 true因为中文在 Unicode 里属于字母。题目如果要求“英文字母”记得加范围判断(c a c z) || (c A c Z)或者自己写个静态方法。1.3 拆分、拼接与替换split是字符串处理里能让你摔得最痛的方法之一。它接收的参数是正则表达式不是普通字符串。按点号拆分时不能写成s.split(.)正则里点号代表任意字符要转义成s.split(\\.)。按竖线拆分同样要转义s.split(\\|)。还有一个容易被忽略的点split会丢掉末尾的空字符串。比如a,b,.split(,)结果是[a, b]末尾那个空串没了。如果你需要保留可以用s.split(,, -1)第二个参数表示保留所有空串。拼接方面普通字符串拼接用加号就行但循环里禁止这么做。JVM 对加号拼接有优化但循环体内多次拼接仍然会创建大量中间对象。正确做法是下面说的 StringBuilder。替换操作有三兄弟很多人分不清String s a.b.c; // replace参数是字面量替换所有匹配 s.replace(., -); // a-b-c // replaceAll参数是正则替换所有匹配 s.replaceAll(\\., -); // a-b-c // replaceFirst参数是正则替换第一个匹配 s.replaceFirst(\\., -); // a-b.c日常刷题最常用的是replacereplaceAll因为走正则性能反而更差。1.4 字符统计与去重模板字符串题里最常出现的需求就是统计字符频率。我见过用嵌套循环硬算的字符一多直接超时。标准答案是长度 26 或 128 的数组配合一个 for 循环// 统计小写字母频率 String s aabbbccc; int[] count new int[26]; for (char c : s.toCharArray()) { count[c - a]; } // 如果包含大小写用 128 位数组覆盖 ASCII int[] asciiCount new int[128]; for (char c : s.toCharArray()) { asciiCount[c]; }这个模板在判断异位词、找重复字符、最长无重复子串、字符串排列等题目里是基础中的基础。字符减a得到 0 到 25 的下标减0可以把数字字符转成真正的数字这个技巧后面还会提到。去重排序也有固定套路。字符串转 char 数组排序再拼回字符串String sorted new String(chars); // 直接由字符数组构造字符串这里注意不要用chars.toString()那拿到的是数组对象的地址不是内容。1.5 StringBuilder刷题效率的关键StringBuilder 是可变字符串在频繁修改场景下比 String 高效得多底层是 char 数组append 是在数组尾部追加。它还有三个高频方法StringBuilder sb new StringBuilder(); sb.append(a); // 追加 sb.insert(0, x); // 头部插入 sb.reverse(); // 反转常用在回文判断 sb.setCharAt(i, c); // 修改指定位置字符反转操作是字符串题里一个非常讨巧的技巧。判断回文串直接比较字符串和它的反转是否相等字符串加法那类题把长字符串反转之后再顺序处理能省去大量边界判断。stringBuilder.reverse()不用白不用底层也是 O(n)比自己撸循环靠谱多了。// 判断回文串一行流 boolean isPalindrome s.equals(new StringBuilder(s).reverse().toString()); // 注意equals 比较内容所以 StringBuilder 要转回 String2. 排序题的三种实现路径排序题在 Java 里是最幸福的因为 JDK 自带排序足够强大绝大多数场景不需要手写。但前提是你会用、用对。我按照使用的复杂度从低到高来讲。2.1 数组排序Arrays.sort对基本类型数组排序是最简单的int[] arr {3, 1, 4, 1, 5, 9, 2, 6}; Arrays.sort(arr); // 升序1 1 2 3 4 5 6 9 Arrays.sort(arr, 0, 5); // 只排序 [0, 5) 区间这里有个隐藏知识点Arrays.sort对基本类型数组使用双轴快速排序对对象数组使用 TimSort稳定归并排序变体。所以如果你需要稳定的排序结果即相同元素的相对次序不变并且数据是对象JDK 的排序默认就能保证。但如果数据是基本类型 int[]你可不能说稳定——快速排序是不稳定的虽然刷题时很少用到这个性质但面试时被问到就得说得出来。对数组按倒序排基本类型数组没有直接的一行 API需要转成包装类// 方法一包装类数组 Comparator.reverseOrder() Integer[] boxed Arrays.stream(arr).boxed().toArray(Integer[]::new); Arrays.sort(boxed, Comparator.reverseOrder()); // 方法二先升序再逆序输出数组本身顺序不变 Arrays.sort(arr); for (int i arr.length - 1; i 0; i--) { System.out.print(arr[i] ); }如果只是想拿最大的几个数不需要全排序。用优先队列维护大小为 k 的最小堆更高效后面会展开讲。2.2 集合排序Collections.sort 与 Comparator集合排序用Collections.sort或 List 自带的sort方法。Java 8 之后更推荐用 list.sortListInteger list new ArrayList(Arrays.asList(3, 1, 4, 1, 5)); Collections.sort(list); // 升序 Collections.sort(list, Collections.reverseOrder()); // 降序 // Java 8 推荐写法 list.sort(Comparator.naturalOrder()); // 升序 list.sort(Comparator.reverseOrder()); // 降序真正有技术含量的是自定义 Comparator。比如按字符串长度排序ListString words Arrays.asList(apple, banana, cherry, date); // 先按长度升序长度相同按字典序 words.sort(Comparator.comparingInt(String::length) .thenComparing(Comparator.naturalOrder()));这一段写法非常优雅拆开讲就是comparingInt(String::length)表示以字符串长度作为比较键thenComparing表示前一个比较结果相等时再用字典序做二次比较Comparator.comparingInt避免了装箱比comparing更省性能。Java 8 的 Lambda 让自定义排序代码变得非常简洁我刷算法题时很少写匿名内部类了全部用 Lambda 一行流。但这里有个巨大的坑下面第 4 章会专门讲 Comparator 的返回值陷阱。2.3 稳定排序、对象排序与 TreeMap如果排序对象是二维数组或者自定义对象Comparator结合 Lambda 最顺手。我以二维数组按照第二列升序排序为例这个场景在贪心算法题里高频出现int[][] intervals {{1, 3}, {2, 2}, {4, 1}}; Arrays.sort(intervals, (a, b) - a[1] - b[1]); // 结果{{4, 1}, {2, 2}, {1, 3}}注意这里接收的是二维数组数组的每个元素是一维数组a[1] - b[1]表示按每个子数组的第二个元素升序排列。区间调度、会议室安排、合并区间这类题全靠这一行。同样的套路还能扩展到按字符串某个字符排序、按对象的多个字段排序// 按对象的 age 字段降序age 相同按 name 字典序升序 people.sort(Comparator.comparing(Person::getAge).reversed() .thenComparing(Person::getName));TreeMap 和 TreeSet 也值得一提。它们是按 key 排序的 Map 和 Set构造时可以传入自定义比较器// 按 key 降序的 TreeMap TreeMapInteger, String map new TreeMap(Comparator.reverseOrder()); // 按字符串长度排序的 TreeSet TreeSetString set new TreeSet(Comparator.comparingInt(String::length));它们底层是红黑树插入、删除、查找都是 O(log n)。如果你需要一套有序的数据结构直接用 TreeMap 比“排序 数组”更灵活。但注意 TreeSet 去重依据的是比较器返回 0 的情况如果要保证完全去重比较器必须能区分所有不同元素。2.4 自定义类的排序写法当题目的数据模型稍微复杂一点比如候选人对象包含姓名、年龄、分数除了传 Comparator 之外还有一个常见做法是让类实现Comparable接口class Person implements ComparablePerson { String name; int age; int score; Override public int compareTo(Person other) { // 先按分数降序分数相同按年龄升序年龄相同按姓名字典序 if (this.score ! other.score) { return other.score - this.score; // 降序 } if (this.age ! other.age) { return this.age - other.age; // 升序 } return this.name.compareTo(other.name); } }实现Comparable的类可以直接调用Arrays.sort(people)或Collections.sort(list)完成排序因为 JDK 的排序方法默认使用自然顺序。我在实际做题中更推荐传Comparator的外部比较方式因为同一个类可能需要按评分排、按年龄排、按拼音排写死在类里的compareTo不够灵活。不过面试手撕代码时Comparable是常考点两种写法都得会。3. 需要手写排序的场景有的题目会明确要求手写排序或者数据规模、性质特殊比如链表排序、海量数据这时候需要自己有模板。这里给出三个核心实现都是我调过很多版本之后留下的稳定模板。3.1 快速排序模板快排的核心是分治选一个基准值把数组分成小于基准和大于基准两部分再递归排序。面试最常让你写的是快排因为空间复杂度 O(log n)、常数小是很多场景的首选。下面这个模板我用了很久关键是随机选基准避免最坏情况public void quickSort(int[] nums, int left, int right) { if (left right) return; // 随机选基准避免对已排序数组退化到 O(n^2) int pivotIdx left new Random().nextInt(right - left 1); swap(nums, pivotIdx, right); // 基准放最后 int pivot nums[right]; int i left; // i 指向小于基准区的边界 for (int j left; j right; j) { if (nums[j] pivot) { swap(nums, i, j); } } swap(nums, i, right); // 基准归位 quickSort(nums, left, i - 1); quickSort(nums, i 1, right); } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; }这个模板是典型的 Lomuto 分区法代码短、好记。i这个指针维护的是“小于基准的区域的右边界”每次发现比基准小的数就把它交换到前面。最后i的位置就是基准的最终位置。快排在笔试中遇到的另一个高频变体是求第 k 大元素TopK 问题快排每次递归都能确定一个元素的最终位置如果这个位置正好是 n-k那它就是答案不需要完全排序。这个思路面试很喜欢问能顺手答出“快选”算法会加分。3.2 归并排序模板归并排序的特点是稳定、时间复杂度稳定在 O(n log n)、适合链表和外部排序。它的缺点是空间复杂度 O(n)需要额外数组辅助。但归并排序的模板同时也是很多算法题的基础比如求逆序对数量、链表排序都建立在归并思想上。public void mergeSort(int[] nums, int left, int right, int[] temp) { if (left right) return; int mid (left right) 1; // 无符号右移防 int 溢出 mergeSort(nums, left, mid, temp); mergeSort(nums, mid 1, right, temp); merge(nums, left, mid, right, temp); } private void merge(int[] nums, int left, int mid, int right, int[] temp) { int i left, j mid 1, t 0; while (i mid j right) { if (nums[i] nums[j]) { temp[t] nums[i]; } else { temp[t] nums[j]; } } while (i mid) temp[t] nums[i]; while (j right) temp[t] nums[j]; // 拷贝回原数组 t 0; while (left right) { nums[left] temp[t]; } }这里的细节是(left right) 1用无符号右移而不是(left right) / 2因为 left 和 right 特别大时相加可能溢出成负数。虽然算法题里数据规模一般达不到但面试官问起时能说出这个点会显得你基本功扎实。归并排序还可以“顺便”统计逆序对在合并时如果右边数组当前元素小于左边说明左边剩余的所有元素都比它大逆序对数量直接加mid - i 1。这是剑指 Offer 原题掌握归并模板等于同时掌握了这道题。3.3 堆排序模板堆排序的代码长度是三种排序里最长的但它在“排序的同时维护动态最大/最小”的场景下不可替代。Java 刷题时PriorityQueue 底层就是堆工具类解决大部分问题真正手写堆排序一般在面试中遇到。public void heapSort(int[] nums) { int n nums.length; // 建堆从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; i--) { siftDown(nums, i, n - 1); } // 排序堆顶最大值交换到最后再调整 for (int i n - 1; i 0; i--) { swap(nums, 0, i); // 当前最大值归位 siftDown(nums, 0, i - 1); // 重新调整 } } private void siftDown(int[] nums, int parent, int end) { while (parent * 2 1 end) { int left parent * 2 1; int right left 1; int largest left; if (right end nums[right] nums[left]) { largest right; } if (nums[parent] nums[largest]) break; swap(nums, parent, largest); parent largest; } }实际刷题时堆排序更多体现为“用 PriorityQueue 实现 TopK”// 取前 K 大的数维护一个大小为 K 的最小堆 PriorityQueueInteger minHeap new PriorityQueue(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() k) { minHeap.poll(); // 弹出最小值堆里保留最大的 k 个 } }这个思路在“数据流中的第 K 大元素”“前 K 个高频单词”里都是标准解法。堆里的元素充满动态变化用 PriorityQueue 比每次都全排序高效得多。3.4 刷题场景下的选择建议到了真正做算法题的场景我的建议是能用 JDK 排序就不用自己写。Arrays.sort经过无数优化比绝大多数手写实现都要快。手写排序只发生在几种情况题目明确禁止使用现成排序、排序对象是链表Collections.sort对链表也用归并可以直接用、面试官要求手写考察基本功。硬要手写的话我自己的选择是先背熟快排模板和归并模板。快排应对绝大多数数组排序需求归并应对需要稳定排序或统计逆序对的场景。堆排序更多是理解 PriorityQueue 的底层原理理解了才知道它为什么能做到 O(log n) 的动态维护。4. 实战中高频踩坑与排查下面这些坑每一个我都付出过 WAWrong Answer的代价有的是代码写错了有的是编译都没过有的是逻辑没毛病但就是跑不过。整理成清单你在比赛中遇到类似症状可以直接对照排查。4.1 equals 和 的混淆顶级的低级错误。字符串比较必须用equals这个没人不知道但实战中容易出错的地方是判断null。如果你写str.equals(abc)而str是 null直接空指针异常。正确的姿势是把常量放前面if (abc.equals(str)) { } // str 为 null 时不会空指针返回 false还有一个场景是自动装箱带来的坑。比较 Integer 对象时Integer a 127, b 127; a b返回 true但Integer a 128, b 128; a b返回 false。因为 Integer 缓存池默认范围是 -128 到 127超出范围会创建新对象。所以永远不要用比较包装类全部用equals或intValue()。4.2 字符与数字的互相转换字符转数字是个高频坑点。char类型的5转为 int直接强转得到的是 ASCII 码 53不是数字 5。正确做法char c 5; // 方式一减字符 0 int num c - 0; // 5 // 方式二Character.getNumericValue int num2 Character.getNumericValue(c); // 5数字转字符反过来加0int num 5; char c (char)(num 0); // 5整数字符串解析成数字用Integer.parseInt但这只对 int 范围内的有效。超过 int 上限要用Long.parseLong。需要支持任意进制时用Integer.parseInt(str, radix)比如Integer.parseInt(1010, 2)得到 10。Integer.valueOf也能转但返回的是 Integer 包装类如果只想要基本类型用parseInt更干脆、避免不必要的装箱。4.3 split 的边界行为前面提到过 split 的两个坑参数是正则、末尾空串丢失。我再补充一个当字符串本身为空串时.split(,)返回的是长度为 1 的数组[]不是空数组。这在解析 CSV 行数据时很容易出错判断时别用str.split(,).length 0而是先判断字符串是否为 null 或 isEmpty。如果想把字符串按任意长度空白拆分空格、tab、换行正则这样写String[] parts s.split(\\s);\\s匹配所有空白字符表示一个或多个。这个在 ACM 模式输入读取时很常用。4.4 Comparator 返回值的陷阱Comparator 的compare方法约定是返回负数表示第一个参数排在前面返回正数表示第二个参数排在前面返回 0 表示相等。这个规则我反复忘每次都在纸上推演一遍。但更大的坑是直接return a - b。这行代码在两组数在 int 范围内相减可能溢出当 a 是 2147483647、b 是 -2147483648 时a - b超出 int 范围变成负数排序结果就是错的。推荐用比较器自带的静态方法// 安全写法不会溢出 list.sort(Comparator.comparingInt(x - x)); // 或者 Integer.compare list.sort((a, b) - Integer.compare(a, b));同理compareTo也可以直接调用String类型直接让a.compareTo(b)JDK 已经帮我们实现了。4.5 StringBuilder 的容量与多线程问题StringBuilder 默认容量是 16如果频繁 append 超过容量底层会自动扩容并拷贝原数组有性能损耗。已知待拼接字符串较长时先指定容量new StringBuilder(initialCapacity);另外 StringBuilder 不是线程安全的多线程环境中拼接字符串必须用StringBuffer但同步也有锁开销。算法题普遍单线程用 StringBuilder 即可面试时能说出二者的区别是加分项。4.6 二维数组排序的稳定性Arrays.sort排序二维数组时比较的是数组引用对每一行调用 Comparator 去比较。但要注意如果你写的 Comparator 只比较了某一列且值相等这两行的相对顺序是不确定的依赖底层排序算法如果你需要保持原始顺序需要额外加一个比较维度比如索引列int[][] arrWithIndex new int[n][2]; // 填充时 arrWithIndex[i][0] 原始值; arrWithIndex[i][1] i; Arrays.sort(arrWithIndex, (a, b) - a[0] ! b[0] ? a[0] - b[0] : a[1] - b[1]);这种做法本质上是用索引保证稳定性在需要“按值排序但又要知道原始位置”的题目里比如计算每个数在排序后的名次极为常见。5. 常见问题速查表整理一个速查表按“场景 → 推荐写法 → 注意事项”的格式给你方便刷题时快速翻阅场景推荐写法注意点字符串遍历s.toCharArray() for-each需要下标时用charAt(i)字符串反转new StringBuilder(s).reverse().toString()记得转回 String 再比较字符频率统计int[26]c - a含大写字母用int[128]字符串转 intInteger.parseInt(s)可能抛 NumberFormatExceptionchar 转 intc - 0直接强转得到的是 ASCII 码int 数组排序Arrays.sort(arr)基本类型排序不稳定对象/二维数组排序Arrays.sort(arr, (a,b)-...)注意返回值不能仅用a-bList 排序list.sort(Comparator.naturalOrder())Java 8 推荐TopK 问题PriorityQueue 维护大小为 k 的堆前 K 大用最小堆前 K 小用最大堆需要稳定排序对象数组 TimSort 天然稳定基本类型数组不保证稳定字符串拼接循环StringBuilder别用在循环里拼接判断是否字母/数字Character.isLetterOrDigit(c)中文字符也算字母注意过滤原位置信息保留二维数组里存索引排完序再用索引回查这个表是我自己刷题时积累出来的“肌肉记忆集”每次处理字符串、排序相关题目都会下意识扫一遍避免在低层次细节上出错。当然表里的内容不是一开始就有的而是踩坑后不断迭代出来的。你也可以准备一个自己的速查表把每次 WA 的原因记录下来慢慢沉淀成最适合自己的版本。刷到最后你会发现字符串题和排序题考来考去就是这些基础点遍历、比较、统计、拆分、拼接、排序、堆、归并。套路都是固定的真正拉开差距的是谁在不该出错的地方不出错。比如同样是字符串转字符数组有人记得toCharArray有人硬写循环同样是逆序输出有人三行代码搞定有人还要翻转数组。语法熟不熟直接决定了你在比赛中是十分钟写完一题还是半小时还在跟空格斗争。我自己的经验是与其大量刷题前先花一个小时背 API不如直接在题中反复用每次碰到记不清的就记录下来刷满五十道字符串题后这些语法就会变成反射动作。如果你正在准备蓝桥杯或者笔试可以从字符串和排序这两类最基础的题目开始练把这份速查表里的每个方法都在代码里敲一遍很快你就会发现原来比赛时卡住你的不是思路而是那个忘了加括号的length()。