京东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) { stack<char> 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 种组合。n=100 的时候，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 vector<int>& w, const vector<int>& v, int n) { vector<int> 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(vector<Task>& 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 是 100，O(n^2) 可以接受；n 是 10^5，O(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的边界条件抓起，性价比远高于死磕压轴题。
