提起腾讯暑期实习生招聘的编程题2017年这套题在牛客网和各大技术社区里流传很广属于典型的“大厂校招入门必刷”题单。很多准备过校招的同学应该都见过这三道题构造回文、字符移位、有趣的数字。题量不大但考察点非常集中——字符串处理、动态规划、排序与计数难度上属于“看着都会写对不容易”的类型。我至今还留着当年刷这套题的笔记。倒不是说题目本身有多惊艳而是它代表了一种很典型的国内大厂笔试命题思路不考偏题怪题专考基础算法的边界处理能力。哪怕是2025年的今天这套题拿出来给准备实习面试的同学练手依然不过时。这篇文章我就按当年的复盘思路把三道题从头到尾拆一遍包括每道题的解题推导、完整代码、易错点以及我当时踩过的坑。1. 2017腾讯暑期实习生编程题到底在考什么1.1 三题全景构造回文、字符移位、有趣的数字这套题一共三道每道题的考点和难度差异还是比较明显的先做个总览题目核心考点常见解法难度容易丢分点构造回文动态规划、最长回文子序列区间DP / LCS转化中等状态转移写错、边界初始化漏掉字符移位字符串操作、稳定性排序双指针搬移 / 冒泡思想简单偏中等题目要求的“相对顺序不变”被忽略有趣的数字排序、组合计数、去重排序后分类讨论中等偏难重复元素减出的二元组统计出错从表格能看出来这套题覆盖了笔试最常考的几类基础题型一类是经典的动态规划一类是字符串原地操作一类是排序思维加计数。三道题之间没有复杂的前置依赖非常适合用来检验自己的算法基本功。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[i1][j-1] 2。如果s[i] ! s[j]那么这两个字符不可能同时出现在同一个回文子序列中所以我们只能选择舍弃其中一个取最大值dp[i][j] max(dp[i1][j], dp[i][j-1])。边界条件是dp[i][i] 1因为单个字符本身就是一个回文子序列。如果字符串为空长度就是0。实现时需要注意的是遍历顺序。因为dp[i][j]依赖dp[i1][j]、dp[i][j-1]和dp[i1][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[i1][j-1]实际上是dp[i1][i]这是一个长度小于等于0的区间。由于dp矩阵默认初始化为0这个值刚好是0所以dp[i][j]会正确变成2不需要额外判断。理解了这一点你就能明白为什么初始化时要把整个dp都填成0了。2.3 另一种实现原串与逆序串的LCS除了区间DP这道题还有一个非常经典的等价转化一个字符串的最长回文子序列长度等于它和自身逆序串的最长公共子序列LCS长度。为什么因为回文子序列正着读和倒着读一样所以它一定同时出现在原串和逆序串中且保持相同的相对顺序。反过来原串和逆序串的公共子序列在原串中正序出现在逆序串中也正序出现合起来恰好构成一个回文子序列。基于这个结论代码就变成了标准的二维LCSdef 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]排序后相邻差最小值是01和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]内”。第二类原地重排类问题。题目如果说“不能申请额外空间”通常可以用“双指针 循环搬移”或者“从后往前处理”的模板。处理顺序很重要从后往前处理往往能避免覆盖未处理的元素从前往后处理则适合维护一个“已处理区域”的边界指针。第三类计数统计类问题。先排序然后用相邻关系来简化问题。涉及组合数的时候记得考虑重复元素和全相同数组的边界情况。这类题最容易丢分的地方不是算法而是分类讨论不完整。我把这套题中容易踩的坑整理成一张速查表方便大家复盘题目陷阱点正确做法错误做法构造回文子序列 vs 子串求最长回文子序列DP或LCS用最长回文子串的滑动窗口解法字符移位相对顺序稳定从后往前搬移大写字母直接新开列表收集大小写再拼接有趣的数字重复元素与全相同数组分类讨论重复段组合数只统计最大频次元素的C(cnt,2)5.2 我刷这套题时踩过的坑第一次做这套题的时候我在字符移位上就翻过车。当时我图省事直接用Python的列表解析把所有大写字母筛出来再把小写字母筛出来最后拼在一起。本地测试没问题但一提交就是“超出内存限制”或者“不满足题目要求”。后来我才意识到这里的“不能申请额外空间”不是靠自觉而是评测系统会卡掉所有新开数组的解法。构造回文我也踩过坑。最初我用的是求最长回文子串的“中心扩展法”因为题目里“删除字符”让我误以为剩下的字符必须连续。后来在草稿纸上画了几次才发现回文子序列和回文子串是两回事。这个转化如果没想明白后面怎么写都是错的。有趣的数字那道题我第一次提交只过了部分用例。排查后发现是全相同数组没特判max_count算成了n*n。当时在牛客网的讨论区里这道题的通过率非常低很多人都在重复元素和全相同数组这两个边界上栽了跟头。5.3 腾讯笔试命题风格小结从这套题能看出腾讯笔试的几个特点。一是题面朴实不搞花活。三道题都没有复杂的故事背景不会出现什么“魔法森林”“星际穿越”之类的包装直接给你最原始的算法问题。所以刷题时建议不要只看题面字数多的难题基础题才是主流。二是考察边界处理能力。这三道题没有任何一道是“模板题”直接套公式就能过的每一道都至少有一个需要分类讨论的边界构造回文的空串和单字符、字符移位的全大写或全小写、有趣数字的全相同和重复元素。这些边界恰恰是实际工程项目中最容易出bug的地方。三是限时压力下的取舍。三道题一个半小时左右每道题分配大概半小时。如果你在某一题卡住了我的建议是先跳过把后面能做的都写完再回头处理。面试官看的是整体完成度先把保底分拿到手比死磕一道难题重要得多。5.4 从套题延伸出的练习建议如果你刷完这套题还有时间建议接着练几道同类型的题目巩固手感。构造回文可以练LeetCode 516最长回文子序列字符移位可以练LeetCode 283移动零有趣的数字可以练一些“排序后相邻差值”类的题目比如LeetCode 1200最小绝对差。这几道题和腾讯2017这套题的思路非常接近练完以后你会发现笔试里大量题目都能归类到这几个模板里。再说一个具体的练习方法不要只满足于“提交通过”每道题做完之后尝试用至少两种方法实现。比如构造回文我既写了区间DP又写了LCS转化字符移位我既写了倒序搬移又写了正序插入。这样做的目的不是炫技而是通过对比不同解法理解它们各自的时间和空间复杂度差异遇到变种题时才能灵活切换。说实话腾讯2017这套题放在今天看难度不算高但它是一面很好的镜子能照出你对基础算法到底掌握得扎不扎实。尤其是有志于进大厂实习的同学我建议不要只盯着难题刷把这种经典套题反复做透比稀里糊涂刷一百道新题更有用。我自己后来在面试别人时也经常会不自觉拿这套题里的思路去考察候选人。最后再分享一个小技巧笔试前用这套题做一次限时模拟严格控制在一个小时内独立完成三道题。如果三次下来都能稳定通过那基本的算法功底就没问题了。祝大家都能顺利拿到心仪的实习offer。
腾讯2017实习生编程题全解析：回文、字符移位与数字计数
提起腾讯暑期实习生招聘的编程题2017年这套题在牛客网和各大技术社区里流传很广属于典型的“大厂校招入门必刷”题单。很多准备过校招的同学应该都见过这三道题构造回文、字符移位、有趣的数字。题量不大但考察点非常集中——字符串处理、动态规划、排序与计数难度上属于“看着都会写对不容易”的类型。我至今还留着当年刷这套题的笔记。倒不是说题目本身有多惊艳而是它代表了一种很典型的国内大厂笔试命题思路不考偏题怪题专考基础算法的边界处理能力。哪怕是2025年的今天这套题拿出来给准备实习面试的同学练手依然不过时。这篇文章我就按当年的复盘思路把三道题从头到尾拆一遍包括每道题的解题推导、完整代码、易错点以及我当时踩过的坑。1. 2017腾讯暑期实习生编程题到底在考什么1.1 三题全景构造回文、字符移位、有趣的数字这套题一共三道每道题的考点和难度差异还是比较明显的先做个总览题目核心考点常见解法难度容易丢分点构造回文动态规划、最长回文子序列区间DP / LCS转化中等状态转移写错、边界初始化漏掉字符移位字符串操作、稳定性排序双指针搬移 / 冒泡思想简单偏中等题目要求的“相对顺序不变”被忽略有趣的数字排序、组合计数、去重排序后分类讨论中等偏难重复元素减出的二元组统计出错从表格能看出来这套题覆盖了笔试最常考的几类基础题型一类是经典的动态规划一类是字符串原地操作一类是排序思维加计数。三道题之间没有复杂的前置依赖非常适合用来检验自己的算法基本功。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[i1][j-1] 2。如果s[i] ! s[j]那么这两个字符不可能同时出现在同一个回文子序列中所以我们只能选择舍弃其中一个取最大值dp[i][j] max(dp[i1][j], dp[i][j-1])。边界条件是dp[i][i] 1因为单个字符本身就是一个回文子序列。如果字符串为空长度就是0。实现时需要注意的是遍历顺序。因为dp[i][j]依赖dp[i1][j]、dp[i][j-1]和dp[i1][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[i1][j-1]实际上是dp[i1][i]这是一个长度小于等于0的区间。由于dp矩阵默认初始化为0这个值刚好是0所以dp[i][j]会正确变成2不需要额外判断。理解了这一点你就能明白为什么初始化时要把整个dp都填成0了。2.3 另一种实现原串与逆序串的LCS除了区间DP这道题还有一个非常经典的等价转化一个字符串的最长回文子序列长度等于它和自身逆序串的最长公共子序列LCS长度。为什么因为回文子序列正着读和倒着读一样所以它一定同时出现在原串和逆序串中且保持相同的相对顺序。反过来原串和逆序串的公共子序列在原串中正序出现在逆序串中也正序出现合起来恰好构成一个回文子序列。基于这个结论代码就变成了标准的二维LCSdef 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]排序后相邻差最小值是01和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]内”。第二类原地重排类问题。题目如果说“不能申请额外空间”通常可以用“双指针 循环搬移”或者“从后往前处理”的模板。处理顺序很重要从后往前处理往往能避免覆盖未处理的元素从前往后处理则适合维护一个“已处理区域”的边界指针。第三类计数统计类问题。先排序然后用相邻关系来简化问题。涉及组合数的时候记得考虑重复元素和全相同数组的边界情况。这类题最容易丢分的地方不是算法而是分类讨论不完整。我把这套题中容易踩的坑整理成一张速查表方便大家复盘题目陷阱点正确做法错误做法构造回文子序列 vs 子串求最长回文子序列DP或LCS用最长回文子串的滑动窗口解法字符移位相对顺序稳定从后往前搬移大写字母直接新开列表收集大小写再拼接有趣的数字重复元素与全相同数组分类讨论重复段组合数只统计最大频次元素的C(cnt,2)5.2 我刷这套题时踩过的坑第一次做这套题的时候我在字符移位上就翻过车。当时我图省事直接用Python的列表解析把所有大写字母筛出来再把小写字母筛出来最后拼在一起。本地测试没问题但一提交就是“超出内存限制”或者“不满足题目要求”。后来我才意识到这里的“不能申请额外空间”不是靠自觉而是评测系统会卡掉所有新开数组的解法。构造回文我也踩过坑。最初我用的是求最长回文子串的“中心扩展法”因为题目里“删除字符”让我误以为剩下的字符必须连续。后来在草稿纸上画了几次才发现回文子序列和回文子串是两回事。这个转化如果没想明白后面怎么写都是错的。有趣的数字那道题我第一次提交只过了部分用例。排查后发现是全相同数组没特判max_count算成了n*n。当时在牛客网的讨论区里这道题的通过率非常低很多人都在重复元素和全相同数组这两个边界上栽了跟头。5.3 腾讯笔试命题风格小结从这套题能看出腾讯笔试的几个特点。一是题面朴实不搞花活。三道题都没有复杂的故事背景不会出现什么“魔法森林”“星际穿越”之类的包装直接给你最原始的算法问题。所以刷题时建议不要只看题面字数多的难题基础题才是主流。二是考察边界处理能力。这三道题没有任何一道是“模板题”直接套公式就能过的每一道都至少有一个需要分类讨论的边界构造回文的空串和单字符、字符移位的全大写或全小写、有趣数字的全相同和重复元素。这些边界恰恰是实际工程项目中最容易出bug的地方。三是限时压力下的取舍。三道题一个半小时左右每道题分配大概半小时。如果你在某一题卡住了我的建议是先跳过把后面能做的都写完再回头处理。面试官看的是整体完成度先把保底分拿到手比死磕一道难题重要得多。5.4 从套题延伸出的练习建议如果你刷完这套题还有时间建议接着练几道同类型的题目巩固手感。构造回文可以练LeetCode 516最长回文子序列字符移位可以练LeetCode 283移动零有趣的数字可以练一些“排序后相邻差值”类的题目比如LeetCode 1200最小绝对差。这几道题和腾讯2017这套题的思路非常接近练完以后你会发现笔试里大量题目都能归类到这几个模板里。再说一个具体的练习方法不要只满足于“提交通过”每道题做完之后尝试用至少两种方法实现。比如构造回文我既写了区间DP又写了LCS转化字符移位我既写了倒序搬移又写了正序插入。这样做的目的不是炫技而是通过对比不同解法理解它们各自的时间和空间复杂度差异遇到变种题时才能灵活切换。说实话腾讯2017这套题放在今天看难度不算高但它是一面很好的镜子能照出你对基础算法到底掌握得扎不扎实。尤其是有志于进大厂实习的同学我建议不要只盯着难题刷把这种经典套题反复做透比稀里糊涂刷一百道新题更有用。我自己后来在面试别人时也经常会不自觉拿这套题里的思路去考察候选人。最后再分享一个小技巧笔试前用这套题做一次限时模拟严格控制在一个小时内独立完成三道题。如果三次下来都能稳定通过那基本的算法功底就没问题了。祝大家都能顺利拿到心仪的实习offer。