企业官网建设流程全解析

提起腾讯暑期实习生招聘的编程题，2017年这套题在牛客网和各大技术社区里流传很广，属于典型的“大厂校招入门必刷”题单。很多准备过校招的同学应该都见过这三道题：构造回文、字符移位、有趣的数字。题量不大，但考察点非常集中——字符串处理、动态规划、排序与计数，难度上属于“看着都会，写对不容易”的类型。

我至今还留着当年刷这套题的笔记。倒不是说题目本身有多惊艳，而是它代表了一种很典型的国内大厂笔试命题思路：不考偏题怪题，专考基础算法的边界处理能力。哪怕是2025年的今天，这套题拿出来给准备实习面试的同学练手，依然不过时。这篇文章我就按当年的复盘思路，把三道题从头到尾拆一遍，包括每道题的解题推导、完整代码、易错点，以及我当时踩过的坑。

1. 2017腾讯暑期实习生编程题：到底在考什么

1.1 三题全景：构造回文、字符移位、有趣的数字

这套题一共三道，每道题的考点和难度差异还是比较明显的，先做个总览：

从表格能看出来，这套题覆盖了笔试最常考的几类基础题型：一类是经典的动态规划，一类是字符串原地操作，一类是排序思维加计数。三道题之间没有复杂的前置依赖，非常适合用来检验自己的算法基本功。

1.2 这套题为什么值得反复刷

先说一个观点：大厂笔试题从来不追求“难倒所有人”，而是想在有限时间内筛选出“基础扎实、思路清晰、能处理边界情况”的人。2017年这套题就是个很好的样本。

举个例子，构造回文这道题，本质上是求最长回文子序列，属于动态规划里的经典问题。但题目不会直接告诉你“请用DP”，而是包装成“删除若干字符使得剩余字符串为回文”。如果你能看穿这层包装，说明你有一定的抽象建模能力。字符移位这道题就更典型了，题目明确要求“不能申请额外空间”，这其实是在考察你在资源受限条件下的思考习惯。很多同学一上来就用一个新字符串拼接，虽然答案对，但不符合题目要求，直接判错。

我个人建议，准备实习面试的同学把这套题至少刷三遍：第一遍独立完成，第二遍对照题解优化思路，第三遍限时训练模拟真实笔试环境。每刷一遍，你对边界条件的敏感度都会明显提升。

2. 构造回文：从“删字符”到动态规划

2.1 题意拆解与第一直觉

先看题目描述：给定一个字符串s，你可以从中删除一些字符，使得剩下的字符串是一个回文串。问最少需要删除多少个字符。

我第一次看到这道题的时候，脑子里第一个想法是：这不就是求最长回文子串吗？但仔细一想不对，回文子串要求连续，而这里删除字符之后剩下的字符在原串里不一定连续。比如字符串"aebcbda"，删除'e'和'd'之后得到"abcba"，是一个回文串，但"abcba"在原串里并不是连续子串。

所以这个问题实际上是：在原串中找一个最长的回文子序列。子序列不要求连续，只需要保持相对顺序。删除的字符数 = 原字符串长度 - 最长回文子序列长度。

这一步转化很关键。如果你没有意识到是“子序列”而不是“子串”，后面所有解法都会跑偏。

2.2 最长回文子序列的DP推导

动态规划的第一步是定义状态。这里我用dp[i][j]表示字符串s[i:j]（闭区间）内的最长回文子序列长度。

状态转移分两种情况：

• 如果s[i] == s[j]，那么这两个字符可以同时作为回文子序列的两端，所以dp[i][j] = dp[i+1][j-1] + 2。
• 如果s[i] != s[j]，那么这两个字符不可能同时出现在同一个回文子序列中，所以我们只能选择舍弃其中一个，取最大值：dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

边界条件是dp[i][i] = 1，因为单个字符本身就是一个回文子序列。如果字符串为空，长度就是0。

实现时需要注意的是遍历顺序。因为dp[i][j]依赖dp[i+1][j]、dp[i][j-1]和dp[i+1][j-1]，都是从长度更短的子串推导到更长的子串，所以外层循环应该从字符串尾部开始，或者按子串长度从小到大遍历。我习惯用后一种方式，逻辑更直观：

def longest_palindrome_subseq(s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): dp[i][i] = 1 for j in range(i + 1, n): if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] + 2 else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) return dp[0][n - 1] s = input().strip() print(len(s) - longest_palindrome_subseq(s))

