很多年前我还在准备秋招的时候就把腾讯研发岗的历年编程题翻来覆去刷了好几遍。说实话腾讯2016研发工程师编程题这一套在当年的校招题库里属于「看着不难但非常考验基本功」的典型代表。它不考偏题怪题也不追求复杂的算法炫技翻来覆去就在字符串、数组、动态规划、递归这些基础模块上做文章但每一道都能把一批人卡在边界条件和复杂度优化上。正因为如此这套题直到现在依然是很多同学备战大厂笔试的首选练习材料。无论你是正在准备校招的应届生还是工作几年后想查漏补缺的开发者这套题都值得认真过一遍。它会让你重新审视自己写代码时的边界感知能力、复杂度分析意识以及最基本的编码习惯。这篇文章我按当年考场上流传出来的题型风格整理了最有代表性的三道题字符串循环移位、最长回文子串、数组中的逆序对。每一道我都会从题目分析、暴力思路、优化解法、代码实现、面试考点五个维度拆开讲最后再聊聊校招笔试的实战经验和容易踩的坑。1. 2016年腾讯研发工程师编程题整体拆解1.1 当年的出题风格与考察重点腾讯研发工程师的笔试题目在2016年前后的风格非常鲜明不追求题目表面上的难度而是喜欢在看似简单的题目里埋边界条件和复杂度陷阱。整套题通常包含3到4道编程题考试时间60到90分钟使用牛客网或者其他在线OJ平台支持C/C、Java等主流语言。从题目类型上看字符串处理和数组操作是绝对的高频考点。比如字符串移位、回文判断、子串匹配、数组排序变体、逆序对统计等这些都是日常开发中真正会用到的基本功。腾讯的出题人很清楚一个应届生在实际工程中能写出多优雅的架构代码是次要的首先要保证基础算法扎实、代码边界处理不出错、能够在有限时间内给出一个复杂度合理的解法。这套题还有一个特点很多题目都存在“暴力解法能跑通小数据但一到大数就用例超时”的情况。也就是说出题人故意留了暴力得分的空间但真正的区分度在于你能不能想到优化方案。这也是大厂笔试比较常见的筛选逻辑。1.2 题型盘点与通用解题策略把这套题里出现的题型归纳一下基本集中在以下几个方向字符串类循环移位、回文子串、模式匹配、单词反转。这类题考察的是对字符串底层操作的理解以及是否熟悉各种回文算法、双指针技巧。数组类排序、逆序对、TopK、去重合并。这类题背后经常隐藏着归并排序、快排partition、堆排序等经典算法的影子。递归与动态规划背包问题、最长公共子序列、编辑距离。这类题考察的是状态定义能力和递推关系的推导能力。针对这套题我建议的做题策略是第一步快速判断题目属于哪一类心里先有一个大概的复杂度目标第二步如果一时想不出最优解法先把暴力方案写出来保证能拿部分分数第三步再尝试从暴力解中找重复计算看看能不能用缓存或分治的手段降复杂度。考场上最忌讳的就是在第二题上死磕到底导致后面的题根本没时间看。2. 第一道题字符串循环移位2.1 题目描述与思路分析题目大概是这样给定一个字符串和一个非负整数k要求将字符串循环右移k位。举例来说字符串abcdefg右移2位结果是fgabcde。这道题看起来非常简单很多人的第一反应就是按照移动的语义去模拟每次把最后一个字符取出来放到最前面重复k次。但稍微一算就知道这种解法的时间复杂度是O(n*k)一旦字符串长度达到10万级别k稍微大一点超时没商量。而且腾讯的用例往往不会给你这么温柔的数据范围。所以正确做法是先把k对字符串长度取模因为循环右移n位等于没有移动。然后利用“三次翻转”的思路把问题转化为数组区间翻转问题。2.2 三次翻转的完整实现三次翻转的思路是这个题的核心先翻转整个字符串再翻转前k个字符最后翻转剩下的字符。以abcdefg右移2位为例完整过程如下原始字符串abcdefg整体翻转gfedcba翻转前2位fg edcba翻转后5位fg abcde最终得到fgabcde结果正确。这个做法的时间复杂度是O(n)空间复杂度是O(1)因为整体翻转操作可以用首尾交换完成。C的参考实现如下void reverse(string s, int l, int r) { while (l r) { swap(s[l], s[r--]); } } string rightShift(string s, int k) { int n s.size(); if (n 2 || k % n 0) return s; k % n; reverse(s, 0, n - 1); reverse(s, 0, k - 1); reverse(s, k, n - 1); return s; }这里有几个细节值得注意。第一一定要先取模再判断是否为0否则当n为0或k为0时可能出现除零错误或者无意义的翻转。第二如果题目要求左移其实只需要把“反转前k位”改成“反转前n-k位”即可本质上是同一个思路。第三输入输出格式要特别注意有些OJ题目要求循环读取多个测试用例这时候不能只处理一次就返回。2.3 这道题背后的面试考察点为什么腾讯会出这么一道看起来毫无技术含量的题我理解面试官想考察三件事第一你写代码时有没有边界意识k比字符串长度大的时候会不会处理第二你知不知道反转字符串是解决一类旋转问题的通用技巧——比如后面还有一道常见变体“判断一个字符串能否通过另一个字符串循环移位得到”做法就是把其中一个字符串拼接成两倍长度然后查找另一个字符串是否在里面第三你愿不愿意在简单题上多花一分钟想更好的解法还是一上来就写暴力。这题如果出现在面试环节答完三次翻转之后面试官大概率会接着问一句“如果字符串长度很大比如上百万你的方案还能跑吗”这时候需要解释清楚O(n)复杂度的原因以及为什么三次翻转比逐位移动更优。3. 第二道题最长回文子串3.1 题目描述与样例分析这道题是腾讯笔试的常客也是面试中最高频的字符串题目之一。题目描述很直接给定一个字符串s找到s中最长的回文子串。比如s babad那么bab和aba都是合法的答案如果s cbbd答案就是bb。我见过很多人一上来就用暴力枚举所有子串然后逐个判断是否为回文。子串数量是O(n^2)个每个子串判断回文最坏要O(n)总复杂度O(n^3)对于字符串长度超过1000的用例基本就跪了。腾讯的笔试数据范围通常都在10^4到10^5级别所以这个题必须在O(n^2)甚至更低的复杂度内解决。3.2 中心扩展法实现简单适合笔试中心扩展法是最推荐在笔试中使用的解法。它的核心思想是回文串一定是对称的所以我们枚举每一个可能的回文中心然后从中心向两端扩展直到无法形成回文为止。一个字符串的回文中心不仅包括每个字符本身还包括每两个相邻字符之间的空隙因此总共有2n-1个中心。具体实现时用两个循环分别处理奇数和偶数长度的回文。奇数回文的中心是某个字符s[i]偶数回文的中心是s[i]和s[i1]之间的空隙。扩展过程中维护当前找到的最长回文左右边界即可。参考代码如下string longestPalindrome(string s) { int n s.size(); if (n 2) return s; int maxLen 1, start 0; for (int i 0; i n; i) { // 奇数长度回文 int l i, r i; while (l 0 r n s[l] s[r]) { if (r - l 1 maxLen) { maxLen r - l 1; start l; } l--; r; } // 偶数长度回文 l i; r i 1; while (l 0 r n s[l] s[r]) { if (r - l 1 maxLen) { maxLen r - l 1; start l; } l--; r; } } return s.substr(start, maxLen); }这段代码的时间复杂度是O(n^2)因为每个中心最多向外扩展n次。空间复杂度是O(1)。笔试场景下这个方案完全够用而且不容易写错。面试中如果时间充裕还可以主动提一下Manacher算法把复杂度优化到O(n)但不需要在笔试中冒险。3.3 动态规划解法与边界细节如果你想在面试中展现更系统的思维这里也可以选择动态规划。定义dp[i][j]表示字符串从下标i到下标j的子串是否为回文。递推关系是dp[i][j]为true当且仅当s[i] s[j]且dp[i1][j-1]为true。注意边界情况单个字符一定是回文两个相邻且相同的字符构成偶数回文。由于dp[i][j]依赖dp[i1][j-1]即长度更短的子串所以遍历顺序必须是子串长度从小到大。这一点很多人会写错如果按照通常的二维数组从左到右、从上到下去遍历会遗漏依赖关系。代码如下string longestPalindrome(string s) { int n s.size(); if (n 2) return s; vectorvectorbool dp(n, vectorbool(n, false)); int maxLen 1, start 0; for (int i 0; i n; i) { dp[i][i] true; if (i 1 n s[i] s[i 1]) { dp[i][i 1] true; if (maxLen 2) { maxLen 2; start i; } } } for (int len 3; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (s[i] s[j] dp[i 1][j - 1]) { dp[i][j] true; if (len maxLen) { maxLen len; start i; } } } } return s.substr(start, maxLen); }动态规划版本的代码量明显更大笔试时如果追求速度中心扩展法是更优的选择。但如果面试官追问“如何证明你的算法是对的”动态规划的状态转移逻辑反而更容易讲清楚。3.4 复杂度对比与面试中的取舍解法时间复杂度空间复杂度建议场景暴力枚举O(n^3)O(1)仅作为思路铺垫中心扩展O(n^2)O(1)笔试首选动态规划O(n^2)O(n^2)面试展示思维ManacherO(n)O(n)加分项不建议笔试现场写我个人的建议是笔试时直接用中心扩展法因为不容易出错空间占用小运行速度也能通过腾讯的用例。如果面试时被问到可以主动说“我知道Manacher算法整体思路是通过对称性避免重复计算但现场实现风险较高所以我用中心扩展法保证正确性”。这既展示了知识广度又体现了工程上的取舍判断。4. 第三道题数组中的逆序对4.1 题目描述与暴力思路这道题在当年的腾讯笔试里属于压轴题之一。题目描述在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对总数。例如数组[7,5,6,4]逆序对一共有5对(7,5)、(7,6)、(7,4)、(5,4)、(6,4)。最直接的思路是双重循环枚举所有数字对遇到前大后小就计数加一。时间复杂度O(n^2)空间复杂度O(1)。当数组长度到10^5级别时这个解法基本超时。别问我为什么知道问就是我当年真拿暴力去交了然后卡在最后一个用例上超时。4.2 归并排序求逆序对的原理逆序对问题的最优解法是借助归并排序的分治思想。归并排序在合并两个有序子数组时会逐一比较左右两边的元素。关键点在于如果左半边当前元素nums[i]大于右半边当前元素nums[j]那么左半边从i到mid的所有元素一定都大于nums[j]这些元素和nums[j]都能组成一个逆序对。这听起来有点抽象我举个例子。左半边是[5,7]右半边是[4,6]。合并时5和4比较5大于4此时左半边中5和7都比4大所以4这个元素贡献了2个逆序对。接着5和6比较5小于6不做计数7和6比较7大于6此时左半边只有7了贡献1个逆序对。总数就是3个。这和暴力枚举出来的结果一致。这个思路的高明之处在于利用了两个子数组已经有序的前提把“当前元素能和后面多少个元素组成逆序对”这个问题从O(n)次比较降到了O(1)次计算。4.3 完整代码实现与边界处理归并排序求逆序对的C参考实现如下long long mergeCount(vectorint nums, vectorint tmp, int left, int mid, int right) { int i left, j mid 1, k left; long long cnt 0; while (i mid j right) { if (nums[i] nums[j]) { tmp[k] nums[i]; } else { cnt mid - i 1; tmp[k] nums[j]; } } while (i mid) tmp[k] nums[i]; while (j right) tmp[k] nums[j]; for (int p left; p right; p) { nums[p] tmp[p]; } return cnt; } long long mergeSortCount(vectorint nums, vectorint tmp, int left, int right) { if (left right) return 0; int mid left (right - left) / 2; long long cnt mergeSortCount(nums, tmp, left, mid); cnt mergeSortCount(nums, tmp, mid 1, right); cnt mergeCount(nums, tmp, left, mid, right); return cnt; } long long reversePairs(vectorint nums) { vectorint tmp(nums.size()); return mergeSortCount(nums, tmp, 0, nums.size() - 1); }这个实现有几个容易写错的点。第一计数变量必须用long long因为一个长度为10^5的数组逆序对数量最多接近5 * 10^9int会溢出。第二在nums[i] nums[j]时增量是mid - i 1而不是简单加1很多人就是在这里少算了一大半逆序对。第三临时数组可以提前分配好避免在每一层递归里反复创建vector否则会有大量内存分配开销导致性能下降。4.4 为什么腾讯爱考这类题表面上看逆序对只是一个数组统计问题但它的背后实际上是考察你对归并排序这个经典算法到底理解到什么程度。很多同学能背出归并排序的代码但从来没想过归并过程中可以顺带统计逆序对。这就是“会默写代码”和“真正理解算法”之间的区别。大厂笔试出这种题就是在筛选那些对基础算法有深度理解的人。你不仅要会写归并排序还要能在它的框架上做扩展把计数逻辑嵌进合并过程中。这种能力放到实际工作中就对应着在现有代码框架上做逻辑扩展的能力。5. 校招笔试实战经验做题顺序与避坑指南5.1 做题顺序与时间分配腾讯笔试一般有3到4道编程题时间通常在60到90分钟。我的建议是拿到题目后先全部扫一遍给每道题打一个难度标签然后按照“易到难”的顺序做。第一道题往往是最基础的送分题必须快速拿下确保保底分中间一道题可能是中等偏上的难度比如回文子串这种集中精力做出来最后一道题如果一时没有思路先写一个能过部分用例的暴力解再慢慢优化。时间分配上我推荐用40%的时间做前两道题用60%的时间做后两道题。因为前面的题目通常思路明确代码量不大后面的题目需要更多思考时间而且往往需要调试边界情况。千万不要在前面的题上过度自信写完不测试就提交却在一道根本没有思路的难题上死磕半小时。5.2 常见失误与排查技巧我把自己和身边同学在刷这套题时踩过的坑整理了一下列成了一份速查表错误情况原因分析解决方案字符串右移时k大于字符串长度没有先取模先执行 k % n再判断是否为0最长回文子串输出结果错误奇偶回文中心没分开处理分别以字符i和空隙(i,i1)作为中心逆序对数量溢出使用了int类型使用long long存储计数逆序对漏算合并时简单加1而不是加mid-i1记住左子数组从i到mid都大于当前右元素归并排序递归过深导致栈溢出数据量规模极大改为非递归归并或增加栈空间动态规划遍历顺序错误dp[i][j]依赖dp[i1][j-1]一定要按子串长度从短到长遍历做题之前还有一个容易被忽略的动作确认OJ的输入输出格式。腾讯的笔试平台有时候需要自己处理多组输入有时候是单组输入。如果题目描述写了“输入包含多组测试用例”那就必须用while循环读取否则只能过一个用例分数会非常难看。另外我建议在本地写代码时就把边界用例列出来至少准备几组空字符串、单个字符、全相同字符、k等于数组长度、数组长度为1、逆序数组、升序数组。跑一遍这些用例能避免80%的低级失误。5.3 笔试后的复盘方法笔试结束不代表这件事就翻篇了。我自己的习惯是无论AC了几道题都会把没做出来的题目重新在IDE里实现一遍然后记录自己卡住的点到底是思路问题还是编码问题。如果是思路问题就把题解里的核心思想用自己的话写一遍如果是编码问题就重点练习那类边界处理。腾讯2016研发工程师编程题这套题我前前后后刷了三遍。第一遍是研二上学期很多题靠暴力解勉强跑通第二遍是秋招前开始有意识地追求最优解和边界处理第三遍是工作之后再回头看这些题更加理解了出题人想考察的能力模型。每一次刷都有不同的收获这套题确实是校招备战过程中值得反复咀嚼的材料。如果你现在正在为校招笔试发愁我的建议是不要追求题目数量先把一套经典题目吃透把每一道题的暴力解、最优解、边界情况、复杂度分析都弄得清清楚楚比盲目刷50道新题有用得多。