前两天刷题碰到一道字符串处理的经典题——拼数number。题面包装得很像课堂作业小 r 正在学习字符串处理小 x 给了小 r 一个字符串 s里面是一串由空格隔开的数字要求把它们全部拼接成一个整数并且拼出来的数要尽量大。我一开始觉得这就是排序题把数字从大到小排一遍就完了结果样例就把我的想法打回去了。仔细想了一圈才发现这道题把字符串处理、贪心思想和逆向思维全拧在了一块儿顺手还牵扯出排序写法里的许多坑。也因为这道题我把最近刷题清单里的六个高频专题——字符串处理、贪心思想、逆向思维、二叉排序树、链表模式匹配、图形打印——重新整理了一遍写成这篇手记。想冲击机试、面试手撕算法或者刷题刚起步的朋友都可以参考一下。1. 字符串处理很多算法题的入场券1.1 拼数这题考的不只是“排序”先把题意说清楚。给定 n 个非负整数比如3、30、34、5、9目标是把它们按某种顺序首尾相接得到一个尽可能大的整数。题目描述里为什么会涉及字符串 s因为拼接后的结果位数可能上百位早就不在一个int或long long能装下的范围内所以这道题天然就是用字符串来做的。你拿到的一开始就是字符串或者你得先把数字转成字符串再处理拼接和比较。我最初的错误做法非常典型按每个数的数值从大到小排序。用3、30一试就露馅——数值上 3 比 30 小如果让 30 排在前面得到303让 3 排在前面得到330明显330 303。也就是说3虽然数值小却必须先放。再看34、3、30这一组按数值降序是34、30、3拼出来34303可实际上34、3、30能拼成34330后者更大。这说明“尽量把数值大的放前面”这个直觉完全不靠谱。正确的比较方式也来自很朴素的尝试两个数字 x、y 谁在前直接比较 x 拼在 y 前面和 y 拼在 x 前面谁更大就行。如果x y y x那 x 应该在前否则 y 在前。把这种两两比较抽象成自定义排序规则对整个数组排一次序最后得到的拼接结果就是答案。这里有两个隐秘的坑第一x y不能用整数相加否则一旦超过类型范围就会溢出必须保留字符串拼接形式第二排序比较器必须满足严格弱序用而不是否则标准库排序的行为是未定义的。很多初学的朋友在这里写挂不是思路想错而是对字符串作为“比较载体”这件事不够重视。1.2 字符串处理最容易翻车的几个细节第一个细节是拼接方向。比较a b和b a时两边都得真的拼出来再比不要只拼一边或者想当然地认为“字典序大的在前”。字符串的字典序和数值序并不等价比如9的字典序大于10但数值上 9 小于 10。所以拼数这类场景里唯一可靠的基准就是完整拼接后的字符串。第二个细节是 C 比较器的写法。我见过不少人把函数签名写成bool cmp(string a, string b)虽然也能跑但每次排序调用都会发生两次字符串拷贝数据量一大性能立刻变差。正确姿势是传const string如下#include bits/stdc.h using namespace std; bool cmp(const string a, const string b) { return a b b a; } int main() { int n; cin n; vectorstring v(n); for (int i 0; i n; i) cin v[i]; sort(v.begin(), v.end(), cmp); if (v[0] 0) { cout 0 endl; return 0; } for (const string s : v) cout s; cout endl; return 0; }注意最后这个v[0] 0的判断。如果排序后第一项还是0说明输入的所有数字都是 0此时正确输出应该是单个0。如果不做这个特判你会拼出一长串000...0样例可能看不出来大数据直接判错。第三个细节是语言层面的字符串拼接成本。Python 里字符串是不可变对象循环里反复执行ans s会产生大量临时对象复杂度变得很难看。正确做法是先把所有片段放进列表最后统一用.join(list)。C 的vectorstring再拼接也要注意性能好在题目通常不会卡到这一步但养成好习惯不吃亏。2. 贪心思想不只是“每步选最大”2.1 怎么判断一道题能不能贪贪心思想的定义谁都会背每一步都做当前看起来最好的选择希望最终结果全局最优。但真正做题时很多人栽在“看起来能贪其实不能贪”的题上。我的经验是看到一道题先用三件事去试能不能把决策分解成一系列独立的“谁先谁后”选择有没有一个清晰的可比较优先级交换任意两个相邻决策会不会影响其它部分的结果。如果一个选完就影响后续所有选择那多半不是简单贪心能解决的可能得上动态规划。拼数为什么能贪因为它满足一个很关键的性质任意两个数字的相对顺序只影响这两个数字拼接出来的那一段结果不影响它们前后其它数字的内部顺序。换句话说当你把3放在30前面更好时这个“好”是稳定的不会因为旁边插了一个34而改变。这也解释了为什么最后能用一个全局排序搞定而不是做动态规划。这里必须强调贪心不是“凭感觉选最优”而是“先证明局部最优能被安全传递”。常见的证明手段有交换论证、反证法、数学归纳法。拿零钱兑换举例在人民币面值体系下用尽量少张数的策略确实可以贪但如果自定义一套奇怪面值贪心会失败。做题时不能因为题目长得像贪心就硬去贪先找反例找不到再用找到反例立刻换思路。2.2 交换论证与拼数排序规则交换论证是贪心题最常用也最像“数学题”的一种证明方式。对拼数来说假设最优排列中存在相邻两项 x、y且按我们的规则应该让 x 在前但实际排列是 y 在前也就是x y y x但 y 被放在了 x 前面。把 x 和 y 交换观察整个拼接结果的变化x、y 前面的部分和后面的部分都没有变只有中间这一段从y x变成x y。因为整串数的大小由“前缀 中间 后缀”决定前后缀没动中间值变大了整体自然变大。这就和“最优排列”矛盾了。所以最优排列里任何相邻两项都必须满足x y y x。接下来再补一个传递性的问题。自定义比较器要在std::sort里安全使用必须满足传递性也就是说如果a应该排在b前b应该排在c前那么a一定应该排在c前。这个性质可以从字符串拼接的角度严格推出来大体思路是把数字看成带位权的字符串形式比较ab和ba本质上是在比较某个加权字典序。竞赛中你不需要每次手推但面试时如果被追问能说出“交换论证 比较关系可传递”这两点就够了。代码上还有一个容易被忽略的点比较器写作a b b a相等时返回false这才是严格弱序。如果写成程序可能在某些编译器上陷入未定义行为排序结果甚至可能打乱我第一次写拼数时就被这种细节坑过。3. 逆向思维正面走不通就反着来3.1 逆向思维在算法题里长什么样逆向思维不是一种具体的数据结构而是一种视角切换。我总结了几种常见的“反面”形态从结果反推原因、从最终状态倒推初始状态、从问题补集入手、从结尾往前处理。拼数里的逆向体现在一个很小的点上——不要问“哪个数字大”而要问“两个数字谁拼在前面更好”。这个问题一反过来整道题的解法就从“数值排序”跳到了“拼接比较”。另一个很常见的逆向形态是“正难则反”。比如一个图不断删点问每次删完还剩多少个连通块。正着做每次都要重新计算很麻烦。如果先把所有要删的点全部删掉得到最终图然后倒着把点一个一个加回去用并查集维护连通块每个点的加入只需要处理几条邻边复杂度直线下降。这种“最终状态倒推”在网上被叫“离线逆向并查集”原理并不复杂但没见过的人第一次很难想到。还有一类是“从右往左想”。很多单链表、后缀类的问题正着扫描时要记录各种信息一旦从右往左扫描信息的传递立刻变得自然。最典型的是“找出右边第一个比自己小的元素”正着做用暴力是 O(n²)反着用单调栈每个元素进栈出栈一次整体 O(n)。我第一次学单调栈时最大的感慨就是原来有些事换一个方向会这么顺。3.2 三个值得收藏的逆向处理场景第一个场景是删除转添加。前面说的并查集逆向就是这个套路适用于“不断删除”的题目。拿到题先别急着模拟删除花两分钟想想如果反过来按时间倒序处理所有删除操作就变成了插入操作而插入恰好是并查集最擅长的。第二个场景是删数问题的“保留视角”。题目是这样的给定一个数字串删掉 k 个数字使剩下的数字组成的数最小数字相对顺序不能变。正向想“删哪 k 个”会非常乱但换一个说法——从原串里保留 len-k 个数字——思路就顺了。维护一个栈从左到右扫描如果当前数字比栈顶小说明栈顶这个“更大的数字”留着不如删掉于是弹出栈顶。整个过程始终在决定“保留谁”而不是“删掉谁”。string removeKdigits(string num, int k) { string stk; for (char c : num) { while (k 0 !stk.empty() stk.back() c) { stk.pop_back(); k--; } stk.push_back(c); } while (k--) stk.pop_back(); int pos 0; while (pos stk.size() stk[pos] 0) pos; return pos stk.size() ? 0 : stk.substr(pos); }第三个场景是拼数里的“想要最大就反向比较”。拼最大数用a b b a拼最小数就把规则反转成a b b a。很多题把最大换成最小就让人懵了其实就是比较符号一个反转的事。这正好体现逆向思维的实用价值一旦你理解了正向规则的本质反向规则根本不需要重新想。4. 二叉排序树把动态有序性握在手里4.1 BST 的核心性质与三个基础操作二叉排序树Binary Search TreeBST的定义看起来很短对于任意节点左子树所有节点的值小于当前节点右子树所有节点的值大于当前节点。由这个性质可以推出一个重要结论中序遍历 BST 得到的结果一定是有序的。这意味着 BST 天生就是为“动态维护一组有序数据”设计的插入、删除、查找都只跟树的高度有关。三个基础操作必须滚瓜烂熟。插入从根开始比当前节点小就向左大就向右走到空位置就挂上新节点。查找同样是从根开始每走一步就可以排除整棵子树。删除稍麻烦分三种情况没有孩子直接删只有一个孩子把孩子提上来有两个孩子一般用右子树的最小节点或左子树的最大节点替代被删节点再删掉那个替身。我自己经常用的插入代码长这样struct Node { int val; Node *left, *right; Node(int v) : val(v), left(nullptr), right(nullptr) {} }; Node* insert(Node* root, int val) { if (!root) return new Node(val); if (val root-val) root-left insert(root-left, val); else root-right insert(root-right, val); return root; }注意这里else部分包含了“等于”的情况我默认重复值插入右子树。不同题目对重复值的处理要求不同有的要求去重有的要求计数写之前一定要看清题。如果要求严格不重复插入前先查找一次如果允许重复就要明确所有相等值都去同一侧否则树的中序遍历会丢数据。4.2 手写 BST 的几个关键坑第一个坑是退化。BST 的复杂度是期望 O(log n)但这个结论建立在插入序列足够随机的前提下。如果数据恰好有序输入比如1、2、3、4、5依次插入树会退化成一棵单链查找和插入全部变成 O(n)。很多题的数据就是喜欢给你这种“有序”序列专门卡不写平衡树的人。所以在竞赛里能直接用std::set、std::map就用它们内部是红黑树自动保证平衡如果需要手写也要意识到数据结构本身并没有承诺最坏情况复杂度。第二个坑是删除操作的实现细节。删除有两个孩子的节点时如果你选择用右子树最小节点替代必须先找到这个“最小节点”再递归删除它。因为最小节点位于右子树的左下角它最多只有一个右孩子删除逻辑会简单很多。手写时最容易出错的地方是递归返回值没有接收导致删除后父节点指针还指向原来的节点树直接断掉。建议写完用一组包含各种形态的数据反复测试删根、删叶子、删只有一个孩子的节点、删有两个孩子的节点。第三个坑是和字符串处理的结合。BST 的节点值不一定非是整数也可以是字符串。比如给你一批单词要求去重并按字典序输出最直观的做法就是建一棵字符串 BST中序遍历就是字典序。C 里直接用string的operator就能比较比手写strcmp省心不少。这种场景能帮你把“有序性”这个抽象概念从数字扩展到文本遇到“动态维护字典序集合”的题会更有感觉。5. 链表模式匹配没有随机访问的匹配战5.1 链表匹配为什么不能直接套 KMP在数组里判断一个串是否是另一个串的子串经典算法是 KMP复杂度做到 O(n m)。它能高效的根本原因有两个数组支持随机访问失配时可以直接跳回某个位置继续比较数组长度固定所有回溯操作都在常数时间内完成。链表不一样单链表只能沿着next指针往前走不能后退也没有下标索引。你想让模式串回退到某个位置除非额外存下沿途所有节点否则做不到。所以链表上的模式匹配最常见——也最容易被接受——的方案是暴力双指针。外面用一个指针遍历主链表每到一个节点就把它当成匹配起点内层再用一个指针按模式链表往后走。如果匹配成功就返回 true失败就把外层指针往前挪一格再重新开始。最坏情况是主链每个位置都比较到模式末尾才发现失败复杂度 O(n × m)。对于链表这种结构这个复杂度很多时候是能接受的因为题目给的数据规模通常不会太大。另一个常见思路是“转数组再匹配”。先遍历一遍主链表把节点值存进一个 vector再把模式链表也存进去然后直接套字符串匹配或std::search。思路简单、不容易出错代价是额外 O(n) 空间。还有一种更进阶的思路是哈希把模式链的每个节点值滚成哈希值再在主链上滑动窗口比对能把复杂度降到近似 O(n m)但哈希冲突、取模、长度对齐这些细节足够让你写半个小时笔试时间紧张时性价比不高。5.2 三种实战思路与一个常被忽略的坑先给一个最干脆的暴力模板struct Node { int val; Node* next; }; bool matchList(Node* head, Node* pattern) { if (!pattern) return true; if (!head) return false; Node* cur head; while (cur) { Node* a cur; Node* b pattern; while (a b a-val b-val) { a a-next; b b-next; } if (!b) return true; cur cur-next; } return false; }这个函数的时间复杂度要看主链剩余长度和模式长度的乘积。有一个很容易被忽略的优化先扫一遍两条链的长度如果主链剩余节点数少于模式链长度直接不用比了或者先数出模式链总长在主链上只走到n - m的位置。这样能挡掉一大批无意义的比较。接下来是转数组方案。把主链和模式链都转成vectorint然后比较所有长度相等的子数组。这么做有个好处你可以在转数组的过程中顺手做“翻转链表的回文判断”之类的事但要注意如果匹配要求的是节点对象地址相同而不是值相同转数组就帮不上忙因为数组比较的是值。最后一个必须提的坑是环。如果主链表内部有环暴力双指针会进入死循环——外层指针沿着环永远走不完。所以在做任何链表匹配之前先判断有没有环用快慢指针如果有环先处理环的问题再谈模式匹配。我第一次在做链表题时忽略了这个调试了一个小时才发现根本不是匹配逻辑的问题而是数据里藏了一个环。这个教训告诉我链表类题目开场第一句一定是问自己这里会不会有环6. 图形打印老题新看输出类问题的一招鲜6.1 图形打印的本质是坐标映射图形打印类题目常出现在笔试和机试的入门部分比如输出菱形、回形矩阵、三角形、杨辉三角。很多人一看到这种题就开始逐行cout 一个个空格去凑结果把自己绕晕。我的经验是先把图形看成一个二维字符矩阵然后逐行逐列遍历所有坐标判断“这个坐标该放什么字符”。判断条件通常可以被总结成数学关系式而不是老老实实模拟画图的过程。举一个最经典的菱形例子。假设要输出一个由星号组成的菱形总行数为奇数比如 5 行。把图形放在一个 5×5 的坐标棋盘上中心点坐标为(r0, c0)。一个位置(r, c)属于菱形当且仅当它到中心的曼哈顿距离小于等于某个半径。所谓曼哈顿距离就是abs(r - r0) abs(c - c0)。你根本不需要关心每一行有几个空格只需要在双重循环里用这个条件判断即可。void printDiamond(int n) { int c n / 2; for (int r 0; r n; r) { for (int col 0; col n; col) { if (abs(r - c) abs(col - c) c) cout *; else cout ; } cout \n; } }我第一次用这个模板做菱形时最大的收获不是记住代码而是理解“图形 坐标集合”。你只要能把图形的轮廓转换成一个不等式剩下的代码就是双重循环的问题。三角形、平行四边形、X型图案全部是这类思想先定位再判断最后输出。6.2 菱形与回形两个生成模板比起菱形回形矩阵也叫蛇形填数复杂一点它是按一定方向在二维数组里填入 1 到 n² 的数字碰到边界或已经填过的格子就转向。经典做法是用方向数组int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1, 0}; int dir 0; int x 0, y 0; for (int num 1; num n * n; num) { a[x][y] num; int nx x dx[dir]; int ny y dy[dir]; if (nx 0 || nx n || ny 0 || ny n || a[nx][ny] ! 0) { dir (dir 1) % 4; nx x dx[dir]; ny y dy[dir]; } x nx; y ny; }这里最核心的技巧是“先探路再移动”每次填完数字先尝试按当前方向走出一步如果下一步越界或者已经被填过就转向再重新计算下一步。这样代码非常统一不需要为四个方向各写一遍判断。我见过不少同学用 if-else 把四个方向分开写代码又长又容易漏方向数组就是来一劳永逸解决这件事的。图形打印还有一个很多人不在意的输出细节行尾空格。某些 C 判断系统对输出非常严格每行末尾多一个空格可能直接判 Wrong Answer。如果题目没有明确说允许行尾空格建议要么用二维字符数组先全部填充再一次行输出要么在循环里控制最后一个字符后不打印空格。我踩过一次这个坑从那以后所有输出类题目我都会额外检查一遍行尾有没有多余字符。这个习惯在图形打印题里尤其重要。最后再分享一个小技巧图形打印题的调试不要只看最终输出把行号和列号标出来按坐标对照题目给的示意图能很快就定位是条件写反了还是边界算错了。配上abs或方向数组的模板图形打印题真的是算法题里最容易拿到满分的类型千万别在这上面丢分。写完这些专题我最大的体会是它们单独拎出来都不难真正难的是组合。拼数这道题外壳是字符串内核是贪心钥匙是逆向构造比较规则二叉排序树是动态有序性的骨架链表把模式匹配从“能随机访问”的世界拽回“只能往前走”的世界图形打印练的是把思路落成输出代码的手感。刷题别只背结论多问一句这个题反过来想行不行、换成链表还能不能做、数据顺序会不会卡掉树结构这样刷一道题的收获会比赶十几道题的进度更大。