腾讯2018春招技术类编程题汇总这份题库我到现在还会翻出来看。原因很简单它不像很多压轴竞赛题那样劝退但又能把二分、贪心、区间DP、组合计数这几个校招最高频的考点都考到位题量不大难度梯度合理非常适合拿来摸底和找手感。无论你是准备腾讯的正式批还是想用一套高质量题目检验自己的算法底子这十几道题都值得认真过一遍。这套题最大的价值在于“用得上”每道题背后都是一个可以迁移到别家笔试的解题模型。我把当年考过的核心题目按考点拆开结合我自己的实现过程把解题思路、代码细节、容易踩的坑全部过一遍。即便你不是应届生把这些模型吃透应付大多数公司的线上笔试也够用了。1. 2018腾讯春招编程题的整体设计思路1.1 题型分布与考点盘点2018年腾讯春招技术类笔试的编程题部分整体风格是“短题干、多约束、重边界”。题目往往用一个小故事包装去掉包装后就是个经典算法模型。这一点和LeetCode的风格有点像但比LeetCode更强调“能不能在短时间内想清楚数据范围和边界条件”。把这批题目过一遍考点可以归成这么几类题目核心考点推荐解法难度贪吃的小Q二分答案、模拟二分第一天吃的数量check函数按天累加中等小Q的歌单组合计数、预处理枚举A类歌数量组合数相乘累加中等偏易纸牌游戏区间DP、博弈思想dp[i][j]表示区间内先手最大得分中等安排机器贪心、排序、双指针时间降序处理任务等级用计数数组匹配中等偏难你会发现这些题目没有特别冷门的算法也没有变态的数学构造题。它考的恰恰是校招生最该有的基本功二分边界会不会写、组合数取模会不会预处理、区间DP的状态转移能不能想清楚、贪心策略能不能证明。1.2 为什么这套题值得反复刷我开始带新人之后经常用这套题当“面试前置热身”。原因有三个。第一题目覆盖面广但不偏门。二分、DP、贪心、组合计数这四样几乎是所有大厂笔试的通用考点。把这套题刷透等于给算法基础做了一次系统体检哪块薄弱一目了然。第二题目难度适合“限时训练”。每道题单独拿出来给到30到40分钟正好模拟面试笔试的节奏。如果你能在45分钟内AC三道以上说明基本功已经达到一个比较稳的水平。第三题目背后的坑非常典型。比如二分边界、组合数取模、long long溢出、区间DP的循环顺序这些坑在真实笔试里每年都有人踩。这套题的设置恰好把这些细节暴露得很充分刷一遍能积累不少避坑经验。2. 核心题目解析与解题思路2.1 贪吃的小Q二分答案的经典模板题目大概是这样的小Q的父母出差N天走之前给他留了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天的一半且每天至少吃1块但他又不想在父母回来之前断粮。问小Q第一天最多能吃多少块巧克力。这道题的突破口在于“第一天吃的数量”和“能否撑过N天”之间是单调关系第一天吃越多后面每天的消耗也越高越容易断粮。所以可以二分答案枚举第一天的数量x然后check一下按照规则能不能撑满N天。check函数的写法是核心我贴一下我常用的实现bool check(int x, int n, int m) { long long total 0; int cur x; for (int i 0; i n; i) { total cur; if (total m) return false; cur (cur 1) / 2; // 向上取整的一半 if (cur 1) { // 从第 i1 天起到最后每天都是1块 total (n - i - 1); return total m; } } return total m; }有几个细节必须强调。第一cur (cur 1) / 2这个写法等价于向上取整因为巧克力数量必须是整数。第二一旦cur变成1后面每天都是1块后续可以直接用乘法算完不要再进循环里模拟否则容易在n很大的时候超时。第三累加值total必须用long longM的上限如果给到2^31int在累加过程中可能溢出。二分部分比较简单int l 1, r m, ans 1; while (l r) { int mid (l r) / 2; if (check(mid, n, m)) { ans mid; l mid 1; } else { r mid - 1; } } cout ans endl;这里注意先判断check成功再更新ans保证ans始终是可行解中的最大值。我第一次做这道题的时候犯了个低级错误check里没有处理cur1后的尾巴导致n很大的时候TLE。后来才意识到这个优化不只是锦上添花而是这道题的一个隐藏考点数据一大不加这个优化就可能超时。2.2 小Q的歌单组合计数与取模陷阱第二道经典题是歌单问题小Q有X首长度为A的歌和Y首长度为B的歌现在要从里面选一些歌组成一个总长度恰好为K的歌单每首歌只能用一次问一共有多少种组合方案结果对1e97取模。这道题的核心是枚举。假设选i首长度为A的歌剩余长度K-iA必须能被B整除而且剩余部分对应的歌数量不能超过Y。满足条件时方案数就是C(X, i) * C(Y, j)其中j (K - iA) / B。实现上需要预处理组合数。C我一般用二维数组杨辉三角因为这道题的数据范围通常不会太大n最多几百到一千const int MOD 1e9 7; const int MAXN 105; long long C[MAXN][MAXN]; void init() { for (int i 0; i MAXN; i) { C[i][0] C[i][i] 1; for (int j 1; j i; j) { C[i][j] (C[i-1][j-1] C[i-1][j]) % MOD; } } }然后枚举ilong long ans 0; for (int i 0; i X; i) { if (i * A K) break; int remain K - i * A; if (remain % B ! 0) continue; int j remain / B; if (j Y) continue; ans (ans C[X][i] * C[Y][j]) % MOD; } cout ans endl;易错点主要有两个。第一C数组类型用long long但乘完之后要立刻取模否则两个大数相乘可能溢出。第二C[i][0]和C[i][i]都要初始化为1不初始化或者漏掉一个边界用例就会错。另外i的枚举可以提前剪枝一旦i * A K就能break这个优化虽然小但能让逻辑更清晰。2.3 纸牌游戏区间DP的入门佳例题目是经典的取纸牌问题N张纸牌排成一排两个人轮流从最左端或最右端取走一张牌都采取最优策略问先手最终能拿到的最大分数总和。这道题我当初做的版本要求输出先手最多能拿到多少分。可以用区间DP设dp[i][j]表示在区间[i, j]内当前玩家能拿到的最大分数。转移的时候当前玩家要么拿左端的牌要么拿右端的牌拿完之后剩下的区间交给对手而对手也会最优地拿。状态转移方程dp[i][j] max( a[i] sum(i1, j) - dp[i1][j], a[j] sum(i, j-1) - dp[i][j-1] )这里的sum(i1, j) - dp[i1][j]的含义是当前玩家拿走a[i]后剩余区间[i1, j]在“最优策略下”对手会拿走dp[i1][j]剩下的sum(i1, j) - dp[i1][j]就是当前玩家后续还能拿到的分数。实现时先预处理前缀和数组方便O(1)求区间和vectorint a(n1), pre(n1, 0); for (int i 1; i n; i) pre[i] pre[i-1] a[i]; vectorvectorint dp(n2, vectorint(n2, 0)); for (int len 1; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; int sumL pre[j] - pre[i]; // (i1)到j的和 int sumR pre[j-1] - pre[i-1]; // i到(j-1)的和 dp[i][j] max(a[i] sumL - dp[i1][j], a[j] sumR - dp[i][j-1]); } } cout dp[1][n] endl;关键点在于区间长度从小往大枚举确保dp[i1][j]和dp[i][j-1]已经算出来。这个循环顺序在二维DP里特别容易写反一旦反了结果全是错的。我第一次写的时候用左端点i从1到n、右端点j从i到n的顺序枚举结果子区间的dp还没算就用了。后来改成按len枚举才AC。2.4 安排机器贪心排序的细节处理这题是2018腾讯春招里区分度比较高的一道。题意大致是有n台机器和m个任务机器有运行时间和等级任务也有运行时间和等级。一台机器只能执行一个任务且机器的运行时间和等级都要不小于任务的要求。每完成一个任务收益是200 * 任务时间 3 * 任务等级。问最多能完成多少个任务最大收益是多少。首先要想明白贪心策略。因为收益中时间占比高达200倍所以优先处理时间长的任务对于同一个任务要选择满足要求的机器中等级最低的那台把高等级机器留给后面可能要求更高的任务。两个条件结合起来就是先按时间降序处理任务同时用双指针把时间足够的机器筛选出来再按等级匹配。我用一个等级计数数组来管理候选机器因为等级范围通常在0到100之间数组比multiset更轻量struct Item { int time, level; bool operator(const Item other) const { return time other.time; // 按时间降序 } }; vectorItem machines(n), tasks(m); sort(machines.begin(), machines.end()); sort(tasks.begin(), tasks.end()); vectorint cnt(105, 0); int machineIdx 0; long long ansCnt 0, ansProfit 0; for (auto task : tasks) { while (machineIdx n machines[machineIdx].time task.time) { cnt[machines[machineIdx].level]; machineIdx; } for (int lv task.level; lv 100; lv) { if (cnt[lv] 0) { cnt[lv]--; ansCnt; ansProfit 200LL * task.time 3LL * task.level; break; } } }这题有几个容易翻车的点。第一收益必须用long long因为任务时间和等级累计之后很容易超过int范围。第二机器按时间降序排序后用machineIdx维护所有时间足够的机器之后不要再回头处理之前跳过的机器。第三找等级匹配时要从任务等级往上找找到的第一个就是“刚刚好”的机器这样能最大化保留高等级机器。我有一次在真实笔试里遇到类似的题因为贪心顺序反了先按等级排导致收益少了一大截。后来复盘才意识到这种“时间权重远大于等级”的收益设计本身就是在暗示你要优先处理时间维度。3. 实操过程与稳定落地的刷题准备3.1 搭一个顺手的本地刷题环境刷题环境不需要太复杂但一定要顺手。我个人的习惯是本地用VS Code配C17再开一个Python3终端备用。C用来写对性能要求高的题Python用来快速验证思路。VS Code里我会装C/C扩展配置好Code Runner这样写完后一键运行。另外一定要开“编译输出”窗口方便看到编译错误。如果你用的是Mac或者Linux直接用g编译也完全没问题关键是调试断点要会用。环境这块有个容易被忽视的点在线笔试的编译器版本可能比较老C11/14是最稳妥的。像auto、vector初始化列表这些语法可以用但那些C17才有的特性比如if constexpr、string_view最好别在笔试里用。3.2 输入输出模板与调试技巧很多笔试的输入输出是不给文件名的直接标准输入输出。你要保证代码能在“一段测试数据到EOF或者第一行给一个T表示测试组数”这两种模式下都能快速切换。我常用的C模板长这样#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m) { // 单组数据逻辑 } return 0; }ios::sync_with_stdio(false)和cin.tie(nullptr)这两行可以显著提升cin的读取速度避免因为输入量过大导致TLE。不过要注意关掉同步之后不能混用scanf和cin。写二分这类题我强烈建议先写一个暴力算法再用随机数据对比验证。比如二分答案题可以先写一个从1到M逐个枚举的暴力版本然后用小数据随机对比一旦结果不一致马上就能定位是check函数的问题还是二分边界的问题。3.3 预判数据范围选对算法复杂度每道题拿到手先看数据范围。我用一个简单粗暴的判断标准n 10^5O(n log n)基本稳n 5000O(n^2)可以接受n 20可以直接上状态压缩n 10^9就要考虑数学公式或者二分答案。2018这套题里的二分答案题M可以达到10^9甚至更大但check函数里cur每轮除以2实际循环也就几十次所以完全不慌。而组合数的题数据范围通常限制在1000以内用O(n^2)预处理组合数就是最优解。不需要上逆元那套高级操作。有时候题目没有明确给数据范围这种时候要靠经验和试探。遇到一道看起来需要DP的题我会先写一个O(n^3)的版本跑一遍示例再根据实际执行时间判断要不要优化。做法虽笨但省时间。4. 常见问题与避坑实录4.1 笔试现场最容易翻车的三个点第一个是读题不清。2018这套题里的“贪吃的小Q”题目说“每天吃的巧克力数量不少于前一天的一半”很多人以为是向下取整实际上必须是向上取整。如果按向下取整实现样例可能还是过的但大数据一定挂。读题时遇到“不少于”“不超过”这类字眼一定要在草稿纸上把不等式写出来然后确认整除方向。第二个是long long溢出。纸牌游戏的分数、安排机器的收益、歌单的方案数这类涉及累加和乘法的题答案轻松超出int范围。我有个习惯只要题目里出现10^9级别的数值或者存在乘法运算先默认用long long。即使最后答案在int范围内多写一个LL后缀也不会扣分。第三个是单调栈和双指针类题目的死循环。安排机器这题如果machineIdx没有正确递增或者内层找等级的循环忘了break就很容易死循环。调试时最有效的方法是打印关键变量比如machineIdx、当前任务等级、cnt数组的状态。4.2 从2018春招题看腾讯笔试的演变趋势现在回头看2018年这批题能明显感觉到时代变化。那时候的编程题偏重“算法基本功”题目短、模型清晰、一眼能看出考什么。近几年的大厂笔试包括腾讯的越来越喜欢把算法题包装在具体业务场景里比如音视频处理、地图坐标转换、云资源调度这类话题。表面上是个业务题骨子里还是算法和数据结构。这意味着什么意味着你不能只背模板还得学会“翻译”。遇到一道很长的业务背景题先划掉无关描述把约束条件抽象成输入变量把目标抽象成最优化或计数问题。这个能力刷题是练得出来的尤其是通过2018年这种题干简洁的题目把模型基础打牢再去看长题干题目反而会轻松很多。4.3 刷完这套题之后的扩展路径如果你把这套题吃透了下一步我建议按专题刷而不是按题库刷。今天只练二分答案做三五道明天只练区间DP再做三五道。这种“短周期、重复刺激”的刷法比每天做一套完整试卷更容易形成肌肉记忆。专题之外每周再做一套限时的往年真题模拟真实的笔试环境。我一般用手机计时定50分钟到点就收写完的代码再回头分析看是卡在思路还是卡在实现细节。坚持一个月手感和自信都会明显提升。我个人在实际操作中最深的体会是刷题的数量不重要复盘的质量才重要。每道题做完不管AC没有都要给自己留一句总结比如“这道题的坑在于向上取整”“这类区间题用长度枚举最稳”。等到笔试前翻这些总结比重新刷一遍题库效率高得多。最后分享一个我一直在用的小技巧把容易出错的边界测试用例单独存在一个文件里比如二分题的n1, m1、DP题的n2、组合数的K0。每次写完代码先把这些边界用例跑一遍再跑示例。这个习惯帮我避开了至少一半的罚时。