这里有个细节我当初栽过跟头：当j = i + 1且s[i] == s[j]时，dp[i+1][j-1]实际上是dp[i+1][i]，这是一个长度小于等于0的区间。由于dp矩阵默认初始化为0，这个值刚好是0，所以dp[i][j]会正确变成2，不需要额外判断。理解了这一点，你就能明白为什么初始化时要把整个dp都填成0了。

2.3 另一种实现：原串与逆序串的LCS

除了区间DP，这道题还有一个非常经典的等价转化：一个字符串的最长回文子序列长度，等于它和自身逆序串的最长公共子序列（LCS）长度。

为什么？因为回文子序列正着读和倒着读一样，所以它一定同时出现在原串和逆序串中，且保持相同的相对顺序。反过来，原串和逆序串的公共子序列，在原串中正序出现，在逆序串中也正序出现，合起来恰好构成一个回文子序列。

基于这个结论，代码就变成了标准的二维LCS：

def lcs(s1: str, s2: str) -> int: n = len(s1) dp = [[0] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, n + 1): if s1[i - 1] == s2[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 dp[n][n] s = input().strip() print(len(s) - lcs(s, s[::-1]))

两种做法的时间复杂度都是 O(n²)，空间复杂度也都是 O(n²)。但从实际笔试的角度看，LCS 转化更不容易写错，因为dp矩阵从1开始索引，天然避开了负区间的问题。我个人在考场上更推荐LCS写法，省心。

2.4 复杂度与边界处理

当字符串长度为1000左右时，O(n²) 的二维DP在绝大多数在线评测系统里都能稳定通过。但如果字符串长度到了5000以上，Python的二维列表就会比较吃力——每个格子一个Python对象，内存开销非常大。这时候可以考虑用滚动数组优化空间，把dp压缩成一维：

def longest_palindrome_subseq_optimized(s: str) -> int: n = len(s) dp = [0] * n for i in range(n - 1, -1, -1): dp[i] = 1 prev = 0 for j in range(i + 1, n): temp = dp[j] if s[i] == s[j]: dp[j] = prev + 2 else: dp[j] = max(dp[j], dp[j - 1]) prev = temp return dp[n - 1]

这段代码里prev保存的是左上角的值，也就是上一轮循环中dp[j-1]的旧值，因为它在被覆盖之前就已经被暂存了。滚动数组是笔试中很重要的优化手段，不光这道题，很多二维DP都能用它降一维空间。

边界条件方面还有一个容易忽略的点：输入字符串可能包含空格。如果题目没有明确说明字符串不含空格，建议直接用sys.stdin.readline().strip()读取整行，不要用input().split()，否则带空格的字符串会被错误地拆成多个单词。

3. 字符移位：大小写稳定重排的经典操作

3.1 题目限制：“不能申请额外空间”意味着什么

第二道题是字符移位，题目大致是这样：给定一个字符串，要求把所有大写字母移到字符串的末尾，同时保持所有字符的相对顺序不变，并且不能申请额外的空间。

注意最后这个限制。很多同学第一反应是：把大写字母和小写字母分别收集到两个列表，再拼接起来。这个做法逻辑上没错，但它申请了额外空间，不满足题意。腾讯在这里卡得比较死，一旦你用了新数组，这道题就是0分。

所以这道题本质上是在考察原地稳定重排。什么叫稳定？就是小写字母之间的相对顺序不能变，大写字母之间的相对顺序也不能变。比如输入"AabBcC"，正确输出是"abcABC"，而不是"bacACB"之类的乱序。

3.2 倒序搬移法：从后往前处理大写字母

我在网上看到最多的解法是倒序搬移，思路非常清晰：从字符串末尾往前扫描，每遇到一个大写字母，就把它“搬”到当前末尾区域的最前面，同时把中间的元素整体向前移动一位。

可以想象成在数组尾部划出一块“大写字母专区”，这个专区的边界用指针j维护。初始时j指向数组最后一个位置，从后往前扫描，遇到大写字母就把它放到j位置，同时j左移一位。因为是从后往前处理，所以后面已经放置好的大写字母不会被破坏。

s = list(input().strip()) n = len(s) j = n - 1 for i in range(n - 1, -1, -1): if 'A' <= s[i] <= 'Z': ch = s[i] for k in range(i + 1, j + 1): s[k - 1] = s[k] s[j] = ch j -= 1 print(''.join(s))

拿"aBcDeFg"来走一遍：初始数组['a','B','c','D','e','F','g']，j = 6。倒序扫描到索引5的'F'，把['D','e']整体左移一位，'F'放到索引6，得到['a','B','c','D','e','g','F']，j变成5。接着扫描到索引3的'D'，把['e','g']左移，'D'放到索引5，得到['a','B','c','e','g','D','F']，j变成4。最后扫描到索引1的'B'，把['c','e','g']左移，'B'放到索引4，得到['a','c','e','g','B','D','F']。输出"acegBDF"，完全正确。

这个解法的时间复杂度最坏是O(n²)，因为每次搬移都要移动一串字符。不过笔试数据规模通常不大，几千个字符以内完全没问题。

3.3 正序插入法：维护小写字母写入位置

除了倒序搬移，还有一种正序遍历的写法，思想是维护一个指针pos，表示下一个小写字母应该放置的位置。扫描过程中遇到小写字母，就把它通过循环移位搬到pos处，然后pos加1。遇到大写字母直接跳过。

s = list(input().strip()) n = len(s) pos = 0 for i in range(n): if 'a' <= s[i] <= 'z': if i != pos: ch = s[i] for k in range(i, pos, -1): s[k] = s[k - 1] s[pos] = ch pos += 1 print(''.join(s))

这个写法其实是把问题反过来看：不主动去移动大写字母，而是把每个小写字母往“前面”的正确位置搬。每次遇到一个新的小写字母，就把从pos到i-1的这一段整体右移一位，然后把当前字符放到pos。由于pos之前的区域已经是排列好的小写字母，这个操作不会破坏稳定性。

两种写法我实测下来，正序插入法的逻辑更符合直觉，面试时也更容易跟面试官讲清楚。不过如果你只准备一种，我建议把倒序搬移法记熟，因为它在思路上和“尾部建区”的套路更通用——类似的题目比如把0移动到数组末尾，也可以套这个模板。

3.4 易错点与输入处理

这道题最大的易错点不是算法本身，而是忽略了“相对顺序不变”。很多人用Python的sorted按大小写排序，或者用双指针直接交换字符，虽然能分出大小写，但相对顺序被打乱了。比如"Ba"，直接交换得到"aB"，字母顺序没变，但如果输入是"BAc"，直接交换可能得到"AcB"之类的结果，大写字母'B'和'A'的相对顺序就错了。

另一个坑是输入读取。这道题的输入可能是一整行字符串，也可能包含换行符。用input()读取时默认会去掉末尾换行，但要注意如果字符串本身就是空串，input()返回空字符串，代码也应该能正常输出空串。我见过有人在这里没加判空，结果空输入时直接报IndexError。

还有一种情况是输入可能包含非字母字符，比如数字或符号。题目原意是只处理大写和小写字母，但保险起见，判断时最好用'A' <= c <= 'Z'和'a' <= c <= 'z'，而不是c.isupper()和c.islower()。因为在某些编码环境下，isupper()会对一些特殊字符返回奇怪的结果，用ASCII范围判断最稳。

4. 有趣的数字：排序、计数与边界陷阱

4.1 先排序，一切好说

第三题是这样的：有n个数，两两组成二元组，问差最小的一对有多少个，差最大的一对有多少个。注意这里的“对”是指下标对，也就是说值相同的两个不同元素也算不同的对。

这道题的突破口非常明确：先把数组排序。排序之后，差最大的两个数一定是最大值和最小值，差最小的两个数一定是排序后相邻的两个数。这是所有后续计算的基础。

我用一个具体例子来说明。假设输入是[1, 2, 3, 4, 5]，排序后不变。最大差是5 - 1 = 4，只有(1, 5)这一对，所以最大差对数1。最小差是1，排序后相邻元素差为1的有(1,2)、(2,3)、(3,4)、(4,5)四对，所以最小差对数4。

看起来很简单，但一旦数组里有重复数字，情况就复杂了。比如[1, 1, 2, 3]，排序后相邻差最小值是0（1和1），那差为0的对数应该算几对？答案是1对（两个1），但如果数组是[1, 1, 1, 2]，三个1之间可以组成3对差为0的二元组。这就是这道题最经典的分支情况。

4.2 最大差的对数怎么数

最大差一定等于最大值 - 最小值，这个没悬念。关键是算有多少对能达到这个差值。

如果最大值不等于最小值，那么差最大的对一定是由“一个最大值”和“一个最小值”组成的。所以答案就是最大值出现次数 × 最小值出现次数。

举个例子：[1, 1, 3, 3, 3]，最小值1出现2次，最大值3出现3次，差最大的对数是2 × 3 = 6。这6对分别是每个1和每个3的组合，下标不同，都算不同的对。

但是！如果最大值等于最小值，也就是整个数组所有元素都相同，那情况就变了。这时候最大值和最小值是同一个数，任意两个元素之间的差都是0，而“差最大”和“差最小”实际上是同一个概念。这种情况下，对数应该是n * (n - 1) // 2，即从n个元素中任选两个的组合数。

我当初就是在这里没考虑周全，直接套用“最大值出现次数 × 最小值出现次数”，结果全相同数组的用例直接挂掉。因为max_count * min_count算出来是n * n，但正确的对数应该是C(n, 2)，差了一倍还多。

4.3 最小差的对数：重复元素的两种情况

最小差同样需要分情况讨论。

第一种情况：数组中有重复元素。那么最小差一定是0，我们只需要统计所有重复元素能组成多少个差为0的二元组。也就是对于每个出现次数cnt ≥ 2的元素，累加C(cnt, 2)。这里有个隐藏陷阱：不能只统计出现次数最多的那个元素。比如数组[1, 1, 2, 2]，1出现2次，2出现2次，差为0的组数应该是C(2,2) + C(2,2) = 2，而不是只数一个。

第二种情况：数组中没有重复元素。最小差就是排序后所有相邻元素差的最小值min_diff。然后遍历一遍排序后的数组，统计相邻差等于min_diff的相邻对数量。

注意这里我强调的是“相邻对”，因为最小差只可能出现在排序后的相邻元素之间。如果一对元素不相邻，那么它们之间至少还夹着一个元素，差值不可能比相邻差更小。这是排序法解决这道题的核心依据。

n = int(input()) a = list(map(int, input().split())) a.sort() if a[0] == a[-1]: min_count = max_count = n * (n - 1) // 2 else: max_count = a.count(a[0]) * a.count(a[-1]) min_diff = min(a[i + 1] - a[i] for i in range(n - 1)) if min_diff == 0: min_count = 0 i = 0 while i < n: j = i while j < n and a[j] == a[i]: j += 1 cnt = j - i if cnt >= 2: min_count += cnt * (cnt - 1) // 2 i = j else: min_count = 0 for i in range(n - 1): if a[i + 1] - a[i] == min_diff: min_count += 1 print(min_count, max_count)

这里我特意用a.count(a[0])而不是手动统计，因为数组已经排序，值相同的元素一定连续，count方法是安全的。但在计算最小差对数时，不能用count直接乘，因为一个重复元素组内的所有差为0的组合都要算进去，必须遍历一遍，把每个重复段单独拿出来算组合数。

4.4 全相同数组的特判

前面提到了全相同数组[1, 1, 1]的情况，这里再单独强调一下。全相同数组下：

• 最大差 = 0，最小差 = 0，两者相等。
• 最大差对数 = 最小差对数 =C(3, 2) = 3。

如果用通用逻辑走一遍，max_count = a.count(a[0]) * a.count(a[-1]) = 3 × 3 = 9，明显不对。所以必须在开头就加一个if a[0] == a[-1]的特判。

还有一种更隐蔽的情况：数组不完全相同，但最小差等于0，此时最小差对数按重复元素组合数算；而最大差对数依然按最小值次数 × 最大值次数算。这两者的计算逻辑是独立的，不要混在一起。

我在实际笔试时遇到过一组用例，数组是[1, 1, 2, 2, 3]。最小差0的对数应该是C(2,2) + C(2,2) = 2，最大差3 - 1 = 2，对数应该是2 × 1 = 2。如果你在算最小差时不小心把重复段之间的差值也统计进去，就会出错。

5. 复盘：笔试技巧与常见错误速查

5.1 三类题型的通用解法模板

刷完这套题，我总结了一个通用思路，基本上覆盖了这三道题对应的题型。

第一类，字符串删除/子序列类问题。凡是求“删除多少字符后满足某性质”，优先想能不能转化为“在不删的情况下最多保留多少”，也就是求最长满足该性质的子序列。最长回文子序列、最长公共子序列、最长递增子序列都是这个套路。这类题的解法大多数是DP，状态定义一般是“考虑前i个字符 / 区间[i, j]内”。

第二类，原地重排类问题。题目如果说“不能申请额外空间”，通常可以用“双指针 + 循环搬移”或者“从后往前处理”的模板。处理顺序很重要：从后往前处理往往能避免覆盖未处理的元素，从前往后处理则适合维护一个“已处理区域”的边界指针。

第三类，计数统计类问题。先排序，然后用相邻关系来简化问题。涉及组合数的时候，记得考虑重复元素和全相同数组的边界情况。这类题最容易丢分的地方不是算法，而是分类讨论不完整。

我把这套题中容易踩的坑整理成一张速查表，方便大家复盘：

5.2 我刷这套题时踩过的坑

第一次做这套题的时候，我在字符移位上就翻过车。当时我图省事，直接用Python的列表解析把所有大写字母筛出来，再把小写字母筛出来，最后拼在一起。本地测试没问题，但一提交就是“超出内存限制”或者“不满足题目要求”。后来我才意识到，这里的“不能申请额外空间”不是靠自觉，而是评测系统会卡掉所有新开数组的解法。

构造回文我也踩过坑。最初我用的是求最长回文子串的“中心扩展法”，因为题目里“删除字符”让我误以为剩下的字符必须连续。后来在草稿纸上画了几次，才发现回文子序列和回文子串是两回事。这个转化如果没想明白，后面怎么写都是错的。

有趣的数字那道题，我第一次提交只过了部分用例。排查后发现是全相同数组没特判，max_count算成了n*n。当时在牛客网的讨论区里，这道题的通过率非常低，很多人都在重复元素和全相同数组这两个边界上栽了跟头。

5.3 腾讯笔试命题风格小结

从这套题能看出腾讯笔试的几个特点。

一是题面朴实，不搞花活。三道题都没有复杂的故事背景，不会出现什么“魔法森林”“星际穿越”之类的包装，直接给你最原始的算法问题。所以刷题时建议不要只看题面字数多的难题，基础题才是主流。

二是考察边界处理能力。这三道题没有任何一道是“模板题”直接套公式就能过的，每一道都至少有一个需要分类讨论的边界：构造回文的空串和单字符、字符移位的全大写或全小写、有趣数字的全相同和重复元素。这些边界恰恰是实际工程项目中最容易出bug的地方。

三是限时压力下的取舍。三道题一个半小时左右，每道题分配大概半小时。如果你在某一题卡住了，我的建议是先跳过，把后面能做的都写完，再回头处理。面试官看的是整体完成度，先把保底分拿到手比死磕一道难题重要得多。

5.4 从套题延伸出的练习建议

如果你刷完这套题还有时间，建议接着练几道同类型的题目巩固手感。构造回文可以练LeetCode 516（最长回文子序列），字符移位可以练LeetCode 283（移动零），有趣的数字可以练一些“排序后相邻差值”类的题目，比如LeetCode 1200（最小绝对差）。这几道题和腾讯2017这套题的思路非常接近，练完以后你会发现笔试里大量题目都能归类到这几个模板里。

再说一个具体的练习方法：不要只满足于“提交通过”，每道题做完之后，尝试用至少两种方法实现。比如构造回文，我既写了区间DP，又写了LCS转化；字符移位，我既写了倒序搬移，又写了正序插入。这样做的目的不是炫技，而是通过对比不同解法，理解它们各自的时间和空间复杂度差异，遇到变种题时才能灵活切换。

说实话，腾讯2017这套题放在今天看，难度不算高，但它是一面很好的镜子，能照出你对基础算法到底掌握得扎不扎实。尤其是有志于进大厂实习的同学，我建议不要只盯着难题刷，把这种经典套题反复做透，比稀里糊涂刷一百道新题更有用。我自己后来在面试别人时，也经常会不自觉拿这套题里的思路去考察候选人。

最后再分享一个小技巧：笔试前用这套题做一次限时模拟，严格控制在一个小时内独立完成三道题。如果三次下来都能稳定通过，那基本的算法功底就没问题了。祝大家都能顺利拿到心仪的实习offer。