每年三、四月牛客网的笔试讨论区都会冒出一堆“腾讯暑期实习生编程题”的求助帖。我前几天整理旧电脑里的算法收藏夹翻出了2017年腾讯暑期实习生招聘的笔试题整理文档——构造回文、字符移位、有趣的数字三道题用一晚上重新写了一遍感受还挺深。七八年过去这套题放在今天依然是很好的面试热身材料不考偏题怪题但每一道都能往下挖出两三层考点代码量不大坑倒是不少。无论你是准备大厂实习校招的在校生还是想系统补一补算法功底的转行开发者这套题都值得静下心来做一遍。这篇文章我会把三道题目的完整推导过程、边界条件、我当年踩过的坑以及后来复盘时才想明白的考点全部拆开讲清楚。1. 重温经典这套题到底在考什么1.1 题目背景与当年的笔试环境腾讯的暑期实习生招聘一般从每年三月启动笔试环节通常安排在三月中下旬线上OJ答题用的是牛客网那套在线评测系统。2017年的笔试编程题一共三道时间大概是120分钟左右语言不限C、Java、Python都可以。我印象比较深的是当时笔试页面比现在朴素很多没有代码补全、没有本地调试写完直接提交跑不过就是跑不过不像现在有些平台还能看到部分用例结果。当时的技术氛围和现在不太一样身边很多同学对动态规划还停留在“背模板”的阶段会写最长上升子序列但换个包装就认不出来。腾讯这三道题出得挺有水平表面看都是基础题实际上每一道都埋了“如果只背模板你会挂在这里”的暗坑。比如构造回文如果只背了“最长回文子串”的马拉车算法拿到这道题会直接懵掉比如字符移位如果直接两两交换输出结果会违反“保持相对顺序”的要求比如有趣的数字如果不做去重和相等值统计边界用例一测就挂。1.2 三道题的知识点地图把这三道题的知识点拆开看其实覆盖了大厂笔试最常考的几块基本面题目核心考点隐藏考点数据规模敏感点构造回文最长回文子序列LPS、区间DP回文与逆序串LCS的等价转换长度1000时O(n^2)可过别写O(n^3)字符移位字符串处理、稳定分区稳定性的定义、原地算法的陷阱只含大小写字母但长度可能很大有趣的数字排序、相邻差值、组合计数重复数字的去重、边界情况处理n可能到10^5暴力两两比较必超时这套题组合起来就是在考察一件事你能不能把问题抽象成已知的算法模型而不是对着题目硬模拟。这也是为什么我推荐大家都做一遍——做完再对照下面的推导过程你会发现自己对“算法设计”这四个字的理解会深一层。2. “构造回文”最长回文子序列的两种解法与一个本质2.1 题目描述与第一层思路题目是这样给定一个字符串s你可以从中删除一些字符使得剩下的字符串成为一个回文串。问最少需要删除多少个字符。字符串长度不超过1000只包含小写字母。例如输入abcda删掉b和c得到aba或者删掉c和d得到aba最少删除2个字符输出2。注意一个关键表述这里说的是“剩下的字符串成为回文串”而不是“找到最长的回文子串”。字符串删除若干字符后剩下的子序列必须是回文的所以本质是求最长回文子序列Longest Palindromic SubsequenceLPS的长度。最少删除数 原串长度 - 最长回文子序列长度。为什么不是最长回文子串回文子串要求连续回文子序列只需要保持相对顺序。abcda里没有长度大于1的连续回文子串但aba作为子序列存在所以这道题一定是在讨论子序列问题。很多同学第一眼会按子串去套马拉车这就是第一个失分点。2.2 解法一逆序串的LCS为什么能这么转最长回文子序列有一个非常经典的转换原串s和它的逆序串rev s[::-1]的最长公共子序列LCS长度就是s的最长回文子序列长度。这个结论初看有点绕我们拆开理解。假设某个字符序列t既是s的子序列也是rev的子序列。t是s的子序列说明t可以从s头部往尾部按顺序挑出来t是rev的子序列说明t可以从s尾部往头部按顺序挑出来。也就是说同一个序列在原串中能正向找到也能反向找到。把正向找到的t和反向找到的t拼在一起看中间位置重叠时就构成一个回文结构。举个例子s abcdarev adcba。s和rev的LCS是aba长度3原串长度5答案2。为什么正好是3因为aba在s中正向出现的位置是第1、3、5个字符在rev中正向出现对应s中第5、3、1个字符一正一反刚好构成回文。代码实现就是一个标准LCS动态规划。定义dp[i][j]表示s前i个字符和rev前j个字符的LCS长度转移方程如果s[i-1] rev[j-1]dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])def min_deletions_lcs(s: str) - int: n len(s) rev s[::-1] dp [[0] * (n 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, n 1): if s[i - 1] rev[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 else: dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) return n - dp[n][n]n1000时dp表是1001×1001个整数大约10^6级别内存完全没问题。如果环境内存紧张还可以滚动数组压到两个一维数组后面我讲优化方案时一起说。2.3 解法二直接区间DP边界可别写错除了LCS转换还有另一种更贴合“删除字符”语义的写法——区间DP。定义dp[i][j]表示子串s[i..j]变成回文串最少需要删除的字符数。转移逻辑分两种情况如果s[i] s[j]说明两端的字符可以同时保留问题转化为s[i1..j-1]变成回文最少删除数即dp[i][j] dp[i1][j-1]如果s[i] ! s[j]两端的字符不可能同时出现在最终回文串的首尾所以至少删一个dp[i][j] min(dp[i1][j], dp[i][j-1]) 1初始化时单个字符本身就是回文dp[i][i] 0空区间dp[i][i-1]也看作0。实现时要从短区间向长区间枚举长度不能直接按i从小到大否则计算长区间时依赖的短区间结果还没算出来。def min_deletions_interval_dp(s: str) - int: n len(s) dp [[0] * n for _ in range(n)] for length in range(2, n 1): for i in range(n - length 1): j i length - 1 if s[i] s[j]: # 区间长度为2时dp[i1][j-1]是空区间值为0这里直接取0 dp[i][j] dp[i 1][j - 1] if length 2 else 0 else: dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1 return dp[0][n - 1]这段代码最容易被忽略的坑就是区间长度等于2且两端字符相等的情况例如aa。此时dp[i1][j-1]访问的是dp[i1][i]下标是合法的但dp[i1][j-1]在Python里如果n大于1i1不会越界j-1等于i访问的是自己初始化的0结果没问题。但如果你用C写二维vector当n等于2时i0j1dp[1][0]这个位置是存在的因为dp初始化为n×n值为0也安全。但如果你把dp初始化为n×n且从length1开始做了别的处理这里就要特别小心。最稳妥的写法是显式判断length 2或者把dp[i1][j-1]在length2时直接赋0。2.4 两种写法对比与考场建议两种解法的时间复杂度都是O(n^2)空间也都是O(n^2)。LCS解法胜在思路简单、不容易写乱适合考场上快速实现区间DP解法更贴近题目的“删除”语义而且有一个额外的好处——如果想让你输出删除哪些字符区间DP可以配合回溯直接构造方案LCS方案需要额外保存选择路径稍麻烦一点。如果现场时间紧张我建议用LCS转换写一个标准LCS模板然后return n - dp[n][n]三分钟内能写完。如果面试官追问“能不能把空间优化到O(n)”LCS滚动数组的代码也很好写def min_deletions_lcs_optimized(s: str) - int: n len(s) rev s[::-1] prev [0] * (n 1) for i in range(1, n 1): cur [0] * (n 1) for j in range(1, n 1): if s[i - 1] rev[j - 1]: cur[j] prev[j - 1] 1 else: cur[j] max(prev[j], cur[j - 1]) prev cur return n - prev[n]这里只保留上一行的prev和当前行的cur每次内层循环跑完把cur赋给prev。注意cur[j] max(prev[j], cur[j - 1])中第二项依赖当前行左边的计算值第一项依赖上一行的同列值这两项在滚动数组中都存在所以可以正常推导不用担心覆盖顺序问题。3. “字符移位”三行代码背后的稳定性陷阱3.1 最稳妥的写法与时空复杂度分析第二题是字符移位输入一个只包含大小写英文字母的字符串把所有大写字母移到字符串尾部同时保持小写字母之间和大写字母之间的相对顺序不变。输出调整后的字符串。例如输入AaBbCc输出abcABC。先别急着写交换逻辑仔细读要求中的“保持相对顺序不变”。这意味着我们需要一个稳定的分区算法把字符按“是否小写”分为两类小写在前大写在后同类之间的先后顺序不能乱。笔试现场最稳妥的写法莫过于两遍扫描用两个数组分别收集小写和大写最后一并拼接def move_uppercase(s: str) - str: lower_part [] upper_part [] for ch in s: if ch.islower(): lower_part.append(ch) else: upper_part.append(ch) return .join(lower_part upper_part)时间复杂度O(n)空间复杂度O(n)。这个写法思路极简单不可能写错也一定满足“保持相对顺序”的要求。有些人可能觉得空间O(n)不优雅但笔试环境下n一般不会到无法分配内存的量级能AC就是王道没必要为了省一点空间去冒险。如果要求原地修改字符串例如传入的本来就是字符数组也可以先遍历一遍统计小写字符个数然后用一个双指针重新排列但要注意双指针交换法无法同时保证两类字符的相对顺序必须在写之前想清楚题目到底测不测稳定性。3.2 交换法为什么不成立一个反例很多网上的题解会给出一个看起来很帅的双指针写法维护一个索引idx表示下一个小写字母应该放的位置从头遍历字符串遇到小写字母就和第idx个位置交换然后idx加一。def move_uppercase_inplace_wrong(s: str) - str: arr list(s) idx 0 for i in range(len(arr)): if arr[i].islower(): arr[idx], arr[i] arr[i], arr[idx] idx 1 return .join(arr)这个写法看起来没问题但它会打乱大写字母之间的相对顺序。举一个反例输入aBCdEf小写a、d、f大写B、C、E。初始a B C d E fidx0i0a是小写交换arr[0]和arr[0]结果不变idx1i1B是大写跳过i2C是大写跳过i3d是小写交换arr[1]和arr[3]得到 a d C B E fidx2i4E是大写跳过i5f是小写交换arr[2]和arr[5]得到 a d f B E Cidx3最终结果是adfBEC大写顺序变成了B、E、C而原串大写顺序是B、C、E违反了题目要求。所以我强烈建议这道题不要用交换法至少笔试环境不要用。你永远不知道测试用例里会不会有一个恰好能暴露不稳定性的数据。3.3 面试官追问时可以把答案拉到哪个深度笔试过了之后面试环节经常会有面试官拿着笔试题追问“你对这道题还有没有更好的解法”这里“更好”通常指两个方向一是空间能不能优化二是这个问题的本质是什么。到这个阶段可以这样说这个问题在算法上叫稳定分区stable partition也就是把数组按某个谓词分成前后两部分同时保持同类元素相对顺序。C标准库里的stable_partition函数就是干这个的底层实现是如果有足够额外内存分配O(n)缓冲区做一趟归并式分区时间O(n)如果没有额外内存采用原地循环移位的方式时间退化到O(n log n)。笔试现场用C的同学其实可以直接写#include algorithm #include cctype #include string std::string move_uppercase(std::string s) { std::stable_partition(s.begin(), s.end(), [](char c) { return std::islower(static_castunsigned char(c)); }); return s; }一行搞定而且完全满足稳定性要求。但如果你面试时主动说出“这是一个稳定分区问题能做得更好的是分治块交换”这类话会明显加分因为这展示了你不仅仅会写循环还知道问题在数据结构与算法体系中的位置。更深一层可以提“稳定0-1排序”和荷兰国旗问题的区别荷兰国旗问题解决的是三色分区且不要求稳定性稳定分区要求同类相对顺序不变所以不能简单用交换实现。这个对比能展示你对稳定性的理解不是背出来的。4. “有趣的数字”排序之后一切豁然开朗4.1 先排序把问题变成相邻问题第三题是“有趣的数字”输入n个整数两两组成二元组差最小的有多少对差最大的有多少对n可能达到10^5数字范围没说假设可能很大。要求输出两个整数第一个是差最小的对数第二个是差最大的对数。题目名起得很随意坑却不少。首先最暴力的做法是枚举所有C(n,2)个二元组计算差值再统计复杂度O(n^2)。当n是10^5时C(n,2)大约是5×10^9稳超时。所以要排序。排序之后有两个关键观察差值最大的二元组一定是最大值和最小值组成的对。因为排序后首尾差值就是全局最大差值要想达到这个差值只能选一个最小值和一个最大值所以最大差值对数 最小值的个数 × 最大值的个数。差值最小的二元组只可能出现在排序后相邻的元素之间也可能出现在相等元素之间后面细说。因为如果a b c那么c - a b - a差值最小的二元组不可能跨过中间元素。这两个结论是所有后续计算的基础。先对数组排序一次遍历就能拿到最小差值和最大差值。4.2 最大差值对数首尾元素出现次数的乘积按上面的分析最大差值对数就是nums.count(min_val) * nums.count(max_val)。但要加一个边界如果整个数组所有元素都相等即min_val max_val那么所有二元组的差值都是0最大差值对数是C(n,2)而不是count(min) * count(max)——后者等于n × n显然不对因为同一个元素不能和自己组对。举个例子[2, 2, 2]任意两两组合差值都为0对数应该是C(3,2)3不是3×39。所以代码里要先判断min_val max_val是的话直接返回C(n,2), C(n,2)。如果最大值和最小值不相等还要注意最大值和最小值的个数可能不止一个。例如[1, 1, 4, 4, 5]最小值1出现2次最大值5出现1次最大差4对数2×12即(1,5)有两对分别由两个不同的1和唯一的5组成。4.3 最小差值对数两个分支都要处理干净最小差值分两种情况讨论第一种数组中有重复元素。此时最小差值必为0对数等于所有重复元素各自组合数之和。比如[1, 1, 1, 2, 3]1出现3次C(3,2)3所以差值为0的对数是3。注意此时不能用“相邻相等”来统计因为[1, 1, 1]中相邻相等的对只能数出2而实际是3漏掉了首尾那一对。正确的做法是遍历数组统计每个相同数字出现的次数c累加c×(c-1)//2。第二种数组中没有重复元素。最小差值一定大于0等于排序后所有相邻元素差的最小值。对数等于“相邻差等于这个最小差值的相邻对”的个数。例如[1, 3, 5, 8]相邻差分别是2、2、3最小差2相邻对有两对所以差最小的对数2。这里要特别提一个很多人的误区在没有重复元素时最小差对数只数排序后的相邻对就够了因为前面说过任何跨元素的差值都更大。但一旦有重复元素最小差就变成0相邻对就不够用了必须归组累组合数。这两个分支一定要分开写混在一起很容易漏。完整实现def solve(nums): n len(nums) nums.sort() # 所有数相同 if nums[0] nums[-1]: return n * (n - 1) // 2, n * (n - 1) // 2 # 最大差值对数 min_val nums[0] max_val nums[-1] min_count nums.count(min_val) max_count nums.count(max_val) max_diff_pairs min_count * max_count # 最小差值 min_diff min(nums[i 1] - nums[i] for i in range(n - 1)) if min_diff 0: # 有重复元素统计每个重复组的组合数 min_diff_pairs 0 i 0 while i n: j i while j n and nums[j] nums[i]: j 1 c j - i min_diff_pairs c * (c - 1) // 2 i j else: # 无重复元素统计相邻差等于最小差的个数 min_diff_pairs sum( 1 for i in range(n - 1) if nums[i 1] - nums[i] min_diff ) return min_diff_pairs, max_diff_pairsnums.count(min_val)和nums.count(max_val)虽然是两次线性扫描但合起来还是O(n)不影响整体复杂度。整个算法O(n log n)主要由排序贡献。4.4 边界测试和性能复盘这种题最容易挂的就是边界情况我列出几组自测数据建议写完后逐一跑一遍输入最小差对数最大差对数说明[2, 2, 2]33所有数相同最大差和最小差都是0[1, 1, 1, 2, 3]31重复三个1最大差值对数3×13这里其实最大差是21出现3次3出现1次对数是3上面表格要修正[1, 3, 5, 8]21无重复最小差2有相邻两对[1, 2, 3, 4]11最小差1只有一对(1,2)最大差3只有一对(1,4)[1, 1, 4, 4]24重复元素1和4各C(2,2)1最小差0共2对最大差3最小1出现2次最大4出现2次2×24上面第二行我一开始写错了这里特意标注出来想提醒大家这种题手算都要细心写代码时更要逐分支验证。我当年提交时就是漏了“所有数相同”这个分支导致[5, 5, 5]这种用例挂掉。笔试平台的测试数据往往就爱放这种极端输入你平时自测不跑考场上就只能靠运气。性能方面n10^5时Python的排序约0.05秒遍历O(n)完全没问题。如果n进一步到10^6还是O(n log n)依然能过。真正要注意的是不要写出先O(n^2)求所有差值再排序的写法那是必死无疑。5. 从笔试题到大厂offer这些细节才是分水岭5.1 笔试前的输入输出练习很多人刷LeetCode刷得很顺一到牛客笔试就卡壳问题出在输入输出。LeetCode是函数体填空输入输出框架已经写好了牛客笔试要自己处理标准输入流尤其是多组测试用例时。这三道题里字符移位和有趣的数字都涉及输入读取构造回文只读一行字符串。Python推荐用sys.stdin而不是input()因为大数据量下input()的内置缓冲会有额外开销笔试时出现过DataError也不奇怪。一个实用的模板import sys def solve(): data sys.stdin.read().split() # 按题目要求解析data pass if __name__ __main__: solve()如果题目说“输入包含多组测试用例每组用一行”更稳妥的是import sys for line in sys.stdin: line line.strip() if not line: continue # 处理一组输入把这段代码背下来笔试时能少踩一半的坑。还要注意题目里数字的范围如果数值可能很大Python的int没问题C就要用long long很多人因为用int导致溢出白丢一道题。5.2 做题顺序和时间分配上的个人经验三题笔试合理的时间分配应该是先花5分钟通读全部题目给每道题标一个难度等级然后从最确定能拿到分的题开始做。我自己的习惯是先做综合性最低、不需要太多推导的题。这套题里字符移位最简单优先做构造回文需要写DP复杂度稳定放第二有趣的数字虽然思路也不难但边界分支多测试用例要仔细设计放最后做或者预留充足时间调试。千万不要在一道题上死磕超过40分钟。笔试的计分规则通常按通过率给分哪怕只过一部分测试用例也有对应的分。把能拿的分先拿到手再回头优化是最稳的策略。还有一个小技巧提交前花30秒把代码快速读一遍重点检查数组下标有没有越界、循环变量有没有写错、边界条件是不是返回了空值。很多低级错误都是提交前扫一眼就能发现的。5.3 一道题的多解价值与复盘方法笔试结束不等于学习结束。这套题真正的价值在于复盘时能不能把每道题都拿出两种以上解法并说清楚为什么它们是等价的。比如构造回文LCS解法和区间DP解法其实是同一个问题从两个角度切入一个把回文看成“正向序列和反向序列的公共部分”另一个直接刻画“删除到最小的回文串最少需要删几个字符”。字符移位题也一样从两遍遍历到stable_partition再到稳定分区问题一次比一次抽象也一次比一次靠近问题的本质。我刷题复盘的一种习惯是每道题写三行注释第一行写题目在考什么数据结构或算法第二行写最容易出错的地方第三行写能不能迁移到其他题目场景。比如“有趣的数字”里“排序后只看相邻元素”这个思想可以迁移到很多“两两最小差值”类问题“构造回文”里的LCS转换凡是涉及“删除/插入使字符串成回文”的题都能用。这比做十道新题更有用。最后分享一个关于这套题的小感悟2017年那会儿大厂笔试还很看重基本功三道题没有一道需要很高深的算法但每一道都考察了“能不能把问题看透”的能力。这种能力不是靠背题背出来的而是在反复推导、反复踩坑、反复复盘中长出来的。把这三道题彻底吃透你收获的远远不止几道题的答案。