腾讯暑期实习生编程题拆解：动态规划与排序实战

又到了准备暑期实习的季节后台好几个学弟学妹来问同一件事牛客网上的“腾讯2017暑期实习生编程题”现在刷还有没有价值。我的回答基本一致这套题是当年腾讯春季实习生招聘的在线笔试题一共三道覆盖了字符串处理、动态规划、排序和组合计数难度中等偏基础但很能看出一个人的基本功。就算放到现在用来练手和摸底也一点不过时。这篇文章就以这套题作为样本逐题拆解题目背后的考察点、完整实现、边界条件和答题策略。不是为了让你背答案而是帮你搞懂大厂笔试到底在考什么以及如何用最稳的方式拿到分。无论你是准备暑期实习、秋招还是单纯想系统刷算法题这套题都值得认真过一遍。1. 这套题的整体风格与设计思路1.1 三道题到底考了什么当年这套题的构成是构造回文、字符移位、有趣的数字。从知识点的分布看几乎没有冷门算法全是学校课程里反复出现的经典内容。动态规划、双指针、排序、哈希计数每一样都是面试高频考点也是日常业务开发里真正用得上的思维工具。如果给这套题定个性它不是奥数式的偏题怪题而是典型的“基础算法应用题”。题目场景包装得很生活化比如“小Q今天在上厕所时想到了一个问题”这种描述但内核都是很纯粹的算法题。这种风格在大厂笔试里非常常见——用大白话讲故事考察你是否能把问题抽象成已知的算法模型。1.2 为什么要用这套题备考我见过太多人备战大厂笔试时直接冲难题、偏题结果上了考场连最简单的动态规划都写不利索。这套题最大的价值在于它精准命中了实习生笔试的“及格线”不要求你秒杀Hard题但要求你在有限时间内把中等及以下的题写得又快又稳。另一个值得注意的点是这三道题都有多个解法层次。比如“构造回文”可以用LCS也可以用区间DP“字符移位”可以用辅助数组也可以原地处理。你选哪种解法直接反映出你对时间复杂度和空间复杂度的敏感度。面试官看笔试代码时不只看对不对还会看你是否有意识地做复杂度取舍这个习惯从笔试阶段就应该开始养。2. 第一题拆解构造回文2.1 题目描述与样例题目的大意是给定一个字符串你可以删除其中任意字符问最少删除多少个字符后剩下的字符串能构成回文串。注意删除操作可以跳跃不要求连续。举个典型样例输入abcda输出2原字符串abcda删除b和c后得到ada或者删除b和d得到aca都是回文。最少删除2个字符。2.2 核心思路问题等价于最长回文子序列很多人第一反应是“求最长回文子串”然后用总长度减掉它这是不行的。“子串”要求连续而题目允许删除任意字符剩下的字符保持原相对顺序就好所以实际上要求的是“最长回文子序列”。这里的“子序列”指不要求连续但相对顺序不能变。求最长回文子序列的经典做法是利用动态规划思路是把原字符串反转然后求原串和反转串的最长公共子序列也就是LCS。为什么可以这么做因为回文串反转后和自身相等。原串的任意回文子序列反转后依然等于它自己所以它一定同时出现在原串和反转串中成为它们的公共子序列。反过来两个串的任意公共子序列在原串中的位置和反转串中的位置一一对应也天然构成一个回文。这一步抽象是整个题的核心。很多人卡住是因为没有建立起“删除字符求回文”和“两个串找公共子序列”之间的联系。一旦想通这一点剩下的就是套LCS模板。2.3 完整实现与复杂度分析这里给出基于二维DP的LCS实现写法尽量贴近笔试现场#include bits/stdc.h using namespace std; int main() { string s; while (cin s) { int n s.size(); string rev s; reverse(rev.begin(), rev.end()); vectorvectorint dp(n 1, vectorint(n 1, 0)); for (int i 1; i n; i) { for (int j 1; j n; j) { 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]); } } } cout n - dp[n][n] endl; } return 0; }时间复杂度和空间复杂度都是O(n^2)。当字符串长度在1000左右时这个复杂度完全可接受。如果n达到5000以上可以考虑用滚动数组把空间压到O(n)但笔试现场第一版能写出二维DP已经够了。2.4 易错点与边界情况先说第一个坑字符下标。DP数组的dp[i][j]表示“原串前i个字符”和“反转串前j个字符”的LCS长度所以比较字符时要用s[i - 1]和rev[j - 1]而不是s[i]和rev[j]。这是每次写DP最容易错的地方一行错全盘错。第二个坑输入可能包含多组测试数据。笔试题目经常是“输入包含多组测试用例每组占一行”所以要用while (cin s)处理到文件结束。很多人只处理一组数据就直接提交导致只过部分用例。第三个坑空串和单字符。长度为0或1的字符串本身已经是回文不需要删除任何字符输出0。上述DP对这两种情况都能正确处理但如果你的实现里对空串有额外操作就需要留意。3. 第二题拆解字符移位3.1 题目描述与样例题目描述很直接把一个字符串中的大写字母移动到字符串末尾并且要求大写字母和小写字母各自的相对顺序保持不变。比如输入AkleBiCeilD输出kleieilABCD注意看小写字母kleieil的相对顺序没变大写字母ABCD的相对顺序也没变。3.2 两种主流解法辅助数组和原地平移先讲最直观的解法申请一个新字符串先扫一遍原串把所有小写字母按顺序放进去再扫一遍原串把所有大写字母按顺序放进去。这个解法时间复杂度O(n)思路简单、不容易写错。但如果题目要求不能申请额外空间就需要原地处理。原地处理最稳妥的思路是“冒泡式交换”从左往右扫描遇到一个大写字母就把它不断地和右边相邻的小写字母交换直到它遇到另一个大写字母或者到达末尾。这样做能保证大小写字母的相对顺序都不变代价是最坏情况下时间复杂度O(n^2)。这里我想多说一句笔试现场不要盲目追求理论最优。如果题目没有明确限制空间用辅助数组是性价比最高的选择。如果题目明确要求原地就用冒泡交换代码短、逻辑简单不容易在紧张的考场上翻车。真正要做到O(n)时间且O(1)空间的稳定分区算法实现起来非常绕笔试里很少作为硬性要求。3.3 完整实现辅助数组版本#include bits/stdc.h using namespace std; int main() { string s; while (cin s) { string res; for (char c : s) { if (islower(c)) res c; } for (char c : s) { if (isupper(c)) res c; } cout res endl; } return 0; }原地交换版本#include bits/stdc.h using namespace std; int main() { string s; while (cin s) { int n s.size(); for (int i 0; i n; i) { if (isupper(s[i])) { int j i; while (j 1 n islower(s[j 1])) { swap(s[j], s[j 1]); j; } } } cout s endl; } return 0; }3.4 实测踩坑为什么不能直接交换我第一次做这道题的时候想的是“从后往前扫描遇到大写字母就把它放到末尾”代码写起来很短但运行结果总是不对。后来才意识到简单的首尾交换会破坏小写字母的相对顺序。比如AkleBiCeilD如果从后往前把大写字母依次换到末尾小写字母的位置会被彻底打乱。所以这题的关键不是“交换”而是“保持稳定”。这也是为什么辅助数组解法最不容易出错——你是“复制”而不是“交换”天然保持了所有字符的相对顺序。原地解法里冒泡交换通过“相邻交换”的方式同样保证了稳定性因为相邻交换不会跳过任何字符。另一个容易被忽略的点islower和isupper的入参是unsigned char或EOF直接把char传进去在某些编译器上遇到中文字符的负数ASCII值会有未定义行为。笔试场景下字符串一般是纯英文字母问题不大但如果要写出严谨代码建议先强转成unsigned char。4. 第三题拆解有趣的数字4.1 题目描述与样例这道题的题干很有画面感。题目大意是给定n个数任意两个数组成一对问“差值最小”的数对有多少对“差值最大”的数对有多少对。差值相同的一对数只算一次位置不同但值相同的数对要区分。输入样例6 45 12 45 32 5 6输出样例1 2排序后数组为5 6 12 32 45 45。最小差值是1来自(5,6)只有1对。最大差值来自(5,45)45有两个所以最多有2对。4.2 核心思路排序是前提难点在计数不重不漏差值最大相对好处理排序后最小值和最大值的差一定最大所以只需要统计最小值出现的次数和最大值出现的次数相乘即可。这里要注意如果最小值和最大值相等说明所有数都相同这种情况要单独处理。差值最小需要多想一想。排序后任意数对的最小差值一定出现在相邻的两个数之间所以只需要比较所有相邻差值找到最小值然后统计相邻差值等于这个最小值的对数。但这里藏着一个大坑如果最小差值是0也就是存在相等的数那么差为0的数对不只出现在相邻位置。比如数组1 1 1 2 2排序后相邻差为0的对数只有(1,1)两次但实际差为0的数对总共有C(3,2) C(2,2) 3 1 4对。如果只看相邻对就会漏算。正确做法是统计每个数字出现的频次对频次不小于2的数字计算组合数。这个“重复元素导致多个相同差值”的细节是这道题最大的区分度。很多人排序写对了、双指针写对了却在计数时漏掉了重复元素的情况白白丢分。4.3 完整实现#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long minCount 1, maxCount 1; for (int i 1; i n a[i] a[0]; i) minCount; for (int i n - 2; i 0 a[i] a[n - 1]; i--) maxCount; long long maxPair 0, minPair 0; if (a[0] a[n - 1]) { maxPair minPair 1LL * n * (n - 1) / 2; } else { long long minDiff LLONG_MAX; for (int i 1; i n; i) { minDiff min(minDiff, 1LL * a[i] - a[i - 1]); } if (minDiff 0) { for (int i 0; i n; ) { int j i; while (j n a[j] a[i]) j; long long cnt j - i; minPair cnt * (cnt - 1) / 2; i j; } } else { for (int i 1; i n; i) { if (a[i] - a[i - 1] minDiff) minPair; } } maxPair minCount * maxCount; } cout minPair maxPair endl; } return 0; }需要注意两点第一n最大可能到10万n * (n-1) / 2可能超过int范围所以要用long long。第二多组输入要用while (cin n)包裹并在每组内部重新初始化变量。4.4 边界条件与实战反思全相同的数组是最容易被忽略的边界。比如输入3 1 1 1所有数对差值都是0所以最小和最大的对数都是C(3,2) 3。如果用“最小值个数乘最大值个数”去算最大对数会得到9显然是错的。所以代码里要先判断a[0] a[n - 1]走独立的逻辑分支。另外最小差值大于0时计数相对简单只统计相邻差等于最小差的对数即可因为不同位置的数对不可能再有更小差值。这也是排序带来的便利把无序问题变成有序问题。这道题做完最深的体会是看似简单的题目往往在边界条件上设置了真正的考核点。你在草稿纸上推演的时候一定要拿样例以外的数据多试几组尤其是极端情况例如全部相同、只有一个数、大量重复数字。用手算推演一遍再上机验证能揪出大部分逻辑漏洞。5. 常见问题与备考建议5.1 做题时最容易踩的坑把这套题刷完我把高频错误整理成了一张速查表问题类型典型表现解决方式输入处理没有处理多组数据只跑一组就结束使用while (cin ...)循环读取下标越界DP或for循环中使用s[i]而非s[i-1]涉及dp[i][j]时统一用偏移量访问原串溢出组合数计算用int数据一大就溢出凡是涉及乘法或累加组合数直接用long long边界遗漏忽略所有元素相同、数组长度1、重复元素多的场景提交前用极端case跑一遍自测稳定性误判“字符移位”中用非相邻交换导致乱序牢记“相邻交换才能保证稳定”不确定就用辅助数组5.2 大厂笔试现场的时间分配策略按我的经验一套实习生笔试题一般给2小时左右题量在3到4道。比较合理的时间分配是前30分钟浏览全部题目先挑出最有把握的题做每道题控制在30到40分钟内包括读题、思考、编码和自测。如果一道题卡了20分钟还没有任何思路果断跳过先保证其他题拿分。这套“腾讯2017暑期实习生编程题”的难度分布比较均匀没有哪一题是“绝对的送分题”但也没有“绝对做不出来”的题。最稳妥的策略是先做“有趣的数字”这种思路直白、代码量小的题目再做“字符移位”最后留出整块时间处理“构造回文”的DP。5.3 把一套题的价值用到极致刷完这套题不建议立刻去刷下一套而是应该做一次复盘。把每一道题的“考点关键词”写下来构造回文对应动态规划和LCS字符移位对应稳定分组和原地操作有趣的数字对应排序和组合计数。然后再找同类型的题目巩固比如用“最长公共子序列”去类比其他字符串问题用“原地稳定分区”去思考数组奇偶分离问题。从2017年到现在大厂笔试的出题趋势一直在变但底层的能力要求没有变快速建模能力、边界条件意识、基础算法熟练度。这三样东西都能在这套题里得到有效训练。最后再分享一个小技巧。我刷这套题的时候把三个题的代码都实际编译运行过并且额外准备了一组自测数据比如a、aaaa、AkleBiCeilD、1 1 1 2 2。这些极端用例在笔试现场很难临时想到提前准备好可以帮你避免绝大多数低级失误。刷题不是比谁刷得多而是比谁在考场上更稳。这套题刷透你会明显感觉到拿到一道陌生题时心里有底多了。