计算机机试里的查找、贪心、链表这三块内容放在一起讲其实挺有意思。单独拎出来看查找是基础中的基础贪心是思维题的代表链表则是数据结构里最容易在机试现场翻车的一类。很多同学刷题的时候习惯按知识点分块练练查找就只做二分练贪心就只背区间调度模板练链表就只写反转和合并结果上了考场遇到综合题就懵了。我当年准备机试的时候也踩过这个坑后来才慢慢琢磨明白这三类题目背后其实有一条共同的线它们都在考察你对局部信息如何支撑全局决策这件事的理解程度。查找是你怎么高效定位目标贪心是你怎么用局部最优拼出全局最优链表是你怎么在不连续的内存里维持逻辑上的顺序关系。把这三块放在一个框架里过一遍比分开刷效率高得多。这篇内容适合正在准备计算机机试的在校同学也适合已经工作但需要回头补算法基础的开发者。不管你之前刷过多少题我都会从最底层的思路讲起把每类题目的核心判断逻辑、代码实现的关键细节、以及考场上最容易出问题的地方掰开揉碎说清楚。文中涉及的代码以C和Python为主因为机试环境里这两种语言最常见其他语言的同学看思路就行实现层面是相通的。1. 三类问题的整体设计思路与选型考量1.1 为什么把查找、贪心、链表放在一起练乍一看这三者分属不同类别查找偏基础算法贪心偏策略设计链表偏数据结构实现。但如果你仔细分析机试真题的分布会发现它们经常以组合形式出现。比如在有序链表中查找第一个大于某值的节点这就同时涉及链表遍历和查找策略再比如用贪心策略安排任务任务之间用链表串联这就是贪心和链表的结合。分开练的时候你每个模块都能做对合在一起就卡壳根本原因在于你练的是知识点而不是判断力。我自己的经验是机试现场最耗时的不是写代码而是判断这道题该用什么方法。查找类题目你要判断的是数据是否有序、是否需要多次查询、查询的规模有多大贪心类题目你要判断的是局部最优能不能推导出全局最优、需不需要排序预处理链表类题目你要判断的是需不需要虚拟头节点、指针操作会不会断链。这三种判断力的训练方式其实是一样的先看数据规模再看数据特征最后看操作类型。把这三类放在一起练你会在反复切换中形成一种条件反射式的判断习惯这比单独刷一百道二分题有用得多。还有一层原因跟机试的评分机制有关。机试通常是按测试点给分一道题可能十个测试点你暴力做法能过六个优化做法能过十个。查找和贪心的优化空间往往很明确二分能把O(n)降到O(log n)贪心排序能把O(n²)降到O(n log n)这些优化在测试点规模拉开的时候直接决定你能不能拿满分。链表题则不太一样它的难点不在时间复杂度而在指针操作的边界处理一个空指针解引用就能让你从满分掉到零分。所以这三类题放在一起刚好覆盖了机试里效率优化和实现稳健两个维度练的时候心里有数考的时候才不慌。1.2 三类问题的核心判断框架我在准备机试的过程中慢慢总结出一个判断框架拿到一道题之后按顺序问自己三个问题。第一个问题数据有没有序如果有序或者可以低成本变得有序查找类方法优先考虑。第二个问题能不能用局部最优推出全局最优如果能贪心优先考虑但必须能说清楚为什么局部最优不会导致全局次优。第三个问题数据需不需要频繁插入删除如果需要链表优先考虑否则数组更省事。这个框架看起来简单但真正用起来需要你对每类方法的适用边界有清晰的认识。拿查找来说二分查找的前提是有序但有序这个条件在机试里经常是隐含的比如题目给你一个单调函数让你求零点表面上看是数值计算本质上是二分查找。再拿贪心来说区间调度问题里按结束时间排序是标准做法但如果你按开始时间排序就会出错这个错误的根源在于你没有验证局部最优选择是否影响后续选择空间。链表也是同理单链表和双向链表的操作差异很大双向链表删除节点时不需要前驱指针单链表就需要这个差异在写代码的时候如果不注意调试时间会成倍增加。下面这张表是我自己整理的三类问题的判断要点放在手边随时对照判断维度查找类贪心类链表类数据特征有序或可排序可分解为子决策频繁插入删除核心风险边界条件写错贪心策略不成立指针断链或越界优化方向二分替代线性排序预处理虚拟头节点典型信号词有序查找第k个最多最少最优节点插入删除这张表不是让你死记而是让你在读完题目之后快速定位方向。我见过不少同学读完题直接开始写写到一半发现方法选错了推倒重来时间全浪费在返工上。花三十秒对照这张表判断一下比闷头写十分钟划算得多。1.3 机试环境下的实现选型机试环境和平时刷题环境有个很大的区别你不能依赖IDE的自动补全和调试功能很多时候就是在一个朴素的编辑器里手写代码编译运行看结果。这就要求你在实现层面做一些务实的选型。查找类题目如果数据规模在10^5以内二分查找手写循环版本比递归版本更稳因为递归有栈溢出的风险而且机试环境里递归深度限制不一定明确。贪心类题目排序几乎必用C里用sort配自定义比较函数Python里用sorted配key参数这两种写法要练到不用想就能写出来。链表类题目虚拟头节点dummy head是我强烈建议的习惯它能消掉大量头节点特殊处理的代码分支。还有一个选型细节跟输入输出有关。机试题目经常是多组测试数据C里用while(cin n)这种写法Python里用try-except包住input()这些模板要提前准备好。链表题尤其要注意输入可能是用数组形式给出节点值让你在内存里构建链表也可能是直接给操作序列让你模拟两种输入模式的处理方式完全不同。我建议你在准备阶段就把这几套输入模板写成固定片段考试时直接默写省下来的时间留给思考算法。2. 查找类问题的核心细节与实操要点2.1 二分查找的三种写法与适用场景二分查找看起来简单但真正写对的人不多。我统计过自己早期刷题的错误记录二分查找的出错率排在前三主要问题集中在边界更新和循环终止条件上。常见的二分写法有三种闭区间写法、左闭右开写法、以及带答案记录的写法。闭区间写法用left和right都指向有效元素循环条件是left right更新时mid加减一左闭右开写法用right指向无效位置循环条件是left right更新时right直接等于mid。这两种写法本身没有优劣但混着用必出错你必须选定一种然后练到肌肉记忆。带答案记录的写法适合查找第一个满足条件的位置这类问题。比如在一个单调不减的数组里找第一个大于等于目标值的下标标准二分在找到相等元素时就返回了但题目要的是第一个所以你需要一个额外的变量记录当前找到的候选答案然后继续往左收缩。这种写法在机试里出现频率很高因为很多题目表面上是查找实际上是找边界。我个人的习惯是统一用左闭右开写法配答案记录代码结构固定不容易出错。// 左闭右开 答案记录找第一个 target 的位置 int lowerBound(vectorint arr, int target) { int left 0, right arr.size(); int ans arr.size(); // 默认无解 while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { ans mid; right mid; } else { left mid 1; } } return ans; }这段代码里mid的计算用left (right - left) / 2而不是(left right) / 2是为了防止整数溢出。虽然机试数据规模通常不会大到溢出但养成这个习惯没有坏处。另外注意ans的初始值设为arr.size()表示没找到的语义调用方拿到这个值就知道目标不存在不需要额外判断。2.2 哈希查找在机试中的取舍哈希表在查找类题目里是另一把利器平均O(1)的查找复杂度让它在判断元素是否存在统计出现次数这类问题上几乎是无脑选择。但机试环境里用哈希有两个坑要注意。第一个坑是哈希冲突导致的性能退化虽然理论上平均O(1)但如果你用的哈希函数不好或者数据被刻意构造过最坏情况会退化到O(n)。机试题目一般不会刻意卡哈希但如果你发现用哈希超时了可以考虑换成排序加二分或者用更均匀的哈希函数。第二个坑跟语言特性有关。C里unordered_map的默认哈希对整数是恒等映射如果键值范围很大且分布集中冲突率会很高这时候可以自定义哈希函数或者改用map红黑树O(log n)但稳定。Python里dict的实现已经足够好一般不需要操心。我在机试里用哈希的原则是数据规模在10^6以内、键值类型简单整数或短字符串、只需要存在性判断或计数就直接用哈希如果键值复杂或者需要有序遍历就换排序加二分或者平衡树。注意机试里如果题目明确要求不能使用额外空间或者空间限制很紧哈希表可能不是好选择因为哈希表本身要占O(n)空间。这时候要考虑原地排序加二分或者用位图bitset压缩空间。2.3 查找类题目的边界处理清单查找类题目丢分十有八九丢在边界上。我整理了一份边界处理清单每次写完查找代码对照检查一遍。第一空数组或单元素数组的情况有没有处理第二目标值比所有元素都小或者都大的情况有没有处理第三数组里有重复元素时题目要的是第一个、最后一个还是任意一个第四查找范围是闭区间还是开区间循环条件跟范围定义是否一致第五返回值是下标还是元素值找不到时返回什么这五个问题看起来琐碎但每一个都对应着真实的丢分场景。我印象很深的一次是题目要求找最后一个小于目标值的元素我写成了第一个小于等于的测试点里有一组数据刚好卡在这个差异上直接扣了二十分。从那以后我养成了一个习惯写完查找代码先用三组手造数据跑一遍——目标在数组最左边、最右边、以及不存在。这三组能过基本边界就稳了。3. 贪心类问题的核心细节与实操要点3.1 贪心策略成立性的验证方法贪心题最大的风险不是写不出来而是你用的贪心策略根本不成立。机试里经常出现这样的情况你按某种规则排序然后依次选择样例过了提交之后挂了一半测试点。根本原因是你没有验证贪心策略的正确性。验证贪心策略有两个实用方法一个是交换论证一个是反例检验。交换论证的思路是假设存在一个最优解它跟你贪心策略做出的第一个选择不同你通过一系列交换操作把它变成跟你贪心策略一致的选择且不破坏最优性。如果能完成这个交换说明贪心策略成立。拿区间调度来说贪心策略是每次选结束时间最早的区间交换论证就是假设最优解选的第一个区间不是结束最早的你把最优解里的第一个区间换成结束最早的那个因为结束更早后面能选的区间只会更多不会更少所以替换后仍然是最优解。这个论证过程你在草稿纸上走一遍心里就有底了。反例检验更直接构造小规模数据穷举所有可能的选择组合跟你贪心策略的结果对比。如果找到反例说明策略不成立如果小规模数据全对虽然不能证明策略一定对但至少排除了明显的错误。机试现场没时间写穷举程序但你可以手算几个小例子比如三个区间、四个物品这种规模手算一遍比空想靠谱。3.2 排序预处理的关键细节贪心题里排序几乎是标配但排序的键选择和比较函数的写法有很多细节。以区间调度为例按结束时间升序排列是标准做法比较函数写成a.end b.end。如果结束时间相同怎么办这时候按开始时间降序或者升序都可以因为结束时间相同的区间最多选一个顺序不影响结果。但有些题目里结束时间相同的时候有额外约束比如要求选开始时间最晚的这时候比较函数就要写成先比结束时间再比开始时间。C里sort的比较函数必须满足严格弱序也就是不能出现a b和b a同时为真的情况。如果你写成a.end b.end当两个区间结束时间相同时比较函数返回true这违反了严格弱序可能导致sort行为未定义在某些编译器上会直接崩溃。这个坑我踩过当时调试了半小时才发现是比较函数的问题。正确写法是a.end b.end相等的情况交给排序算法自己处理。// 区间调度按结束时间升序结束相同按开始时间降序 sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { if (a.end ! b.end) return a.end b.end; return a.start b.start; });Python里sorted的key参数没有严格弱序的问题但要注意key函数返回的值必须可比较。如果排序键是元组Python会按元组元素依次比较写起来比C简洁但也要注意元组里元素的顺序跟你想要的优先级一致。3.3 贪心与动态规划的边界判断很多同学分不清什么时候用贪心什么时候用动态规划。我的判断标准是如果局部最优选择不会影响后续选择的可行性用贪心如果局部最优选择会影响后续选择的范围用动态规划。拿背包问题举例分数背包物品可以分割用贪心按单位价值排序依次拿0-1背包物品不可分割用动态规划因为拿了一个物品之后剩下的容量变了后续能拿的物品范围也变了。机试里还有一类题介于两者之间比如用最少的硬币凑出指定金额硬币面额是任意给定的时候贪心不成立比如面额1、3、4凑6元贪心拿411三枚最优是33两枚这时候必须用动态规划。但如果硬币面额是标准货币体系1、5、10、20、50、100贪心成立。这个差异的根源在于标准货币体系的面额设计保证了贪心策略的正确性而任意面额不保证。所以看到硬币题先看面额有没有特殊性质没有的话老老实实上动态规划。提示机试里如果拿不准贪心是否成立可以先写一个暴力搜索或者动态规划的版本保底然后再尝试贪心优化。这样即使贪心策略错了你至少有一个能过部分测试点的版本不至于零分。4. 链表类问题的核心细节与实操要点4.1 虚拟头节点的使用规范虚拟头节点是我在链表题里最推荐的习惯没有之一。它的作用是把头节点的特殊处理统一掉让所有节点的插入删除操作走同一套逻辑。比如删除链表中所有值为某目标的节点如果没有虚拟头节点你需要单独判断头节点是否要被删除代码里会出现两个分支有了虚拟头节点头节点变成普通节点一套循环搞定。// 删除链表中所有值为 target 的节点 ListNode* removeElements(ListNode* head, int target) { ListNode dummy(0); dummy.next head; ListNode* cur dummy; while (cur-next) { if (cur-next-val target) { ListNode* toDelete cur-next; cur-next cur-next-next; delete toDelete; // 机试里可省略但养成习惯 } else { cur cur-next; } } return dummy.next; }这段代码里cur从dummy开始而不是从head开始这是关键。如果从head开始头节点本身就没法被删除。另外注意循环条件是cur-next而不是cur因为我们要操作的是cur的下一个节点cur本身始终是有效的。这个模式在链表题里反复出现练熟之后大部分链表题都能套用。4.2 指针操作的断链风险与规避链表题最容易出的bug是断链也就是你修改了某个指针之后原本能访问到的节点访问不到了。典型场景是反转链表如果你先把cur-next指向pre然后才去取cur-next的原始值就会发现原始值已经丢了。正确的顺序是先保存next再修改指针最后移动。// 反转链表先存后改再移动 ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur) { ListNode* nxt cur-next; // 先存 cur-next pre; // 再改 pre cur; // 再移动 cur nxt; } return pre; }这个先存后改再移动的顺序是链表操作的基本功我建议你把它当成口诀记下来。所有涉及指针重定向的操作都先问自己我改了这个指针之后原来指向的节点还能访问到吗如果访问不到说明你需要提前保存。双向链表稍微复杂一点删除节点时要同时修改前驱的后继和后继的前驱但顺序原则是一样的先把所有需要的信息保存好再统一修改。4.3 链表题的调试技巧机试现场没有断点调试链表题出了bug怎么排查我的方法是打印中间状态。在每次指针操作之后打印当前节点的值和指针地址跑一组小数据看输出是否符合预期。指针地址在C里可以用%p打印Python里可以用id()函数。虽然打印会增加代码量但机试里时间比代码简洁更重要能快速定位问题就是好方法。另一个技巧是用数组模拟链表来验证逻辑。如果你不确定自己的指针操作对不对可以先用数组把同样的逻辑写一遍数组的下标就是节点的地址next指针就是数组里存的下一个下标。数组版本不会出现空指针崩溃调试起来直观得多。等数组版本逻辑验证通过了再翻译成指针版本出错概率会大幅降低。这个方法在考场上可能来不及用但平时练习的时候多用几次你对指针操作的理解会深很多。5. 三类问题的交叉场景与综合应用5.1 有序链表上的查找优化有序链表上的查找是个有意思的场景它同时涉及链表和查找。单链表不支持随机访问所以二分查找用不了只能线性扫描时间复杂度O(n)。但如果题目允许你先把它转成数组那就可以用二分O(n)转换加O(log n)查找。机试里遇到有序链表查找的题目先看操作次数如果只查一次线性扫描就够了如果查多次转数组加二分更划算。还有一种情况是链表本身支持跳表结构但机试里基本不会考跳表的实现最多考概念。所以务实一点有序链表查找就按单次线性、多次转数组来处理不要想太复杂。5.2 贪心策略在链表操作中的应用贪心加链表的组合在机试里出现得不多但一旦出现就是区分度很高的题。典型例子是合并K个有序链表标准做法是用优先队列小顶堆每次取最小的头节点这本质上是一种贪心策略每次选当前最小的最终得到全局有序。这个贪心的正确性是显然的因为所有链表都有序当前最小的节点一定是全局最小的候选。实现的时候要注意优先队列里存的是节点指针比较函数按节点值比较。C里用priority_queue配自定义比较Python里用heapq配元组值链表索引节点。Python的heapq不支持直接比较节点对象所以要包一层元组把值放在第一位。这个细节不注意的话运行时会报类型不可比较的错误。5.3 综合题的拆解策略机试里最后一道题经常是综合题把查找、贪心、链表中的两个或三个揉在一起。拿到这种题我的拆解策略是分三步走。第一步识别出题目里的独立子问题比如先对数据排序是一个子问题在结果中查找是另一个子问题。第二步给每个子问题选择合适的方法排序用sort查找用二分或哈希链表操作用虚拟头节点。第三步把子问题的解拼起来注意子问题之间的数据传递和边界衔接。拆解的时候不要一上来就想最优解先把能跑通暴力版本写出来再逐步优化。机试评分是按测试点给分暴力版本能过小数据点优化版本过大数点两者结合就是你能拿到的最高分。我见过太多同学死磕最优解结果时间到了连暴力版本都没写完一分没拿。先保底再优化这是机试的铁律。6. 常见问题与排查技巧实录6.1 查找类问题速查表问题现象可能原因排查方法解决方法二分死循环循环条件与边界更新不匹配打印left和right的变化统一用左闭右开或闭区间写法查找结果差一边界定义模糊手造三组边界数据明确第一个/最后一个的语义哈希超时哈希冲突严重换map测试是否变快自定义哈希或改排序二分找不到返回错误返回值语义不清检查无解时的返回值统一返回size()或-1并注释6.2 贪心类问题速查表问题现象可能原因排查方法解决方法样例过提交挂贪心策略不成立构造小规模反例换动态规划或修正策略排序后结果错比较函数不满足严格弱序检查是否有改成并处理相等情况结果不是最优排序键选错对比不同排序键的结果按题目目标选排序键多组数据答案累加全局变量未重置检查每组数据前是否初始化把变量定义在循环内部6.3 链表类问题速查表问题现象可能原因排查方法解决方法运行时空指针访问了nullptr的next打印当前节点地址循环条件用cur-next结果链表断链指针修改顺序错打印每步的next指向先存后改再移动头节点丢失没使用虚拟头节点检查返回值加dummy并返回dummy.next内存泄漏删除节点未释放机试可忽略养成delete习惯6.4 考场时间分配的实战心得机试通常三到四道题时间两到三小时。我的时间分配策略是第一遍花十分钟把所有题读一遍按难度排序然后从最简单的开始做每道题先写暴力版本保底再优化如果一道题卡了二十分钟没有进展果断跳过做下一道最后回头再啃。这个策略的核心是保证你会做的题都拿到分而不是在一道难题上耗死。链表题我通常放在中间做因为它代码量大但思路直接适合在精力还充沛的时候写。查找和贪心题看情况简单的先做复杂的往后放。最后留十五分钟检查重点检查多组数据的初始化、边界条件、以及输出格式。输出格式这个细节很多人忽略题目要求输出Case #1:你输出成Case 1:直接零分冤不冤。提示机试提交前一定要用题目给的样例跑一遍再自己造两组边界数据跑一遍。样例过不代表全对但样例不过一定有问题先解决样例不过的情况再提交。我在实际准备机试的过程中最大的体会是这三类题目练到最后拼的不是谁刷的题多而是谁的错误清单更短。每道错题都记下来错在哪是思路错还是实现错是边界没考虑还是策略不成立积累到一定数量之后你会发现错误类型就那么几种考前过一遍自己的错误清单比刷新题有用得多。链表题尤其如此指针操作的错误模式高度重复你把常见的几种断链场景都踩过一遍考场上再遇到就能条件反射地避开。