前两天帮学弟复盘校招真题翻到一套很有代表性的题京东2016研发工程师在线笔试编程题。虽然已经过去好几年但这套题的出题风格、考察重心和现在一线大厂的校招笔试几乎一脉相承。今天把这套题里流传最广、含金量最高的几道完整复盘一遍从题意拆解、推导过程、参考代码到易错点一次讲透。无论是准备校招的应届生还是想系统补算法基础的同学都值得花半小时把这几个典型问题过一遍。我当时自己刷这套题时第一感觉是“不难但处处是坑”。它不像ACM那样考复杂的图论或高级数据结构更多是在考你对基础算法的理解深度以及能不能把一道看似生活化的题目快速抽象成标准的算法模型。这种能力恰恰是面试官最看重的。1. 从真题看京东2016校招编程题的考察逻辑1.1 题量、难度与核心风格这套题的常见流传版本包含四道左右整体时间一般是两个小时。题目难度呈阶梯状一道二维动态规划、一道倒推数学题、一道概率期望题、一道序列转化题。没有偏题怪题都在经典算法框架内但每道题都会在某个地方给你设个小障碍比如边界条件、整除判定、浮点精度、题意理解。这种风格其实很有代表性。大厂校招笔试的核心目的不是筛出“刷题量最大的人”而是筛掉三类人一类是连基础状态转移都写不利索的一类是读题不仔细上来就乱写的还有一类是只会套模板、稍微变个场景就认不出来的。你看这套题每道都把经典模型包了一层“生活外壳”本质还是在考模型识别能力。1.2 校招笔试想筛什么样的人我见过不少同学刷题时喜欢专攻难题、冷门题结果真到笔试发现考的全是“朴素算法”。京东这套题就是个很好的提醒笔试拼的不是你会不会红黑树而是你能不能把 8x8 网格、分苹果、集齐小球这类生活场景快速翻译成 DP、倒推、期望公式。另外这套题对“代码落地能力”的考察很直接。思路想得再好边界处理错一个下标或者漏了 long long照样过不了样例。很多候选人挂在一些非常基础的细节上这不是智商问题是平时写代码习惯不好。下面我逐题拆解把每道题的推导过程和容易踩的坑都说清楚。2. 年终奖8x8棋盘上的经典动态规划2.1 题目原意与考场第一反应题目描述大概是有一个 8x8 的棋盘每个格子里放了一定价值的礼物你从左上角出发每次只能向右或向下移动一格走到右下角问沿途能拿到礼物的最大总价值。这题放到现在看就是标准的“二维网格最小路径和”变体只是把“最小和”换成了“最大价值”。但当年考场上有不少人第一反应是深搜。8x8 的棋盘用 DFS 也可以跑因为路径数量是 C(14,7) 级别大约几千条不至于超时。可如果面试官把棋盘改成 50x50 甚至 100x100DFS 直接爆炸。所以这道题真正的考点是你能不能第一时间想到动态规划而不是用搜索硬刚。2.2 状态设计和转移方程怎么推动态规划最核心的一步是定义状态。这里设 dp[i][j] 表示从起点 (0,0) 走到格子 (i,j) 时能获得的最大礼物总价值。因为每次只能向右或向下走所以想到达 (i,j)上一步只能是左边格子 (i,j-1) 或上面格子 (i-1,j)。我们只需要取这两条路中价值更大的那条再加上当前格子的礼物的价值dp[i][j] max(dp[i-1][j], dp[i][j-1]) gift[i][j]为什么要这样定义而不定义成“从终点倒推”因为正向定义更符合直觉而且边界条件很好写。第一行格子只能一直向右走所以 dp[0][j] 就等于从起点一路向右累加第一列格子只能一直向下走同理。只要把这两条边界先算好中间格子就能按顺序从左上到右下填满。用生活化的例子理解想象你在一个小区里每个路口都放了一个红包你只能往东或往南走想从小区东北门走到西南门。你在某个路口能拿到的最大红包数一定是从北边来的路和从西边来的路中累计红包更多的那个路口再加上这个路口的红包。这个思路非常适合在面试时讲给面试官听。2.3 参考实现与易错点下面给出一个可以直接跑的 C 版本#include bits/stdc.h using namespace std; int main() { vectorvectorint gift(8, vectorint(8)); for (int i 0; i 8; i) { for (int j 0; j 8; j) { cin gift[i][j]; } } vectorvectorint dp(8, vectorint(8, 0)); dp[0][0] gift[0][0]; // 第一列只能从上边来 for (int i 1; i 8; i) { dp[i][0] dp[i-1][0] gift[i][0]; } // 第一行只能从左边来 for (int j 1; j 8; j) { dp[0][j] dp[0][j-1] gift[0][j]; } for (int i 1; i 8; i) { for (int j 1; j 8; j) { dp[i][j] max(dp[i-1][j], dp[i][j-1]) gift[i][j]; } } cout dp[7][7] endl; return 0; }易错点有三处边界初始化顺序先赋值 dp[0][0] gift[0][0]再处理第一行和第一列不然 dp[0][0] 会被重复加一次。输入可能不是严格的 8x8题目说了是 8x8不要自己写成动态读入行数然后搞出越界。如果你是给面试官讲思路最好顺便说出状态转移的“无后效性”——当前格子的最优值只依赖左边和上边和历史路径怎么走来的无关。这句话能体现你对 DP 本质的理解而不是单纯背模板。这道题还有一个进阶问法如果棋盘变成 m x n并且某些格子有障碍不能走状态转移要怎么改其实就是初始化障碍格子的 dp 值为一个极小值遇到障碍直接跳过。理解了基础题这些变形都很自然。3. 分苹果倒推思维与整除判断3.1 题意陷阱不是简单整除这道题的描述比较绕大意是农场主有一堆苹果要分给 n 头牛。第一头牛来的时候把苹果分成 n 堆发现多了一个就把多的那个扔掉然后拿走其中一堆。第二头牛来的时候对剩下的苹果做同样操作也把剩下的分成 n 堆、多一个扔掉、拿走一堆。依此类推。问开始的时候至少有多少个苹果。很多人第一次看到这题会从前往后枚举初始苹果数然后每头牛操作一次检查是否满足条件。这个思路本身没错但效率不高而且很容易漏掉“最后一头牛操作完后可能还剩下一些苹果”这个隐含条件。更严重的问题是如果你枚举初始值判定条件一旦写错整个程序就废了。正解是从后往前倒推。这题的数学结构决定了倒推比正推清晰得多。3.2 从后往前倒推的数学依据设第 i 头牛来之前有 s[i-1] 个苹果操作后剩下 s[i] 个。根据题意操作前数量 s[i-1] 必须满足 s[i-1] % n 1因为“分成 n 堆多一个”。操作后剩余 s[i] (s[i-1] - 1) / n * (n - 1)。反推就是s[i-1] s[i] / (n - 1) * n 1这个反推公式要求 s[i] 必须能被 n-1 整除否则 s[i-1] 不是整数说明当前这条倒推路径不合法。所以算法就清晰了枚举最后一头牛操作后的剩余量 lastlast 从 n-1 的倍数开始往上枚举因为最后一次操作后剩余量必然是 n-1 的倍数然后按照上面的公式倒推 n 次。如果每步都满足整除条件就说明存在一条合法路径此时算出的 s[0] 就是初始苹果数。取所有合法结果中最小的一个即可。3.3 参考实现与整除判断#include bits/stdc.h using namespace std; long long solve(int n) { long long last n - 1; // 最后一头牛操作后的剩余量 while (true) { long long cur last; bool ok true; // 倒推 n 次从最后一头牛推到第一头牛操作前 for (int i 0; i n; i) { if (cur % (n - 1) ! 0) { ok false; break; } cur cur / (n - 1) * n 1; } if (ok) return cur; last n - 1; // 枚举下一个 n-1 的倍数 } } int main() { int n; while (cin n) { cout solve(n) endl; } return 0; }注意这里倒推的是 n 次不是 n-1 次。因为要从“最后一头牛操作后”推到“第一头牛操作前”中间跨越了 n 次操作。我当年写的时候就是这里少循环了一次样例 n3 怎么都算不对。以 n3 为例验证一下结果应该是 25最后一头牛操作后 last 2倒推第三次cur22%20cur 2/2*31 4这是第三头牛操作前倒推第二次4%20cur 4/2*31 7这是第二头牛操作前倒推第一次7%2!0失败。继续枚举 last 4第三次4%20cur 4/2*31 7第二次7%2!0失败。继续枚举 last 8第三次8%20cur 13第二次13%2!0失败。直到 last 枚举到某个值比如能一路整除上去才能得到合法初始苹果数。这个过程的规模其实很小n 一般不超过几十枚举很快。这道题真正的坑在 long long。n 稍大一点倒推出来的数会指数级增长int 直接溢出。笔试时看到“至少多少个苹果”这种题第一反应就应该上 long long尤其是涉及乘法的时候。4. 抛小球优惠券收集者问题4.1 期望线性分解题目大意是箱子里有 n 种颜色的小球每种颜色各一个。每次随机从箱子里摸一个球记录颜色后再放回。问摸多少次才能集齐所有 n 种颜色求次数的期望。这题在概率论里有个经典名字叫“优惠券收集者问题”。很多人一看“期望”两个字就发怵其实它的推导非常优雅。关键在于把等待过程拆成 n 个阶段。假设当前已经集齐了 i 种颜色那么下一次摸球能摸到新颜色的概率是p (n - i) / n因为箱子里有 n 个球其中新颜色有 n-i 个。摸到新颜色之前的尝试次数服从几何分布几何分布的期望是 1/p所以这个阶段需要的期望次数是n / (n - i)从 i0 开始到 in-1 结束把每个阶段的期望次数加起来E n/n n/(n-1) n/(n-2) ... n/1 n * (1 1/2 1/3 ... 1/n)整个过程就像集卡一开始随便摸一张都是新卡后面重复卡越来越多每集一张新卡平均要拆包的次数也越来越多。所以期望次数不是 n而是 n 乘以一个调和级数也就是大约 n * ln(n)。4.2 实现细节与精度代码本身很短#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { double ans 0.0; for (int i 1; i n; i) { ans 1.0 / i; } ans * n; // 四舍五入输出整数 printf(%.0f\n, ans); } return 0; }几个容易出问题的地方循环为什么从 1 加到 n因为 E n * Σ(1/i)i1 到 n。如果你推公式时从 n/n 开始那就是 in 对应第一项别搞反了。浮点精度n 如果很大直接累加 1.0/i 会有一点误差但对这种题目影响不大。如果实在担心可以用 long double输出时再转。输出格式题目一般要求四舍五入到整数。printf(%.0f) 自带四舍五入比 (int)(ans0.5) 更稳妥后者负数的表现会有问题但这里结果一定是正数两者都可以。这题如果你只是背了“优惠券收集者公式”很容易在推导环节露馅。面试时建议把“几何分布期望 1/p”这个关键点讲出来面试官一般就会点头放你过。这也说明了基础概率论的重要性校招笔试里概率题不算多但出了就是送分题前提是你要真懂而不是死记。5. 士兵队列移动次数背后的LIS转化5.1 题目版本说明与问题转化这题在网上的流传版本很多原题描述比较短导致大家看到的内容不太一样。最常见的一个版本是n 个士兵排成一队每个士兵身上有一个编号编号是 1 到 n 的一个排列。现在你可以执行一种操作把任意一个士兵从队伍里拿出来再插入到任意位置。问最少需要多少次操作能让整个队伍按编号从小到大排列。这个问题的关键是发现“不动的士兵”之间的关系。如果一个士兵不需要被移动那么这些士兵在最终序列中的相对顺序必须和在原队伍中的相对顺序一致并且他们的编号必须严格递增。否则无论你怎么插入其他人都无法形成正确排序。而我们需要让“不动的士兵”数量尽可能多。因此这个问题等价于求原序列的“最长上升子序列”长度 LIS答案就是 n - LIS。为什么是 n - LIS因为保留 LIS 里的那些士兵不动剩下的 n - LIS 个士兵每个最多操作一次把它们依次插到正确位置即可。比如序列 [3,1,2,4]LIS 是 [1,2,4] 长度 3只需要把 3 拿出来放到 4 后面一次操作就排序完成。5.2 LIS两种实现先看 O(n^2) 的经典 DP#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint dp(n, 1); int lis 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } lis max(lis, dp[i]); } cout n - lis endl; } return 0; }dp[i] 表示以第 i 个士兵结尾的最长上升子序列长度。每个 dp[i] 初始为 1表示自己单独成一个序列。然后扫描前面所有 j如果 a[j] a[i]就可以把 a[i] 接到以 a[j] 结尾的序列后面长度加 1。如果 n 比较大比如 1e5O(n^2) 会超时需要用 O(n log n) 的贪心 二分#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint tails; for (int x : a) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } cout n - (int)tails.size() endl; } return 0; }这个实现里tails 数组维护的是“长度为 len 的上升子序列中最小可能的末尾值”。lower_bound 找到第一个不小于 x 的位置并替换掉本质上是让每个长度的末尾值尽可能小从而给后续元素留出更多增长空间。面试时能写出这个版本会很加分。5.3 报数出列变体简述如果你看到的版本是“士兵从左到右报数报到奇数的出列剩下的人重新从 1 开始报数问最后剩下的人原来在哪个位置”那解法完全不同。这个版本的规律是最后剩下的位置是不超过 n 的最大 2 的幂。比如 n9最后剩下的是第 8 位。考场上先确认题目问的是什么再动手写别看到“士兵队列”四个字就直接套 LIS。这道题给我们的启发很多“最少操作次数”类的问题最后都会转化成“找最长一个不需要动的结构”。这种逆向思维在校招笔试里反复出现值得专门练一练。6. 笔试实战中的通用策略与避坑经验6.1 拿到题先花5分钟做“题意等价转化”你会发现上面几道题都有一个共同特点表面是生活场景内核是经典模型。年终奖是网格 DP分苹果是倒推数学抛小球是概率期望士兵队列是 LIS。 所以拿到题目后不要急着敲代码先在草稿纸上把题目改写成你熟悉的算法问题。这一步看起来浪费时间实际上能帮你避免大量无效代码。比如分苹果如果你不先做数学推导直接写一个从 1 开始枚举初始苹果数的暴力程序也能出结果但速度慢、易错。而一旦你意识到“这题要倒推”代码逻辑会变得非常清晰。这就是校招笔试和平时刷题最大的区别平时你可以边想边写笔试必须先在脑内建模再动手。6.2 在线评测的输入输出与边界在线笔试最常见的问题不是算法不会而是输入输出处理出错。这套题的评测环境一般支持多组测试数据所以读入用 while(cin n) 是最稳的写法不要只读一组就结束。我还整理了一个高频失分点对照表失分点典型场景应对方案类型溢出分苹果倒推乘法涉及乘法一律用 long long数组越界年终奖 dp[0][j]先把边界初始化写好再循环浮点误差抛小球的 1.0/i 累加用 double 或 long double输出时四舍五入读题不仔细士兵队列版本混淆先确认“移动”还是“报数出列”循环次数错误分苹果倒推 n 次写成 n-1 次拿小样例手推一遍另外代码写完一定要自己代入样例跑一遍。很多同学写完直接提交结果样例都不对白扣分。样例通过后再测几组边界值比如 n1、n2 这种极端情况往往能提前发现隐藏 bug。6.3 刷题准备建议如果你想针对大厂校招笔试做系统准备我给三个建议第一按 tag 刷题别东一榔头西一棒子。动态规划、贪心、数学推导、字符串处理、简单图论每个大类至少刷 30 道经典题。京东这套题里的年终奖、士兵队列都属于“动态规划”大类你刷多了自然会形成条件反射。第二每道真题至少做三遍。第一遍限时模拟考场写不出来没关系第二遍对照题解把思路吃透然后合上书重新写第三遍隔一周再写检验自己是不是真的记住了。这个方法看起来很笨但非常有效。第三刷题时多问自己“这题换个场景我还认识吗”。比如网格 DP换个说法叫“机器人走迷宫”“农民收庄稼”本质都一样。你要训练的是识别能力而不是背题能力。京东这套题完美诠释了什么叫“换汤不换药”。6.4 个人体会说实话这几年我再看这套题依然觉得它值得推荐给每个准备校招的人。它没有为难人但每道题都能让你清晰地看到自己的短板状态定义是否熟练、数学推导是否严谨、边界处理是否细致、代码风格是否干净。这些能力恰恰是研发工程师日常工作中最需要的。我自己当年刷题时有个习惯每道题写完后会在题目标注“这题考的是什么模型”“我卡在了哪个环节”。复盘比刷题更重要因为你刷 100 道题如果不复盘可能只是把 100 道题都做了一遍但如果你认真复盘 10 道题把这 10 道题的模型都吃透遇到变体也能轻松应对。最后再分享一个小技巧做题时如果卡了 20 分钟还没有思路果断跳过先做后面的不要在一道题上死磕。笔试时间有限先把能拿的分拿到最后再回头啃硬骨头。这套逻辑听起来简单但考场上有太多人因为一道题卡住导致后面的送分题都来不及写。稳扎稳打才是校招笔试的正确打开方式。