腾讯2017秋招笔试编程题放到现在看依然不过时。每年到了秋招季都有人在牛客网上把这一批题目翻出来重新练手原因很简单腾讯笔试的命题风格多年保持稳定基础算法和数据结构的考察占了绝对大头题面喜欢用生活场景做包装真正考的是把实际问题抽象成算法模型的能力。这篇文章不是简单地贴一堆代码而是按我自己备考和带人准备校招的经验把这类试卷里最有代表性的贪心、动态规划、字符串处理、排序细节全部拆开讲一遍。题目的回忆版本在网上能找到不少我结合当年的笔试风格和现在面试的延伸方向做了重新整理配了可直接运行的Python代码不管是明年才参加校招的在校生还是打算跳槽的社招选手都可以直接拿这份内容当复习提纲。1. 腾讯2017秋招笔试考什么怎么准备1.1 笔试的基本盘时间、题量与判分逻辑腾讯的笔试一般在牛客网这类在线评测平台进行时间通常在90到120分钟编程题数量一般控制在3到5道。2017年的秋招笔试我印象里比较经典的组合是四道编程题难度有明显梯度前面一两道属于热身级只要思路正确就能写出来考察的是基本功后面一两道则拉开了区分度需要你对算法有比较深的理解还要能在有限时间内把代码写对。这里要重点提一下判分逻辑。牛客网这类平台的判题是全用例跑分每道题可能通过多个测试点全部通过才能拿到满分。这意味着你写出的代码不仅要思路对还要能处理各种边界条件包括空输入、极端数据、重复元素、大整数溢出等。很多人看到题觉得我会做结果一提交只有部分通过问题大多出在细节上这个后面我会专门展开。腾讯笔试还有一个特点题目描述通常很长会给你构造一个具体业务场景。比如路灯安置、歌单组合、纸牌游戏、机器任务分配这些都是典型的场景包装。你必须学会从一大段描述里迅速提炼出真正的数学模型。我见过很多候选人算法本身没问题但读题花了二十分钟还没搞清楚到底要求什么。所以备考笔试练习读题和抽象建模和练习算法本身一样重要。1.2 从回忆版真题看腾讯的命题习惯网上流传的2017年腾讯秋招笔试编程题回忆版本比较多我整理了最常被提到的几道构造回文、字符移位、有趣的数字、小Q的歌单、安排机器、纸牌游戏、贪吃的小Q、安置路灯。这些题目虽然年份较早但很有代表性之后的校招笔试里也能看到它们的影子。从这些题目里能明显看出几个命题习惯。第一经典算法为主偏难怪题很少。贪心、动态规划、字符串处理、排序、二分查找是绝对主力。像后缀自动机、树链剖分、网络流这种竞赛级考点在腾讯笔试里基本不会出现。命题人更想看到你把基础数据结构用熟练而不是背了多少高级模板。第二数据范围设计有讲究。很多题目的n给到了10^5这个量级这基本是在暗示你需要O(nlogn)或者O(n)的解法O(n^2)的暴力大概率超时。反过来如果n只有10^3以内那暴力枚举可能就是一个可接受的方案。学会从数据范围反推算法是笔试实战里非常关键的一项能力。第三结果常常需要取模。像小Q的歌单这种组合计数题结果要对10^97取模。这既是为了防止大整数溢出也是命题人考察你是否了解这个常见套路。10^97是一个质数在组合计数、快速幂、逆元等场景里反复出现你应该形成条件反射看到结果可能很大请对10^97取模就直接想到组合数预计算。第四输出格式有严格要求。有的题需要输出最少操作次数有的需要输出方案数有的需要输出最小值以及对应的数对个数。读题时一定要把输出要求圈出来避免做对了思路却在输出格式上扣分。1.3 备考节奏与刷题方法针对腾讯这类大厂笔试我的建议是提前两到三个月开始准备分三个阶段推进。第一个阶段是打基础时间约三到四周。把常见的数据结构和算法过一遍包括数组、链表、栈、队列、哈希表、二叉树、堆、排序、二分查找、贪心、动态规划、深度优先搜索、广度优先搜索。不需要追求竞赛难度但要做到看到题目能快速判断它属于哪一类。第二个阶段是刷真题时间约三到四周。把牛客网上能搜到的腾讯、阿里、字节等大厂历年真题刷一遍每天两到三题不求多但求透。每做完一道题我建议你在本子上写下三行总结题目类型、核心解法、时间与空间复杂度。这个习惯坚持一个月效果比盲目刷一百道题要好得多。第三个阶段是模拟实战时间约一周到两周。找整块时间用牛客网的模拟笔试功能严格按90分钟限时做题。这能帮你适应考场节奏减少因为紧张导致的低级失误。我第一次模拟笔试时前面两道题花了太长时间后面两道题几乎没时间写经过几次模拟之后才学会合理分配时间。2. 题型拆解这些经典考点至今仍在考2.1 贪心看起来简单坑最多贪心算法的核心就一句话每一步都做当前看起来最优的选择期望最终得到全局最优解。难点在于你怎么确定贪心策略是对的很多贪心题你拍脑袋想出一个策略自己能举出的例子都能过一提交就错原因就是局部最优并不总能推出全局最优。我常用的验证方法有三个。第一尝试构造反例。如果找不到反例不能说明策略正确只是你可能还没找到。第二对于小数据范围可以用暴力搜索做对拍验证。随机生成多组小数据暴力枚举所有方案和贪心方案对比不一致就说明贪心策略有问题。这个方法非常实用笔试前建议熟练掌握。第三会证明。常见的证明手段有交换论证、归纳法、界相等。虽然笔试时不太可能写证明但会证明能帮你确认策略的正确性。腾讯的安置路灯就是一道非常典型的贪心题。还有一种常见的贪心变体是先排序再逐个处理比如纸牌游戏里两个人轮流从牌堆取牌每个人都取当前最大的一张证明方法就是直接排序后按索引累加即可。如果你对这类排序贪心的题目不熟建议集中刷一下经典的活动安排、区间覆盖问题腾讯的很多题目都是从这些模型变形来的。2.2 动态规划区分度的分水岭腾讯笔试里动态规划题通常放在中间靠后的位置用来区分候选人水平。DP题的核心套路可以拆成四步定义状态、写转移方程、确定初始化、确定遍历顺序。这四步每一步都有讲究。状态定义一般是你想求什么就设什么。比如构造回文要求最少删除多少个字符变成回文一个直接的状态定义就是dp[i][j]表示子串s[i:j1]变成回文最少需要删几个字符。转移的时候如果s[i]s[j]两端已经相等那结果就等于dp[i1][j-1]否则可以从删掉左边或删掉右边两个方向中选更小的那个再加1。这种区间DP的套路在字符串相关的题目里特别常见。初始化主要看边界。区间长度为1的时候已经是回文dp[i][i]0区间长度为2的时候两个字符相等则不需要删不等则删一个dp[i][i1]0或1。很多人写DP出错都是栽在初始化上建议每次写完先用长度为1和2的小例子手算一遍。遍历顺序常见有正着遍历、倒着遍历、按区间长度遍历。区间DP一般按区间长度从小到大遍历确保计算长区间时短区间已经算完。动态规划学习曲线较陡但一旦你掌握了这套固定流程大部分常见DP题都能应对。2.3 字符串与排序基础中的基础字符串处理题看起来不难但写起来很容易出小bug。腾讯2017年里字符移位就是一道典型的字符串题把一个字符串里的字母和字符重新排列要求所有小写字母排在大写字母前面并且同类字母保持原有的相对顺序。这种保持相对顺序的要求其实是在暗示你不能无脑排序而应该用稳定的处理方式最直接的办法就是开两个字符串分别拼接。排序类的题目考的不是排序算法本身而是你能否利用排序后的性质解决问题。有趣的数字就是这种题给定n个数求所有两两数对差值绝对值的最小值以及达到这个最小值的数对个数。排序之后相邻两个数的差值一定是所有差值中最小的候选所以只要检查相邻对即可这是典型的排序简化问题思路。2.4 数据结构栈、队列、堆的使用时机数据结构题在腾讯笔试里不一定单独出现但不代表不需要准备。栈常用于处理括号匹配、表达式求值、单调栈求下一个更大元素队列常用于BFS层级遍历和滑动窗口堆常用于TopK问题和合并有序链表。尤其是堆Java的PriorityQueue和Python的heapq在笔试里出场率很高建议熟练使用。还有一个容易被忽略的点是哈希表。很多看似要排序的题其实用哈希表加一次遍历就能解决。比如统计字符频率、查找重复元素、求两数之和都优先考虑哈希表。腾讯笔试的场景题里哈希表经常作为辅助工具出现比如统计每种牌的数量、统计任务出现次数掌握好这个数据结构能省下不少编码时间。3. 经典题实战从读题到AC3.1 安置路灯一道贪心证明的好题目题目描述回忆版小Q正在给一条长度为n的道路设计路灯安置方案。道路可以简化成一个字符串字符.表示这个位置需要照明X表示这个位置不需要照明。每个路灯可以照亮自己所在的位置以及左右相邻的两个位置问至少需要多少盏路灯才能照亮所有需要照明的区域。这道题我建议你先自己想一遍再看答案。思路很简单从左到右遍历字符串遇到第一个需要照明的.就在这个位置放一盏路灯然后跳过它后面的两个字符继续遍历。代码如下def min_lights(s): n len(s) i 0 count 0 while i n: if s[i] .: count 1 i 3 else: i 1 return count s .X..X.. print(min_lights(s))为什么这样贪心是对的关键在于路灯的照明范围是三格连续区间。当你从左边开始扫描遇到第一个需要照明的点这个点左边已经确认全部处理完毕为了覆盖它你必须在这三格中的某个位置放一盏路灯。到底放在哪里最优如果放在当前点覆盖范围是i-1、i、i1其中i-1已经不用管了如果放在当前点的右边一格覆盖范围是i、i1、i2比前者多往后覆盖了一格。所以放在当前点的右边一格不劣于放在当前点甚至更好。这也是贪心策略可以放心向右跳的原因。实现的时候有一个细节要注意先把字符串转换成list因为Python字符串是不可变对象虽然这道题不需要修改字符串但如果你是模拟放置路灯后把X替换为别的字符就会遇到这个问题。另外如果字符串里有空格或换行符读取时要strip干净避免把换行符当成一个有效字符。这类题的变形也值得留意。比如LeetCode上的监控二叉树、经典的灌溉花园问题本质都是区间覆盖的贪心换了一层壳而已。你在刷题时如果遇到类似的模型建议放在一起总结形成自己的贪心模型库。3.2 构造回文最长公共子序列的巧妙变形题目描述回忆版给定一个字符串s你可以删除其中的任意字符问最少删除多少个字符可以使得剩下的字符串是一个回文串。例如abca删除b或者c之后得到aca或aba都是回文串最少删除1个字符。这道题的直接思路是区间DP但更优雅的做法是把它转化为最长公共子序列问题。回文串的特点是从左往右读和从右往左读是一样的那我们把原串s和它的反转串rev(s)求最长公共子序列这个LCS的长度就是原串中能保留下来构成回文的最长字符数。答案就是原串长度减去这个LCS长度。为什么这样成立解释一下。假设原串s里有一个回文子序列那么它从左往右读和从右往左读是一样的在反转串rev(s)里也一定以同样的顺序出现因此这个回文子序列一定是s和rev(s)的公共子序列。反过来s和rev(s)的任意公共子序列实际上就是原串里一个正着读和反着读都能匹配的字符序列它天然是一个回文序列。所以最大保留长度就是LCS长度。LCS的经典DP代码如下def min_deletions_to_palindrome(s): 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] print(min_deletions_to_palindrome(abca))时间和空间复杂度都是O(n^2)。当n在1000以内时这个方案完全可行如果n到了10^5O(n^2)的二维数组会直接爆内存需要换思路。实际笔试里字符串长度通常在1000以内所以这个解法是足够的。代码里有一个容易错的地方dp数组我开的是(n1)x(n1)多出一行一列作为空串的边界。遍历时s[i-1]和rev[j-1]的下标要对应好这个细节写错会导致结果偏差。还有Python里字符串反转用s[::-1]是最简洁的写法不需要写循环。这道题的变形也非常多。比如最少插入多少次能变成回文答案等于字符串长度减去最长回文子序列长度和这道题一模一样。还有分割回文串的最小切割次数则要用到另一个DP思路。把这些变形放在一起比较着学收获会大很多。3.3 小Q的歌单组合计数与背包思想的结合题目描述回忆版小Q有X首长度为A的不同的歌以及Y首长度为B的不同的歌。现在想从这些歌里选出若干首组成一个总长度恰好为K的歌单每首歌最多选一次。问有多少种不同的歌单组合方式结果对10^97取模。例如X3A2Y2B3K6时可以选3首长度为2的歌也可以选2首长度为3的歌还可以选0首长度为2的加2首长度为3的等下0首A和2首B是2*36但K是6这也可以所以答案要仔细枚举。解题的核心思路是枚举从A类歌曲里选i首然后看需要从B类歌曲里选j首使得iA jB K。如果满足条件那么贡献的组合数是C(X, i) * C(Y, j)把所有满足条件的贡献累加就是答案。先看第一个难点怎么快速计算组合数C(n, k)。n和k最大不超过100所以可以直接用递推公式开一个二维数组按杨辉三角的方式填表。注意C(n,0)C(n,n)1C(n,k)C(n-1,k)C(n-1,k-1)。Python代码这样写MOD 10**9 7 def build_comb(n): c [[0] * (n 1) for _ in range(n 1)] for i in range(n 1): c[i][0] c[i][i] 1 for j in range(1, i): c[i][j] (c[i - 1][j - 1] c[i - 1][j]) % MOD return c def count_song_pairs(X, A, Y, B, K): total max(X, Y) c build_comb(total) ans 0 for i in range(X 1): if i * A K: break remaining K - i * A if remaining % B 0: j remaining // B if 0 j Y: ans (ans c[X][i] * c[Y][j]) % MOD return ans print(count_song_pairs(3, 2, 2, 3, 6))这个做法的时间复杂度是O(X*Y)在X和Y不超过100的情况下完全没有压力。如果X和Y放大到10^5就不能用这个枚举方式了需要用到生成函数或者更高级的数学工具笔试很少考到那么深。容易踩的坑有三个。第一组合数取模。因为结果对10^97取模所以组合数递推的时候每一步都要模乘积也要模否则中途溢出会得到错误结果。第二边界判断。j remaining // B之后必须判断j是否在0到Y之间不能只判断整除。第三i的上界。当iA已经大于K时后面的i只会让remaining变成负数可以直接break但要注意别漏掉iAK正好整除的情况。这道题背后的模型其实是有限数量物品的恰好凑数问题和背包问题的思路很像区别在于这里是组合计数而不是最优值。如果你把这道题和经典的硬币凑数放一起对比会发现转移思想是相通的只是约束条件不同。3.4 有趣的数字排序细节与重复元素统计题目描述回忆版给定n个整数你需要求所有数字两两之间的差的绝对值中最小值是多少并且求出差值的绝对值等于这个最小值的数对有多少个。比如输入[1, 3, 1, 3]两两差值最小是0有两对(1,1)和(3,3)。如果输入[1, 5, 3]差的最小值是2对应(1,3)和(3,5)共两对。这道题本身不难但考察了很多细节。首先想清楚未排序的数组中任意两个数的差值最小一定发生在排序后相邻的两个数之间。所以先排序然后遍历一遍计算所有相邻差值找出最小值。这个推理很朴素但能帮我们避免O(n^2)的暴力循环。关键问题在于差值最小值出现了几次。分两种情况。第一种数组里有重复数字。那么最小差值一定是0因为两个相等的数差值就是0。此时需要统计每个数字出现的次数cnt对每个出现次数大于等于2的数字它对答案的贡献是C(cnt, 2)cnt*(cnt-1)/2。第二种数组里没有重复数字。最小差值大于0只要再遍历一遍排序后的数组统计相邻差等于最小差值的对数即可。对应的Python代码def find_min_diff_pairs(arr): arr.sort() n len(arr) min_diff float(inf) for i in range(1, n): min_diff min(min_diff, arr[i] - arr[i - 1]) if min_diff 0: from collections import Counter cnt Counter(arr) ans 0 for v in cnt.values(): if v 2: ans v * (v - 1) // 2 return 0, ans else: ans 0 for i in range(1, n): if arr[i] - arr[i - 1] min_diff: ans 1 return min_diff, ans arr [1, 3, 1, 3] print(find_min_diff_pairs(arr))这里有几个容易出错的地方。第一排序后的重复数字是相邻的所以有没有重复数字可以不用Counter而是遍历排序后的数组看是否有相邻相等。但用Counter更直观也不会错。第二当min_diff为0时你不能再按相邻差去数因为相邻相等的数字会有很多组比如[1,1,1]相邻差为0出现了2次但正确的结果应该是C(3,2)3对所以必须按出现次数组合数计算。第三差值的数据类型。输入可能是负数排序后相邻差可能是负数不排序后大数减小数差值一定是非负的这点不用担心。这道题考察的就是排序分类讨论的能力放在笔试靠前的位置很有迷惑性很多人第一反应是双重循环复杂度是O(n^2)当n10^5时直接超时。你能想到排序后只看相邻就已经赢了大部分人。4. 笔试现场避坑指南4.1 牛客网OJ的输入输出陷阱很多人在本地IDE里代码跑得好好的一提交就报错问题往往出在输入输出上。牛客网的标准输入格式是多行文本你要用input()或sys.stdin.readline()逐行读取。我的习惯是统一用sys.stdinimport sys def main(): data sys.stdin.read().strip().split() if not data: return # 假设第一个数是n后面n个数是数组 n int(data[0]) arr list(map(int, data[1:1n])) # 处理... print(result) if __name__ __main__: main()用sys.stdin.read()一次性读完再按空白字符分割可以避免逐行读取时因为空行或者行尾空格导致的解析错误。尤其适合第一行一个整数n第二行n个整数这种格式。还有一个隐藏问题有些题目会包含多组测试数据输入格式里写了多组输入每组占两行之类的要求。这时候如果你只按一组读就会只通过部分用例。解决方法是循环直到读不到数据为止。逐行读时用while True加try/except EOFError来判断或者用sys.stdin.read().split()然后按长度切分都能处理多组数据。4.2 超时的常见原因和优化手段笔试出现超时最常见的三个原因一是算法复杂度太高二是Python自身运行速度较慢三是代码里有隐藏的O(n^2)操作。第一个原因前面说过要从数据范围推断该用什么算法。第二个原因如果你平时用Python刷题在n达到10^5甚至10^6时建议尽量用sys.stdin、sys.stdout把函数内的局部变量尽量局部化避免在循环里反复调用全局函数。第三个原因最隐蔽。比如你在遍历时反复用list.index()查找元素每次查找都是O(n)整体就可能变成O(n^2)。再比如你在循环里用字符串拼接s charPython的字符串是不可变对象每次拼接都会生成新字符串复杂度是O(len(s))如果要拼n次总复杂度就是O(n^2)。正确的做法是用列表收集再.join()或者直接用列表存储。还有一个经典的优化手段是空间换时间。比如有趣的数字这道题如果数组没有排序要用哈希表记录每个元素出现的位置而不是每次都用index()去查。贪心和DP的问题往往也可以用哈希表、前缀和、差分数组等技巧把复杂度降下来。笔试时如果觉得当前方案可能会超时先冷静想一下能否用额外的空间减少一层循环这招在80%的场景下都有效。4.3 提交前自查清单避免无谓的丢分做完一道题提交之前我强烈建议你按这个清单检查一遍这些教训都是我当年反复踩过的。第一取模。题目要求对10^97取模时别忘了每一步乘法或加法之后都取模尤其是组合数、快速幂、乘法累加类的题目。第二数据类型。Python的int不溢出但如果你用C/Javalong long和int的区别会直接影响结果。即使你用Python也要注意除法是整数除法//和/别用混。第三数组越界。遍历时如果涉及arr[i-1]或者访问dp[i][j-1]一定要确认i和j的起点避免访问到负索引。Python的负索引不会报错但会得到完全错误的结果这点比越界崩溃更坑。第四空数据。输入可能为0个元素或者长度为0的字符串你的代码是否能在不报错的情况下输出约定结果正常情况下输出0但要有这个意识。第五输出格式。是输出一行还是多行有没有要求末尾不能有多余空格如果是多行输出用列表收集结果最后统一打印更稳妥。还有一个容易被忽视的问题递归深度。Python默认递归深度是1000如果题目要求用DFS且深度可能超过1000直接递归会报RecursionError。可以考虑改成显式栈的迭代写法或者在代码开头加sys.setrecursionlimit(1 25)。但说实话笔试现场临时改递归深度有风险最好一开始就用迭代式DFS。笔试中还有一个实用的小技巧当你对一道题没有完整思路时先把暴力解法写出来保证过掉小数据范围的用例拿到部分分数。很多时候部分通过的分数比空着不写要好得多。暴力解法的思路往往也能帮你理清题目的模型写着写着就想到了优化方案。写在最后的一点个人经验我当年准备腾讯笔试的时候最深刻的体会是网上能找到的题目回忆版很多但你光看答案是没有用的必须自己动手写一遍跑通再总结。2017年这批题之所以经典是因为它们考察的算法模型非常基础贪心、DP、组合计数、排序细节这些能力不会因为年份增加而贬值。准备校招与其追逐新题怪题不如把每一道经典题背后的模型吃透。这些年我带过不少候选人凡是把基础模型学扎实的笔试成绩普遍不会差。这份复习提纲如果对你有帮助刷题过程中卡住了也可以按题号来和我交流。祝大家都能拿下心仪的offer。