2020年春招的机考复盘这期接着整理两道让人印象深刻的算法题一道是“扑克牌打出最小次数”一道是“钢琴高昂旋律拼接递增序列”。第一次在笔试系统里看到这两道题时我习惯性地以为前者考牌理、后者考乐理后来才发现这俩本质上都是老题型换了层生活化的皮一个考搜索和动态规划一个考贪心和二分。先说清楚了这两道题的定位正在准备校招机考、尤其容易被“花哨题干”带偏的同学这篇复盘会很有用。我会把两道题从模型还原、状态设计、代码实现到边界测试完整拆开讲再顺手整理一份机考现场的避坑清单。如果你之前看过我写的机考复盘系列应该知道我的习惯不光贴一份能跑的答案更想讲明白一件事遇到一道陌生题时怎么快速判断该用暴力搜索、DP、贪心还是二分。这期内容不依赖特定平台思路、代码和测试方法都可以直接搬到其他笔试系统里用。1. 先剥掉两道题的“生活外壳”1.1 扑克牌题最小打出次数本质上是组合拆分题目包装成“给你一副手牌按规则出牌最少几次能出完”听起来像是斗地主大师才能做的决策。实际上剥掉扑克牌的外壳它就是一道典型的“子集覆盖”问题把手上所有牌拆成若干个合法组合每个组合的代价是1次出牌目标是让组合数量最少。这里最核心的难点是“合法组合”种类多一般平台会允许单张、对子、三张、三带一、三带二、顺子甚至炸弹。不同组合之间还可能互相冲突某张牌被顺子用掉了就没法再凑对子。所以做题时如果有“把某些牌组成一个大组合总能减少次数”的直觉很容易翻车。出题人卡的就是这种局部贪心陷阱。正确的处理思路是搜索所有可能的拆分方式再用记忆化缓存已经算过的状态。只要手牌总数不大机考一般控制在20张以内搜索空间完全可控。这也是为什么这类题在笔试里出现频率那么高能区分出只会背模板的人和真正理解状态设计的人。1.2 钢琴旋律题拼接递增序列考的是排序与单调性“钢琴高昂旋律”这个名字很文艺翻译成程序员语言其实挺朴素给定若干段旋律片段每段有低音和高音只有前一段的最高音小于后一段的最低音时两段才能无缝拼接。要求选择尽量多的片段拼成一条整体持续升高的旋律。这就是经典的“最长数对链”模型解法也成熟把片段按高音从小到大排序然后贪心地选取“当前能接且结束最早”的片段。它的上位概念是“最长递增子序列”下位变体是“最少递增子序列覆盖”这几类题共用同一套贪心和二分思想只是题干从钢琴换成了日程安排、航班转机、区间选择等等。出题人喜欢这种包装一是为了增加一点现场读题的压力二是为了考察你能不能快速把自然语言抽象成数学模型。很多同学在笔试里不是不会贪心而是被“高昂旋律”四个字吓住了半天分不清到底要求输出长度还是输出方案。1.3 两道题的共性题干翻译能力比算法本身更值钱回顾这两道题共同点并不是“搜索”或“贪心”这些具体算法而是一套稳定的读题流程找到实体对象扑克牌、旋律片段找到实体上的操作出牌、拼接找到限制条件组合规则、递增关系最后找到目标函数最少出牌次数、最大拼接长度。做完这四步题干里那些生活化词汇基本就被替换成了数组、元组、排序和状态转移。我在模拟面试中反复强调这件事机考和ACM最大的区别在于题目描述长、样例少、规则多先把题看懂再谈算法。尤其是扑克牌题不同平台对顺子点数范围、三带一是否允许、A能不能连2都有不同定义审题漏一条代码就算写对了也是白搭。所以这篇文章后面给的代码和思路我都会同步标注“哪些地方需要根据平台规则调整”避免你抄完发现本地能跑、提交却全错。2. 扑克牌打出最小次数DFS 记忆化的完整解法2.1 先把规则和样例定清楚为了讨论具体我基于机考里最常见的规则来还原题目点数用1到13表示A是1K是13。允许出牌型单张、对子、三张、炸弹四张算一次、三带一、三带二、顺子至少5张连续点数。目标是输出最小出牌次数。一个典型样例可以看手牌[1,1,2,2,3,3,4,4,5,5,6,6]。直观上最优解是两次先出顺子1,2,3,4,5再出顺子2,3,4,5,6。如果你只会写贪心很可能会想“既然顺子一次出5张那就优先出顺子”这样样例能过但一换数据就容易错。错误的原因很好理解一旦为了凑顺子而拆散了原本能组成多个对子的牌局部的大收益会破坏全局的牌型结构。所以这类题宁可搜索也不建议拍脑袋贪心除非你能严格证明某种出牌顺序在所有情况下都最优——笔试现场通常没这个时间。2.2 状态设计为什么用“每种点数的剩余张数”而不是bitmask看到“最小次数”和“状态转移”很多人第一反应是状态压缩DP给每张牌编号用bitmask表示哪几张牌已经打出。这个思路在手牌少于16张时可行但有两个隐患相同点数的牌是完全等价的给它们分别编号会产生大量对称重复状态。位运算状态很难直接表达“还剩几个对子”“还剩几张3”这类组合信息转移时要现算。更自然的做法是统计每种点数的剩余张数得到一个长度13的计数数组。比如手牌[1,1,2,2,3,3,4,4,5,5,6,6]对应的状态是点数1:2 点数2:2 点数3:2 点数4:2 点数5:2 点数6:2这个计数数组直接用元组表示扔进缓存字典就能做记忆化。因为每出一轮牌至少减少一张手牌总状态数跟手牌数量和点数种类相关实际访问到的状态远小于理论上的5^13所以搜索速度完全够用。如果题目给的点数范围更大比如加上大小王只需要把数组长度从14改成15或16逻辑完全不用变。所以我说状态设计是整道题的核心状态选对了代码写起来就是枚举转移的体力活。2.3 核心转移枚举所有合法出牌方式DFS的框架很简单面对一个剩余状态尝试所有可能的出牌方式取“1 子问题结果”的最小值。合法出牌方式包括单张选一个剩余张数大于0的点数减少1张。对子/三张/炸弹分别要求某个点数剩余2/3/4张。三带一选一个剩余≥3张的点数作为“三张”再选另一个点数带1张。三带二同上但带的是2张。顺子任意连续点数区间长度至少5每个点至少1张。这里有一个非常关键的剪枝技巧单张、对子、三张这类“同点数牌型”的转移不需要枚举每个点数只处理“第一个还有牌的点数”就够了。原因是选A点数出单张和选B点数出单张只是顺序不同最终会走到相同或对称的拆分结果。只处理第一个非零点数能砍掉大量对称分支让搜索快一个数量级。三带一和三带二稍微特殊主牌的三张点数可以只处理第一个满足条件的点数但“被带的牌”必须遍历所有可能的点数。因为带哪张牌会影响后续剩余牌的结构比如带掉点数2的一张牌和带掉点数4的一张牌后续能凑出的对子完全不同。顺子的枚举也简单枚举起点和终点只要区间内每个点数都还有至少1张牌就尝试把这个区间的每个点数各减1形成一个顺子出牌。2.4 可以直接参考的代码与边界说明下面这段代码基于Python实现核心是dfs(state)返回当前剩余手牌的最小出牌次数配合lru_cache做记忆化from functools import lru_cache from typing import List, Tuple def min_plays(cards: List[int]) - int: # 下标 1..13 表示点数 1..130 号位置不用 cnt [0] * 14 for c in cards: cnt[c] 1 lru_cache(None) def dfs(state: Tuple[int, ...]) - int: if sum(state[1:]) 0: return 0 best 10 ** 9 # 单张只考虑第一个还有牌的点数避免对称重复 for i in range(1, 14): if state[i] 0: nxt list(state) nxt[i] - 1 best min(best, 1 dfs(tuple(nxt))) break # 对子 / 三张 / 炸弹 for k in (2, 3, 4): for i in range(1, 14): if state[i] k: nxt list(state) nxt[i] - k best min(best, 1 dfs(tuple(nxt))) break # 三带一 / 三带二 for i in range(1, 14): if state[i] 3: # 三带一 for j in range(1, 14): if i ! j and state[j] 1: nxt list(state) nxt[i] - 3 nxt[j] - 1 best min(best, 1 dfs(tuple(nxt))) # 三带二 for j in range(1, 14): if i ! j and state[j] 2: nxt list(state) nxt[i] - 3 nxt[j] - 2 best min(best, 1 dfs(tuple(nxt))) break # 顺子长度至少为 5 for start in range(1, 14): for end in range(start 4, 14): if all(state[p] 1 for p in range(start, end 1)): nxt list(state) for p in range(start, end 1): nxt[p] - 1 best min(best, 1 dfs(tuple(nxt))) return best return dfs(tuple(cnt))代码里有几个值得说明的边界点。第一range(start 4, 14)保证了顺子长度至少5同时终点最多到13不会越界。如果你的平台允许顺子从A到K这个写法直接成立如果平台要求顺子不能包含某几个点数只需要在all(...)条件里额外排除。第二单张、对子、三张循环里的break不是偷懒而是“只枚举第一个可出同数量牌的点数”的对称剪枝。这个技巧能砍掉大量等价搜索分支但用的时候要心里有数我们只看第一个满足条件的点数是因为把“先出点数i的牌”和“后出点数j的牌”交换顺序不影响最终最优值。三带一里面的“带牌”不能这样剪因为被带的牌会改变剩余牌的结构。第三如果平台允许“四带二”或者“连对”只需要在决策集合里继续增加分支。这个框架是开放式的核心不变。我实测下来20张以内的手牌大多数情况都能在几十毫秒内出结果。如果遇到特别刁钻的数据导致超时常见的优化方向是先把单一牌型的结果当成上界然后在DFS里做“当前步数已经不小于已找到最优解”的最优性剪枝。3. 钢琴高昂旋律拼接递增序列的贪心与二分3.1 把题目翻译成数对链模型我先把“钢琴高昂旋律”翻译成一个可编程的版本输入若干个旋律片段每个片段用[低音, 高音]表示。片段内部保证音高递增也就是低音 高音。若前一个片段的高音后一个片段的低音两个片段可以无缝拼接。每个片段最多使用一次要求输出能拼接成的最长旋律长度。这就是经典“最长数对链”的变体。比如输入[[1,2], [2,3], [3,4], [1,3]]最优可以选[1,2]、[2,3]、[3,4]拼成1→2→3→4答案是3。这里要注意的是第二个片段低音是2与第一个片段高音相等递增条件要求是严格小于所以22不成立不能拼接。这类题一看到“选择最多”“拼接条件”就基本锁定了贪心或DP两个方向。由于片段之间的顺序是我们自己选的也就是说可以重排自然优先考虑排序后贪心。3.2 排序后贪心的正确性做法非常简短把所有片段按“高音”从小到大排序然后从左到右扫描。维护当前拼接旋律的最后一个音last只要当前片段的低音大于last就选中它拼接并把last更新为当前片段的高音。为什么按高音排序直观理解手头有一个能用的片段时优先选那个结束得更早的后面可用的空间就越大。这跟安排会议时尽量选早结束的会议是一个道理。更严谨的说法是贪心交换论证假设最优解的第一个片段不是按高音排序后第一个可用片段由于被替换片段的结束时间不早于当前片段替换掉它不会影响后续片段的拼接条件所以存在一个不劣的解包含当前片段。反复使用这个替换贪心解一定最优。代码量很小from typing import List def max_chain(segments: List[List[int]]) - int: segments.sort(keylambda x: x[1]) ans 0 last float(-inf) for low, high in segments: if low last: ans 1 last high return ans这个解法时间复杂度是O(n log n)主要是排序的耗时扫描本身是线性的。如果笔试数据范围达到n 10^5这个方案也能稳定跑完。3.3 另一种常见考法最少递增子序列覆盖“拼接递增序列”还有一款近亲题型给一个乱序数组要求把它拆成尽量少的“内部严格递增”的子序列问最少拆成几段。这种题在机考里包装成“一群人排队形成几支音高上升的旋律”“把扑克牌排成若干递增叠”之类本质上都是同一个问题。解决思路类似“耐心排序”。从左到右扫描每个数维护若干个子序列的末尾值。新数来了以后优先挂在“尾数小于它且尾数尽可能大”的那个子序列后边如果所有尾数都大于等于它就只能新开一个子序列。维护这堆尾数时用二分查找就能做到O(n log n)。这里给出直接可用的代码import bisect from typing import List def min_increasing_subsequences(arr: List[int]) - int: tails [] # tails[k] 表示长度为 k1 的递增子序列的最小结尾 for x in arr: # 严格递增子序列用 bisect_left如果允许相等则改成 bisect_right pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)关于这个算法还有一句可以在面试里加分的结论最少递增子序列的覆盖数等于原数组最长非递增子序列的长度。这背后是组合数学里的Dilworth定理不一定要背证明但能说出来有助于展示你对问题的理解层次。很多同学第一次看到这段代码会觉得“这不就是最长递增子序列的那个tails数组吗”。确实如此它们本身就是同一个框架下的两种表达一个是正向求“最长”一个是逆向求“最少覆盖”。刷题时能把这层关系看穿比多背十道模板都有用。3.4 变体与二分边界陷阱拼接递增序列的题目通常在两个地方埋坑。第一个是“严格递增”还是“非严格递增”。如果题目写的是“小于”必须用bisect_left如果写的是“不大于”或“小于等于”就要换成bisect_right。这个选择差一个字母结果差很多。我见过考生在本地造数据时用了相等判断没报错结果一提交就挂在全是重复数字的样例上。第二个是片段是否允许重排。我上面讲的数对链模型默认所有片段可以任意选择顺序所以排序后贪心有效。如果题目改成“按给定顺序拼接”也就是不让你重排那问题就变成带顺序约束的DP或最长递增子序列问题解法完全不同。拿到题目时先确认这个前提能少走一大半弯路。另外有些变体把片段设计成可以“翻转使用”比如一个片段既能从左到右弹也能从右到左弹那么预处理时要把每个片段拆成两个方向分别考虑。这种一般不会在基础版本里出现但碰到了知道怎么扩展就好。4. 机考踩坑实录从读题到AC的排查清单4.1 样例之外必须验证的边界条件机考判题不会只跑样例这一点再怎么强调都不为过。基于这两道题我列一份边界检查清单空手牌或空数组输出应该是0不能报错。只有一张牌单张出完次数是1。全是同一张牌比如8个3最优是出两个炸弹还是拆成别的让搜索自己决定。顺子刚好5张长度下界要准确不能出现4张也算顺子的问题。点数顶到13顺子如果从10到13长度只有4非法但9到13是合法5连。大量重复数字的递增序列题二分边界选错最容易在这里暴露。我的习惯是拿到题目后除了跑给出的样例再手动补三组数据最小规模、最大规模、极端重复。这三组都过了提交才相对安心。4.2 搜索慢优先剪枝而不是换算法扑克牌题如果TLE很多人的第一反应是换DP或换贪心但往往剪枝就能解决。DFS慢通常不是状态太多而是对称的搜索分支太多。先做记忆化确保同一个状态不会重复算第二遍。再加入对称剪枝也就是同点数的牌不按编号区分只处理第一个可出的牌型。如果还不够再把“单张优先选第一个有牌的点数”“顺子枚举时起点限制在有效范围”这些细节加上。手牌20张以内这几招用完基本就很快了。一种更激进的优化是迭代加深先假设答案不会超过某个阈值按层数搜索找不到答案再放宽。不过机考时间紧不推荐现场写这种复杂优化不如把基础剪枝做扎实。4.3 贪心怎么快速验证对错拼接递增序列这类贪心题最怕的不是不会写代码而是“觉得对但说不出为什么”。这里分享一个实战技巧先用暴力搜索写一个慢但一定对的版本数据范围不超过10时用随机数据对拍贪心结果和暴力结果一致再正式提交。如果对拍发现有反例说明贪心缺条件或排序方向不对。比如数对链如果按“低音”排序而不是按“高音”排序贪心就会出问题你不需要背结论对拍能直接告诉你答案。扑克牌题则不建议试图找“简单贪心”因为出牌组合之间互相干扰太严重。遇到这种规则多、互动强的题目搜索记忆化才是更稳的解法。4.4 机考现场的时间分配建议我整理这类复盘时发现真正挂掉的人往往不是不会做而是在一道题上死磕太久。机考一般两到三题时间两小时左右比较合理的时间分配是读题加建模不超过10分钟。写暴力或确定算法15到20分钟。调试加边界测试20分钟。每道题总时长尽量控制在50分钟以内。如果一道题到30分钟还完全没思路果断先写一个暴力版本保底再去想优化。机考大多数按测试点给分暴力能过一部分数据比空着强太多。这也是我在模拟面试里反复强调的应试策略。5. 写在最后这类题的共同套路与我的习惯整理完这两道题我最大的体会是机考里所谓“新题”大部分是把经典模型包装成你不熟悉的场景。扑克牌对应子集覆盖和状态搜索钢琴旋律对应区间贪心和递增序列一旦撕掉包装底层全是刷题时见过无数遍的东西。我现在拿到一道生活化题干的笔试题目一般会先问自己四个问题对象是什么操作是什么限制是什么目标是什么四个问题答完再决定用搜索、DP、贪心还是二分。这个习惯帮我避免了很多“读题半小时、代码全是错”的尴尬。最后再分享一个小玩法这类题很适合用来做刻意练习。随便找一道区间贪心题把它改写成“拼钢琴旋律”“拼航班路线”“拼电影场次”只要主干逻辑不变题干怎么变都能应付。经历过几次这样的改写练习你就不会再被花哨的题目描述唬住了。希望这篇复盘能让你在下一场机考里少踩几个坑多拿几个测试点的分。