最近集中刷了一轮算法专题把字符串处理、贪心思想、逆向思维、二叉排序树、链表模式匹配、图形打印这老几样重新过了一遍。最先想记录的是“拼数(number)”这道题题面通常是“小 r 正在学习字符串处理小 x 给了小 r 一个字符串 s”本质上是给出一堆数字字符串要求把它们按某个顺序拼接成一个最大的数。这道题看着简单实际同时串起了字符串处理、贪心思想和逆向思维三条线而且足够经典值得拆开揉碎讲清楚。这篇就把这个专题的完整笔记整理出来包括每类题的套路、代码实现和踩过的坑适合正在刷题备战面试的人也适合想系统补算法基础的同学。1. 拼数问题的完整拆解字符串处理与贪心思想1.1 题目到底在问什么拼数这道题我见过的描述有很多版本核心都是一个给定 n 个正整数把它们以某种顺序拼接成一个新的整数要求这个整数最大。比如输入[3, 30, 34, 5, 9]最大拼接结果是9534330而不是9876543这种按数值大小排出来的结果。第一反应往往是“按数值从大到小排不就完事了吗”试一下就知道不对。拿[9, 95]举例按数值降序排是95 9 959但正确结果是9 95 995反而更大。既然按数值大小不行有人就会想“按字典序排”但字典序同样会翻车。[12, 121]按字典序降序排是12 121 12121而121 12 12112前者确实更大但换成[123, 12312]字典序大的123放前面得到12312312把12312放前面得到12312123反而是后者更大。所以这个题的核心难点在于单个数字的大小完全不能决定拼接后的结果必须把两个相邻元素放在一起比较才能判断谁该在前。这就是它被归到字符串处理和贪心思想两个标签下的原因。1.2 自定义排序规则的正确姿势正确的规则很简洁对于任意两个数字字符串a和b如果a b b a那么a应该排在b前面否则b排在前面。这个规则不需要转换成整数比较直接字符串拼接后按字典序比较即可因为拼接后的两个字符串长度相同字典序比较等价于数值比较。这个规则为什么是对的呢关键在贪心选择的“交换论证”上。假设存在一个最优排列其中某相邻两项x、y不满足x y y x那说明y x x y那么交换这两个相邻项整个拼接结果不会变差。反复执行这样的交换能在一个不差于原方案的结果上逐步把相邻对调整成符合规则的状态。换句话说如果某个排列是最优的它的任意相邻两项都必须满足这条规则否则就在局部上输给了另一种排列。这里有一个容易被忽略的技术细节这个自定义比较器必须满足“传递性”否则排序结果是不可靠的。数学上需要证明ab ba且bc cb能推出ac ca工程上更稳妥的做法是直接用keycmp_to_key做排序让 Python 的排序框架自己去处理比较器的一致性。我个人的习惯是先在纸上列几个反例验证规则再实现代码省得上线后才发现排序结果和预期不符。1.3 实现代码与复杂度说明Python 版本最直观借助functools.cmp_to_key实现自定义比较代码量很短from functools import cmp_to_key def largest_number(nums): strs [str(x) for x in nums] def cmp(a, b): if a b b a: return -1 if a b b a: return 1 return 0 strs.sort(keycmp_to_key(cmp)) result .join(strs) return 0 if result[0] 0 else result如果是 Java 环境写法更贴近工程习惯public String largestNumber(int[] nums) { String[] s new String[nums.length]; for (int i 0; i nums.length; i) { s[i] String.valueOf(nums[i]); } Arrays.sort(s, (a, b) - (b a).compareTo(a b)); String res String.join(, s); return res.charAt(0) 0 ? 0 : res; }两种写法的排序规则其实是反的Java 的 lambda 里(b a).compareTo(a b)表示“如果ba更大就让a排在前面”效果和 Python 的ab ba返回 -1 完全一致。建议两种语言都写一遍能加深对这个比较方向的理解。复杂度也很明确排序是O(n log n)每次比较都要拼接两个字符串如果平均每个数字转成字符串后的长度是L整体复杂度是O(n log n * L)空间复杂度是O(n * L)。n 到 1000 时完全没压力但 n 到十万以上时就需要注意字符串拼接的开销。1.4 这题最容易踩的坑我整理了几个实际写代码时容易翻车的地方全零输入[0, 0]的拼接结果是00但题目要输出的是0。很多解法漏了这个边界一提交就挂。判断时用result[0] 0而不是等所有字符都等于零。比较器方向写反a.compareTo(b)和b.compareTo(a)是完全相反的效果差一个字母结果就错。反转方向时一定要连同拼接顺序一起检查。用数值方式比较拼接结果a b b a如果直接转成int或long大数会溢出。必须保持字符串形式长度相同的前提下字典序比较就是数值比较没有溢出风险。忽略排序的稳定性这个题对相同规则的元素先放谁都行但有的变体会要求“最小数”“字典序最小”那时比较规则里还要处理ab ba的平局情况不能直接返回 0 了事。拼数题是字符串处理和贪心思想结合得最典型的题目之一搞懂它等于同时掌握了自定义排序和贪心正确性证明的基本功。2. 逆向思维从正向盲区到反向破题2.1 拼数题的正向盲区拼数题最容易让人卡住的地方是所有人都想“正向找出一个全局最优的排法”。从高位数字、从长度、从首位字符各种维度都尝试一遍最后发现都有反例。原因在于拼接结果的大小取决于元素之间的相对位置而不是每个数字自身的属性。这个问题的本质决定了只能“逆向”思考——先退一步只问相邻两个元素应该满足什么关系再把这个局部关系交给排序。这种从“全局方案”转向“局部关系”的思维方式就是逆向思维的典型应用。面试时很多人上来就想动态规划做全局最优场面一度很混乱但一旦反向思考“假设最终答案已经排好它的相邻项长什么样”思路立刻就清晰了。2.2 更多逆向思维的实战场景逆向思维并不只出现在拼数题里。另一个经典例子是“删除 k 个数字使剩余数字最小”。正向思路是每次删掉一个当前最大的数字很快就发现不对劲2319删除 1 个数字求最小值删掉最大数9得到231但正确结果其实是删掉中间的3得到219。这个题的正确解法是反向找规律从左往右找到第一个“比后一位大”的数字并删除因为它破坏了递增趋势删掉它能让剩余数字尽量小。这就是从“最终结果的形态”反推操作顺序而不是直接盯着被删的那个数本身。还有一类场景是区间调度问题。很多贪心策略都要“按结束时间排序”而不是“按开始时间排序”原因就是反向考虑“哪个区间给后续留下的空间最大”。这类题见得多了会发现所谓的逆向思维本质是“站在结果角度思考操作条件”而不是“站在操作角度猜测结果”。2.3 训练逆向思维的小方法我个人的体会是训练逆向思维没有捷径但有三个可以落地的习惯。第一遇到一个题目卡住的时候先别急着设计算法先在纸上写一个最小规模的反例看看正向直觉错在哪里。第二拿到正确答案之后不要只看代码要反推“如果我是出题人这个答案的形状是什么”比如拼数题的答案形状就是“任意相邻两项满足比较规则”。第三大量积累“看起来像动态规划、实际是贪心”的题目这类题是逆向思维的重灾区见得多自然就形成了条件反射。逆向思维单独出题的情况不多但它是解锁字符串处理和贪心思想这两类题的关键钥匙。拼数题就是最好的训练场想通“局部比较”这一点后面很多题都会轻松很多。3. 二叉排序树的实现与工程场景3.1 二叉排序树是什么为什么需要它二叉排序树Binary Search Tree简称 BST是一棵满足左子树所有节点值小于根节点值、右子树所有节点值大于根节点值的二叉树。这个约束带来一个巨大便利中序遍历的结果天然是一个递增序列换句话说一棵 BST 本身就是“动态维护有序序列”的数据结构。那为什么需要它因为有序数组虽然支持二分查找但插入和删除需要 O(n) 时间搬移元素有序链表插入删除快但查找又退化成 O(n)。BST 在理想情况下把查找、插入、删除都做到平均 O(log n)解决了“既要有序、又要动态”的矛盾。这个特性让它在很多领域都有用武之地比如内存中的索引结构、数据库索引的思想基础、排行榜系统等。3.2 核心操作的实现细节插入操作是 BST 最基础也最容易写错的部分递归写法非常简洁public TreeNode insert(TreeNode root, int val) { if (root null) { return new TreeNode(val); } if (val root.val) { root.left insert(root.left, val); } else { root.right insert(root.right, val); } return root; }这个写法有一个很容易忽略的精髓递归函数的返回值要赋值给root.left或root.right这样才能把新建的节点真正挂到树上。如果写成insert(root.left, val)而不接收返回值新节点就丢了。查找操作相对简单只需要沿路径比较public TreeNode search(TreeNode root, int val) { if (root null || root.val val) { return root; } return val root.val ? search(root.left, val) : search(root.right, val); }删除操作是 BST 重灾区需要分三种情况处理。第一种被删节点是叶子直接置空即可。第二种被删节点只有一个孩子用孩子顶上。第三种被删节点有两个孩子这时候最稳妥的做法是找到右子树中的最小节点或者左子树中的最大节点用它的值覆盖当前节点再递归删除那个最小节点。这个替代场景我建议画一棵三层以上的树去模拟只看代码很难理解为什么需要“递归删除替代节点”。3.3 什么时候用它什么时候不要用它BST 适合用在需要快速查找、插入、删除且数据基本有序更新的场景最典型的就是动态排行榜数据流式插入时要随时查询第 k 名或某个成绩区间的数量。配合在每个节点记录子树大小这些操作都能做到 O(log n)。但裸 BST 有一个致命问题当数据接近有序输入时树会严重倾斜退化成链表所有操作都变成 O(n)。比如把1, 2, 3, 4, 5顺序插入整棵树就变成一条只往右延伸的链。工程上从来不会直接裸用 BST而是用红黑树、AVL树、跳表这类自带平衡机制的结构。面试时如果面试官让你手写“二叉排序树”多半是在考察递归插入和删除的三种情况如果面试官问“数据库索引为什么不用 BST”回答“因为数据顺序插入会退化成链表磁盘 IO 次数太深”就是得分点。我还踩过一个实际的坑实现 BST 之后用它做排名查询默认认为所有节点值不重复结果数据里大量重复分数导致右子树一直挂同一个值。后来在节点设计里加了count字段把重复值聚合到同一个节点上复杂度才回到正常水平。这个经验分享给做动态排名的同学非常实用。4. 链表模式匹配从暴力到优化4.1 链表模式匹配的问题本质链表模式匹配的常见题面是给定主链表和模式链表判断模式链是否为主链中的一个连续子链。比如主链是1 - 2 - 3 - 4模式链是2 - 3结果是匹配成功模式链是2 - 4则匹配失败。这道题放在数组里很简单直接滑动窗口或连续子串比较即可。但链表有两个天然劣势一是不能随机访问想比较任意位置必须从头走二是单链表无法回头一旦指针走过某个节点想回到上一个节点很麻烦。所以这个题的本质是“在无法随机访问的线性结构上做子串匹配”。4.2 暴力匹配实现与复杂度分析暴力解法非常直观外层循环遍历主链的每一个节点作为起始候选内层循环同时遍历主链和模式链逐个比较节点值一致就继续不一致就换下一个主链节点重新开始。代码如下public boolean isSubList(ListNode head, ListNode pattern) { for (ListNode p head; p ! null; p p.next) { ListNode a p; ListNode b pattern; while (b ! null a ! null a.val b.val) { a a.next; b b.next; } if (b null) { return true; } } return false; }复杂度是 O(n * m)n 是主链长度m 是模式链长度。这个暴力写法最大的坑是内层循环结束后要判断b是否走完了整个模式链而不是判断a走到了哪里。如果模式链比主链剩余部分还长a会先变成 null但b还没走完此时不能算匹配成功最终会自然换到下一个主链起点继续尝试逻辑是对的但第一次写很容易在 while 条件里漏掉a ! null导致空指针异常。4.3 序列化加 KMP 的优化思路暴力法在 m 和 n 都很大时会超时。优化思路也不复杂既然链表的“子串判断”和数组的“子串判断”本质相同我们可以先把链表转成数组再用经典的 KMP 算法在线性时间内完成匹配。具体做法是遍历两遍链表把节点值存入两个数组然后对模式数组构建next数组再对主数组执行 KMP 匹配。空间代价是 O(n m)时间代价是 O(n m)整体效果显著优于暴力法。不过有一个反直觉的细节节点值不是简单的单字符可能是任意整数转换时需要定义清楚。如果直接用整数数组KMP 比较时直接比较整数即可没有任何歧义。如果想转成字符串再用 String 的contains就要特别小心[12, 3]和[1, 23]这种序列转成123之后完全无法区分必须加分隔符比如12#3#和1#23#并且确保分隔符不会出现在节点值里。这个坑我实测过项目里真的有同事因为偷懒没加分隔符匹配结果错得莫名其妙。至于为什么不能直接在链表上做 KMP原因也很简单KMP 在匹配失败时需要根据next数组回退模式链的指针而单链表只能前进不能后退虽然可以通过记录每一个模式节点的“上一个位置”来模拟但那样做的代码复杂度和空间开销完全抵消了优化收益。所以工程上最干净的做法就是“链表序列化 KMP 数组匹配”这也是我向团队推荐的首选方案。5. 图形打印题的规律化处理5.1 图形打印的本质是坐标计算图形打印题是很多高校笔试和面试里必出的小题比如打印三角形、菱形、螺旋矩阵、回形矩阵。这类题代码量不大但特别容易写错究其原因是很多人没有意识到图形打印的核心是“坐标计算”而不是打印语句本身。拿最简单的等腰三角形举例输入 n5要求输出五行的星号三角形。不要一行一行去数空格和星号而是去推导行号i与空格数、星号数的关系第i行从 1 开始空格数是n - i星号数是2 * i - 1。代码就是n 5 for i in range(1, n 1): print( * (n - i) * * (2 * i - 1))这类题的关键是建立“行号到行列坐标”的映射。无论图形多复杂打印的本质都是两层循环外层控制行内层控制列每一列输出什么字符由位置公式决定。一旦从“背代码”切换到“找公式”题目就简单了。5.2 菱形和螺旋矩阵的方向控制菱形是三角形题的升级版常见做法是把上半部分和下半部分分开处理。上半部分从第一行到中间行每行空格递减、星号递增下半部分反过来空格递增、星号递减。写代码时要注意边界的对称性我的习惯是先用 n5 在纸上画出 5 行标出每一行的行列关系再转换成代码基本一次就过。螺旋矩阵则是另一类它考察的是“方向控制”。思路是维护四个边界top、bottom、left、right按照右、下、左、上的顺序填充每走完一条边就收紧对应的边界。核心代码骨架如下int top 0, bottom m - 1, left 0, right n - 1; while (top bottom left right) { for (int j left; j right; j) matrix[top][j] num; top; for (int i top; i bottom; i) matrix[i][bottom?] ... }这个题最容易错的地方是循环条件写得过于复杂。我建议不要把所有方向写在一个巨大的 while 里处理一堆边界判断而是把四个方向拆成四个独立的 for 循环每走完一个方向更新一次边界循环条件只有top bottom left right这一个。这样逻辑更直观也不容易把边界搞混。5.3 图形打印的通用套路与练习建议图形打印题可以总结出三个通用步骤。第一步把图形画在纸上标注行号和列号。第二步寻找行列坐标与字符的映射关系实在找不到就分区域三角形的上下半区、空心的内外圈都是独立处理。第三步把映射关系翻译成循环代码优先使用数学表达式而不是散落的分支判断。练习建议是集中做三个经典题等腰三角形、空心菱形、螺旋矩阵。这三个题覆盖了“单区间公式”“对称分区”和“方向遍历”三种最常见的模式吃透它们大部分图形打印题都能举一反三。实际写代码时还有一个小技巧打印字符之间到底有没有空格一定要先看题目样例很多题目因为空格数量不对被扣分还以为逻辑写错了。图形打印题是纯送分题但送分题一旦耗费太久就会影响整个考试节奏。把这套“坐标映射”的思维练熟考试时就能做到十分钟内一次跑通把时间留给真正的难题。我个人刷完这一轮专题后最大的体会是这些题都是表面不同、内核相通。字符串处理题的底层是排序和比较贪心思想题的底层是交换论证逆向思维的底层是站在结果看条件二叉排序树的底层是有序动态维护链表模式匹配的底层是非随机访问结构上的匹配优化图形打印的底层是坐标映射。无论哪一种最值钱的都不是把模板背下来而是把“为什么这样做”想透。后面如果再遇到新题我会先花几分钟在纸上推演局部关系和小规模样例再动手写代码这个习惯帮我少走了很多弯路。