腾讯暑期实习生笔试题复盘：构造回文、字符移位与有趣的数字

每年三、四月，牛客网的笔试讨论区都会冒出一堆“腾讯暑期实习生编程题”的求助帖。我前几天整理旧电脑里的算法收藏夹，翻出了2017年腾讯暑期实习生招聘的笔试题整理文档——构造回文、字符移位、有趣的数字，三道题用一晚上重新写了一遍，感受还挺深。七八年过去，这套题放在今天依然是很好的面试热身材料：不考偏题怪题，但每一道都能往下挖出两三层考点，代码量不大，坑倒是不少。无论你是准备大厂实习校招的在校生，还是想系统补一补算法功底的转行开发者，这套题都值得静下心来做一遍。这篇文章我会把三道题目的完整推导过程、边界条件、我当年踩过的坑，以及后来复盘时才想明白的考点，全部拆开讲清楚。

1. 重温经典：这套题到底在考什么

1.1 题目背景与当年的笔试环境

腾讯的暑期实习生招聘一般从每年三月启动，笔试环节通常安排在三月中下旬，线上OJ答题，用的是牛客网那套在线评测系统。2017年的笔试编程题一共三道，时间大概是120分钟左右，语言不限，C++、Java、Python都可以。我印象比较深的是当时笔试页面比现在朴素很多，没有代码补全、没有本地调试，写完直接提交，跑不过就是跑不过，不像现在有些平台还能看到部分用例结果。

当时的技术氛围和现在不太一样：身边很多同学对动态规划还停留在“背模板”的阶段，会写最长上升子序列，但换个包装就认不出来。腾讯这三道题出得挺有水平，表面看都是基础题，实际上每一道都埋了“如果只背模板，你会挂在这里”的暗坑。比如构造回文，如果只背了“最长回文子串”的马拉车算法，拿到这道题会直接懵掉；比如字符移位，如果直接两两交换，输出结果会违反“保持相对顺序”的要求；比如有趣的数字，如果不做去重和相等值统计，边界用例一测就挂。

1.2 三道题的知识点地图

把这三道题的知识点拆开看，其实覆盖了大厂笔试最常考的几块基本面：

这套题组合起来就是在考察一件事：你能不能把问题抽象成已知的算法模型，而不是对着题目硬模拟。这也是为什么我推荐大家都做一遍——做完再对照下面的推导过程，你会发现自己对“算法设计”这四个字的理解会深一层。

2. “构造回文”：最长回文子序列的两种解法与一个本质

2.1 题目描述与第一层思路

题目是这样：给定一个字符串s，你可以从中删除一些字符，使得剩下的字符串成为一个回文串。问最少需要删除多少个字符。字符串长度不超过1000，只包含小写字母。例如输入abcda，删掉b和c得到aba，或者删掉c和d得到aba，最少删除2个字符，输出2。

注意一个关键表述：这里说的是“剩下的字符串成为回文串”，而不是“找到最长的回文子串”。字符串删除若干字符后剩下的子序列，必须是回文的，所以本质是求最长回文子序列（Longest Palindromic Subsequence，LPS）的长度。最少删除数 = 原串长度 - 最长回文子序列长度。

为什么不是最长回文子串？回文子串要求连续，回文子序列只需要保持相对顺序。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 =abcda，rev =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]

n=1000时，dp表是1001×1001个整数，大约10^6级别，内存完全没问题。如果环境内存紧张，还可以滚动数组压到两个一维数组，后面我讲优化方案时一起说。

2.3 解法二：直接区间DP，边界可别写错

除了LCS转换，还有另一种更贴合“删除字符”语义的写法——区间DP。定义dp[i][j]表示子串s[i..j]变成回文串最少需要删除的字符数。

转移逻辑分两种情况：

• 如果s[i] == s[j]，说明两端的字符可以同时保留，问题转化为s[i+1..j-1]变成回文最少删除数，即dp[i][j] = dp[i+1][j-1]
• 如果s[i] != s[j]，两端的字符不可能同时出现在最终回文串的首尾，所以至少删一个，dp[i][j] = min(dp[i+1][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[i+1][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[i+1][j-1]访问的是dp[i+1][i]，下标是合法的，但dp[i+1][j-1]在Python里如果n大于1，i+1不会越界，j-1等于i，访问的是自己初始化的0，结果没问题。但如果你用C++写二维vector，当n等于2时，i=0，j=1，dp[1][0]这个位置是存在的（因为dp初始化为n×n），值为0，也安全。但如果你把dp初始化为n×n且从length=1开始做了别的处理，这里就要特别小心。最稳妥的写法是显式判断length > 2，或者把dp[i+1][j-1]在length==2时直接赋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 f，idx=0
• i=0，a是小写，交换arr[0]和arr[0]，结果不变，idx=1
• i=1，B是大写，跳过
• i=2，C是大写，跳过
• i=3，d是小写，交换arr[1]和arr[3]，得到 a d C B E f，idx=2
• i=4，E是大写，跳过
• i=5，f是小写，交换arr[2]和arr[5]，得到 a d f B E C，idx=3

最终结果是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_cast<unsigned 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×3=9。所以代码里要先判断min_val == max_val，是的话直接返回C(n,2), C(n,2)。

如果最大值和最小值不相等，还要注意：最大值和最小值的个数可能不止一个。例如[1, 1, 4, 4, 5]，最小值1出现2次，最大值5出现1次，最大差4，对数=2×1=2，即(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_pairs

nums.count(min_val)和nums.count(max_val)虽然是两次线性扫描，但合起来还是O(n)，不影响整体复杂度。整个算法O(n log n)主要由排序贡献。

4.4 边界测试和性能复盘

这种题最容易挂的就是边界情况，我列出几组自测数据，建议写完后逐一跑一遍：

上面第二行我一开始写错了，这里特意标注出来，想提醒大家：这种题手算都要细心，写代码时更要逐分支验证。我当年提交时就是漏了“所有数相同”这个分支，导致[5, 5, 5]这种用例挂掉。笔试平台的测试数据往往就爱放这种极端输入，你平时自测不跑，考场上就只能靠运气。

性能方面，n=10^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年那会儿，大厂笔试还很看重基本功，三道题没有一道需要很高深的算法，但每一道都考察了“能不能把问题看透”的能力。这种能力不是靠背题背出来的，而是在反复推导、反复踩坑、反复复盘中长出来的。把这三道题彻底吃透，你收获的远远不止几道题的答案。