京东2016研发工程师编程题二这套题放在今天看仍然很有嚼头。我当年准备校招时把这套题翻来覆去刷了三遍后来帮学弟学妹做笔试题复盘又把里面的典型题型重新梳理了一遍。这篇文章我会按当年笔试的常见考点把字符串模拟、动态规划、贪心这几类重点题型的解题思路和完整代码逐一拆开再聊聊笔试现场的时间分配和避坑经验。不管你是正在备战大厂校招还是单纯想把算法基础打牢这篇都能给你一些可落地的参考。1. 京东2016研发笔试里编程题二到底考什么1.1 从整套试卷看这道大题的定位京东2016年的研发工程师校招笔试整套卷子通常是选择题 编程题的组合。选择题覆盖操作系统、计算机网络、数据库、C/Java语言基础这些东西属于知识面考察编程题一般有两到三道放在卷尾。编程题一多数是热身题考的是最基本的循环、字符串处理编程题二就是整张卷子里区分度最高的一道它直接决定你笔试成绩能不能到面试门槛如果还有编程题三那往往是压轴题用来筛掉只会背模板的选手。我当时刷这套题的时候有个很直观的感受编程题二不是那种刷过原题就会没刷过就完蛋的偏题怪题它恰恰选的是最经典的算法模型但会套上一层业务场景的外壳。你以为它在考商品价格计算其实在考字符串处理你以为它在考物流配送其实在考区间贪心。这种出题思路后来被很多互联网公司沿用因为在真实业务里你面对的从来不是请写一个Dijkstra而是请处理一个繁杂的业务逻辑并把核心算法嵌进去。所以准备这类笔试重点不是追求难题偏题而是把基础算法的代码写得又快又稳。编程题二拿满分的难度其实不高难的是你在有限时间内不犯低级错误。1.2 当年出题风格的三个关键词我把2016年京东及其他大厂同期笔试里能见到的题型归纳了一下出题风格基本可以用三个关键词概括。第一个关键词是场景化包装。题目描述会刻意写成一段业务场景比如商品凑单、仓库拣货、优惠券计算、订单拆分。但剥掉这些外壳内核往往就是排序、双指针、动态规划、贪心这些经典模型。这种包装最坑的地方是读题时容易被冗长的描述带偏抓不住真正的约束条件。第二个关键词是数据范围不吓人。京东的笔试编程题一般不会让数据量大到必须上高级数据结构n 的规模通常在一万到十万这个级别要求的是 O(n) 或 O(n log n) 的解法偶尔需要 O(n^2) 剪枝也能过。这意味着你不需要掌握什么冷门算法但必须把常见模板练到肌肉记忆。第三个关键词是重边界。空输入、数组越界、整数溢出、重复元素、字符串首尾空格这些都是出题人埋伏笔的地方。一道简单的字符串题能不能从容处理各种边界情况往往比会不会某个高端算法更能体现真实代码功底。2. 字符串与模拟题笔试中的保分题2.1 只反转字母保留数字和符号位置这道题是我在复盘时觉得最有代表性的字符串题。题干非常简洁给定一个字符串只反转其中的英文字母数字、空格、标点符号全部保持在原来的位置上。看起来简单但第一次写很容易在边界条件上翻车。举个例子输入字符串a-bC-dEf-gh目标输出是h-gfE-dCb-a。手动推一遍字母有 a、b、C、d、E、f、g、h反转后顺序变成 h、g、f、E、d、C、b、a再把原来的-填回原就位就是结果。解法用双指针#include string #include cctype using namespace std; string reverseOnlyLetters(string s) { int left 0, right (int)s.size() - 1; while (left right) { while (left right !isalpha(s[left])) left; while (left right !isalpha(s[right])) right--; if (left right) { swap(s[left], s[right]); left; right--; } } return s; }这段代码的复杂度是 O(n)只遍历了字符串一次空间复杂度 O(1)没有额外开数组。具体过程就是两个指针从两端往中间走各自跳过非字母字符停在字母上就交换然后继续向内收缩。很多人第一次写会漏掉两个点。第一isalpha函数要包含cctype头文件而且要保证传入的是 unsigned char否则在某些编译器下会有未定义行为的争议。第二内部的两个while循环必须带上left right这个条件否则如果字符串全是符号left 会一路越界直接导致运行时错误。为什么这种题会放在编程题二这个位置因为它不考复杂算法考的是你能不能把双指针这个基本功写得滴水不漏。尤其要注意笔试环境里你没法调试只能一次编译运行看测试样例稍有不慎就是编译错误或者运行错误白白丢分。2.2 括号匹配的完整版括号匹配是数据结构课里栈的经典应用但在笔试里出现的频率高得惊人。京东2016年的编程题二里出现过一版完整版要求字符串同时包含()、[]、{}三类括号必须按正确顺序闭合。题意简单说输入一个只包含括号字符的字符串判断它是不是合法的括号序列。合法定义是每个左括号都要在恰当的位置被对应的右括号闭合并且不能出现像([)]这种交叉嵌套。标准解法是栈#include stack #include string using namespace std; bool isValid(string s) { stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char top st.top(); if ((c ) top () || (c ] top [) || (c } top {)) { st.pop(); } else { return false; } } } return st.empty(); }复杂度还是 O(n)空间复杂度最坏 O(n)也就是字符串里全是左括号的情况。我在帮人复盘时发现最容易错的是两个分支一是右括号出现的时候栈已经空了比如输入)(这种应该直接返回 false二是整个字符串扫描结束后栈里还有残留的左括号比如(()这种情况也要返回 false。很多同学只记得右括号要和栈顶配对忘记了最后要检查栈是否为空。这种模拟题的真正价值不在于考察栈这个数据结构而在于训练一种思维模式把人的直观逻辑翻译成程序时必须把所有异常分支都想全。括号匹配的直观逻辑很简单但人眼扫一眼就能判断的事情写成代码却需要多个分支条件。这就是编程题二想要筛选的能力——简单模型下能不能把逻辑写完整。3. 动规与贪心拉开差距的两类题3.1 背包类问题的简化考法最大价值分配2016年的笔试题里有一类很经典的题场景可能是购物车凑单或者仓库装箱核心就是0/1背包。题目描述会把它包装成有 n 件商品每件商品有重量占用的容量和价值背包容量有限求能带走的最大总价值。给一个典型的数据约束n 不超过 100背包容量的上限不超过 10000。这个数据范围意味着你必须做动态规划不能写指数级枚举。先分析一下为什么暴力不行。每件商品有选或不选两种可能n 件商品就是 2^n 种组合。n100 的时候2^100 是一个天文数字任何普通机器在笔试限时内都跑不完所以我们需要用状态转移来压缩重复计算。定义dp[i][j]表示前 i 件商品在背包容量为 j 的情况下能获得的最大价值。状态转移只有两种决策不选第 i 件商品dp[i][j] dp[i-1][j]选第 i 件商品前提是 j 大于等于第 i 件商品的重量dp[i][j] dp[i-1][j - w[i]] v[i]两种情况取较大值。最后答案就是dp[n][C]其中 C 是背包总容量。代码实现时有优化空间。因为dp[i]只依赖dp[i-1]我们可以把二维数组压缩成一维数组但内层循环必须倒着遍历这是0/1背包和完全背包最核心的区别#include vector #include algorithm using namespace std; int knapsack(int C, const vectorint w, const vectorint v, int n) { vectorint dp(C 1, 0); for (int i 0; i n; i) { for (int j C; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[C]; }为什么一维以后要倒序因为每个商品只能用一次。如果正序遍历容量 j那么dp[j - w[i]]可能已经在当前第 i 件商品的循环里被更新过了相当于同一件商品被重复放入了多次这就不符合0/1背包的规则。倒序遍历保证dp[j - w[i]]还是上一轮也就是没考虑当前商品时的状态。这道题在笔试里还有一个常见变体就是洗成完全背包把每件商品只能选一次改成每件商品可以选无限多次。这个时候只需要把内层循环从正序改成倒序的镜像——改成从小到大遍历即可。所以你看变体往往藏在约束条件的一句话差别里读题的时候一定要圈出每个商品最多选几次这个信息。3.2 贪心考法结束时间早优先另一道高频题是区间调度类。题干经常是一个资源分配场景一天内有多个任务每个任务有一个开始时间和一个结束时间你同一时刻只能做一个任务问最多能完成几个任务。数据约束一般是 n 不超过 10^5时间值可能是大整数。这个规模直接排除了 O(n^2) 的解法需要贪心。贪心策略很明确按结束时间从小到大排序依次选择当前结束最早、且开始时间不与已选任务冲突的任务。为什么这样最优直观解释是结束得越早给后面的任务留下的时间空间就越大所以优先选结束早的任务总是不会吃亏的。严格证明可以用交换论证法——假设最优解里第一个选择的不是结束最早的区间那么把它替换成结束最早的区间不会让剩余可选区间变少所以贪心解至少不劣于最优解。代码实现很短#include vector #include algorithm using namespace std; struct Task { int start; int end; }; int maxTasks(vectorTask tasks) { sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { return a.end b.end; }); int count 0; int lastEnd -1; for (const Task t : tasks) { if (t.start lastEnd) { count; lastEnd t.end; } } return count; }这里有几个容易踩的坑。第一排序依据是结束时间不是开始时间。如果按开始时间排序你会得到完全错误的结果。第二判断是否冲突时用的是t.start lastEnd注意如果题目允许两个任务无缝衔接上一个任务刚结束下一个任务立即开始那就用大于等于如果不允许要改成大于。第三lastEnd初始值要设成一个比所有开始时间都小的值比如-1如果你用 0 而任务里存在 0 开始的任务会漏掉第一个任务。这道题出现在编程题二里说明出题人希望考生具备一点算法证明的直觉。不需要写出严格数学证明但你要能感觉到结束早的应该优先而且知道为什么不是开始早的优先。我在面试中经常问候选人这道题能答出贪心策略的不在少数能解释清楚为什么按开始时间排序不行的就少了一半。4. 笔试现场的策略多拿分比写出满分更重要4.1 拿到题目先做的三件事我见过太多人一拿到编程题就埋头写代码结果写了半天发现用例过不去再回头读题往往是漏了某个输入格式或者输出要求。笔试现场时间紧张正确顺序应该是先花三到五分钟做三件事。第一读输入输出格式。是单组数据还是多组数据输入是不是要用 while 循环读到文件末尾每行的字段用什么分隔符这些信息藏在题目描述的最后几行却决定了代码的骨架。2016年京东的笔试环境用的是传统 OJ 模式输入输出必须严格匹配多打一个空格都不行。第二手推一遍样例。把题目给的示例输入在草稿纸上手动算一遍看看输出是怎么得到的。这个过程能帮你明确题目里的业务规则比如优惠券只能叠加使用和优惠券不能叠加使用在计算逻辑里是完全不同的代码。第三估算数据范围。题目会给 n 的上限养成看一眼就估算复杂度的习惯。n 是 100O(n^2) 可以接受n 是 10^5O(n^2) 就是必死n 是 10^18八成是要你找规律或者用矩阵快速幂。这个判断在草稿纸上花三十秒就能完成却能避免你写完一个必然超时的算法。4.2 暴力解法兜底再谈优化很多考生有个误区一道题想不出最优解就不写代码直接放弃或者卡在优化上直到时间耗尽。实际上笔试按通过的测试点给分部分正确远好于完全空白。正确做法是先写暴力解法保证逻辑正确让一部分简单用例通过然后再在暴力解法的基础上优化。比如上面说的背包问题如果你一时想不起怎么压缩空间可以先写二维 dp至少它是正确的能通过一部分测试点如果你连 dp 都没想出来可以写递归枚举n 比较小的测试点也能过。笔试是和时间赛跑不是优雅竞赛。我看过不少人的笔试代码发现一个规律能在编程题二上得分的人通常不是第一个想到最优解的人而是能快速写出准确暴力解、再用剩余时间逐步优化的人。最优解往往是在暴力解的思路上演化出来的直接凭空想最优解反而容易卡壳。4.3 时间分配建议针对编程题一 编程题二 编程题三这种常见结构我建议这样分配时间题目建议用时策略编程题一10分钟内保分题快速解决不要恋战编程题二25-35分钟核心题留足时间推演和自测编程题三20分钟拔高题卡住15分钟就果断跳过检查5-10分钟重测空输入、边界值、大数据量为什么编程题二要留 35 分钟因为它通常不是纯靠模板就能秒杀的题读题、推样例、写代码、调边界整套流程走下来 25 分钟是很正常的节奏。如果你提前写完不要急着交卷拿多出来的时间做边界测试是最划算的。很多人忽略的一点是笔试环境里的编译和运行是有开销的每次提交可能要排队等几秒甚至十几秒。如果把所有用例都靠提交来验证一次提交失败就是几分钟的损失。所以在本地编辑器里尽量多自测把a、、---这种边界输入都跑一遍再交。5. 刷完这套题我给后来人的三点复盘5.1 题库复用度比想象中高我刷完京东2016研发工程师编程题二之后最大的感触是这套题里的题型在后续几年被大量复用只是换了层壳。比如字符串里的双指针反转后来在其他公司的笔试里变成了只反转字符串中的元音字母背包问题常常换成预算内选择最大满意度方案区间调度变成最多能安排多少场面试。所以我不建议机械地按年份来刷题而是按题型归档。准备一个文档把每道题归到对应模型下面记录它的变体和常见坑。到了笔试前一周只看这个归档文档比盲目刷一百道新题有用得多。5.2 模板代码要练到肌肉记忆编程题二考到的快排、二分、双指针、栈、一维背包这些模板代码必须达到默写程度。我说的默写不是背下来而是理解每一行之后能在三分钟内无脑写对。因为考场上真正卡人的往往不是思路而是while的边界写错、还是搞混、数组越界导致运行错误。我备考时每天抽二十分钟手写模板不跑测试就是照着白纸写写完对照标准版检查。一开始总会漏括号或者写错循环边界坚持两周以后这部分代码就是零思考成本了。5.3 错题本记什么才有用很多人记错题本就是贴一遍题解代码说实话那对复习没什么用。我的错题本每道题只记四样东西题干里的核心约束、当时卡住的点、边界条件、复杂度结论。比如背包题我记的是一维dp内层倒序防止物品重复使用括号匹配题我记的是右括号先判栈空结束判栈不空。这样做的好处是复习成本极低。考前翻一遍错题本每道题三秒钟就能回忆起来而不是重新读一遍几千字的题干。我后来带过的几个学弟用这个方法备考反馈都是考前一周只看错题本比再刷一百道题效果好得多。最后说点个人体会。我当年准备笔试时总以为那些难题才是拉分关键直到反复复盘才发现编程题二这种位置的题目真正决定胜负的是保分题的准确率。难题做不出来大家都会空着但保分题写错边界条件才是最容易拉开差距的地方。所以如果你正在备笔试先从字符串模拟和经典dp的边界条件抓起性价比远高于死磕压轴题。