网易有道2017内推编程题拆解：模拟、动规与字符串处理

刷算法题这件事，我从来不相信“题海战术”能解决所有问题。但像“网易有道2017内推编程题”这种有明确背景、有真实场景的真题，确实值得拿出来反复嚼一嚼。原因很简单：这类题目往往不是单纯考你会不会背某个模板，而是考你在有限时间内，能不能把一个模糊的业务场景抽象成清晰的数据结构，再写出边界完整的代码。对于准备校招、内推，或者想系统提升编码能力的同学来说，这是一份含金量很高的训练材料。

这篇文章我会以当年这批内推题里最有代表性的几类题目为例，把完整的拆题过程、代码实现、调试踩坑和现场时间分配全部写出来。适合正在准备大厂笔试的应届生，也适合想检验自己算法功底的职场人。你会看到一套可以复用的解题思路，而不是零散的答案。

1. 拿到这组题，先别急着敲代码

很多人刷题有个习惯：看到题目描述，手立刻放到键盘上，恨不得马上写一个暴力解出来。笔试特别是内推笔试，最忌讳的就是这个。网易有道的题目有一个特点，就是题干普遍偏场景化，会用一个业务故事把算法题包装起来。你如果直接跳过去读输入输出，很容易漏掉对时间复杂度和边界条件的要求。

1.1 网易有道的笔试到底在考什么

从2017年内推这批题目来看，核心考察点集中在四个方面：基础数据结构（栈、队列、哈希表）、简单的动态规划、字符串处理，以及模拟题。这不是偶然。网易有道的产品线偏工具类和在线教育类，业务场景里大量涉及文本处理、用户行为序列分析、数据统计。所以笔试题目自然会向这些方向倾斜。

举个例子，当年有一道题是“字符串编码”相关的，题目背景是有道词典的输入提示。它要求你把一个字符串按连续相同字符压缩成“字符+出现次数”的格式。这道题放在业务里，就是做词条存储时的压缩逻辑。很多同学第一反应是直接遍历拼接，但一旦忘记处理最后一段字符，就会在边界用例上翻车。这种题目其实不考算法深度，考的是代码的完整性和严谨度。

还有一道“计算糖果”的题目，表面上是一个数学题：已知A减B、B减C、A加B、B加C的结果，要求你还原A、B、C的值。但仔细想，它考察的是你能否通过等式推导求解，以及在无解的情况下如何判断。这就涉及到了数学建模能力和条件判断能力。

我建议你拿到任何一道类似的题，先做三件事：

1. 在草稿纸上画出数据流：输入是什么，输出是什么，中间经过几步变换。
2. 标注边界条件：字符串为空、数组长度为1、数值超出常规范围，这些情况代码能不能扛住。
3. 预估暴力解法的复杂度：如果数据范围是10的5次方，O(n²)的解法基本可以直接放弃。

做完这三步再动笔，你的正确率会明显提升。

1.2 题目类型分布与难度参考

根据我对2017年内推题的整理，可以给这批题目画一个粗略的画像。整体难度属于“中等偏基础”，和现在动辄出hard级别压轴的笔试不同，有道更看重基础是否扎实。这个策略其实很聪明，因为内推筛选的是“能干活、代码稳”的人，而不是“竞赛型选手”。

从这个表能看出来，你不需要把《算法导论》从头啃一遍。但你需要对常见数据结构的基本操作熟到肌肉记忆，同时对“把一个实际问题转化为什么数据结构”有直觉。

2. 典型题目手把手拆解

接下来我挑三道有代表性的题目，完整走一遍从读题到AC的过程。这三道题分别对应了模拟、动态规划和字符串处理三个最常出现的考点。

2.1 用一道模拟题盘点基本盘

模拟题是笔试里的送分题，也是最容易丢冤枉分的题。原因是它不需要高深的算法，但对逻辑拆解能力要求不低。2017年有道内推有一道“数字反转”类题目，要求输入一个整数，输出反转后的整数，如果反转后溢出则输出0。

题目描述大概是这样：输入一个32位有符号整数x，返回x反转后的结果。如果反转后整数超过32位有符号整数的范围，就返回0。这个描述初看很简单，但里面藏着三个坑。

第一个坑是负数的处理。很多同学会先把符号丢掉，反转数字，再把符号加回来。这个思路没问题，但要注意边界，比如-2147483648反转后就超过了int范围。第二个坑是溢出判断。正数2147483647反转后会变成7463847412，明显溢出。如果题目要求用C++写，你用int存反转结果，在中间过程中就已经溢出了，根本等不到最后判断。所以判断溢出必须放在乘10加余数之前做，而不是之后做。第三个坑是末尾为0的情况。比如输入120，反转后应该是21，如果直接按位拼，很容易拼成021再转成int，输出反而没问题。但如果你自己实现字符串转数字，就要处理前置零。

我用Python写这个题，因为Python的int是无限精度的，不会真的溢出，但为了模拟32位环境，需要手动加判断：

def reverse(x): INT_MIN, INT_MAX = -(2**31), 2**31 - 1 sign = -1 if x < 0 else 1 x_abs = abs(x) rev = 0 while x_abs > 0: digit = x_abs % 10 # 核心：在累加之前判断是否溢出 if rev > (INT_MAX - digit) // 10: return 0 if rev < (INT_MIN + digit) // 10: return 0 rev = rev * 10 + digit x_abs //= 10 return sign * rev

注意上面的判断方式。很多人用的是rev * 10 + digit > INT_MAX这种写法，但问题是此时rev * 10可能已经溢出了。我这里用了一个等效变换：rev > (INT_MAX - digit) // 10。因为我们要判断rev * 10 + digit是否超限，等价于判断rev > (INT_MAX - digit) / 10。整数除法会向下取整，所以用//。这个方法在C++、Java里同样适用。

这道题给我们的启发是：模拟题考察的不是你会不会写循环，而是能不能预判所有边界输入。建议你在平时练习时，刻意把输入的特殊值列成一个清单：最大值、最小值、0、负数、末尾带0。遇到题目时就对照清单检查代码。

2.2 一道动规题教你如何想状态

动态规划是很多同学的噩梦，但网易喜欢的动态规划题目恰恰是“看起来不像动态规划”的那种。2017年内推题里有一道“数字和为sum的方法数”，题目大意是：给定n个正整数和一个目标数sum，问有多少种方式选出若干个数，使它们的和等于sum。每个数只能用一次。

这个题目本质上是个01背包问题。但如果你没看出来，也可以用递归暴力枚举，每个数选或不选，时间复杂度O(2^n)，n到二十就直接爆炸。所以在笔试场景里，能不能从“选或不选”这个决策模型中跳出来，直接定义状态，决定了你能不能过这道题。

我们定义dp[i][j]表示从前i个数中选取若干个数，使得它们的和为j的方案数。那么对于第i个数a[i]，有两个决策：不选它，那方案数就是dp[i-1][j]；选它，那方案数就是dp[i-1][j-a[i]]，前提是j >= a[i]。所以转移方程为：

dp[i][j] = dp[i-1][j] + (j >= a[i] ? dp[i-1][j-a[i]] : 0)

初始状态dp[0][0] = 1，表示一个数都不选、和为0，有一种方案。

很多教科书会直接建(n+1) x (sum+1)的二维数组，空间复杂度O(n*sum)。但实际笔试里，为了节省内存和提升速度，我们可以使用一维滚动数组优化。因为dp[i]只依赖dp[i-1]，所以可以用一维数组反复更新。但注意j要倒序遍历，否则当前数会被重复使用。

def count_subsets(nums, target): dp = [0] * (target + 1) dp[0] = 1 for num in nums: for j in range(target, num - 1, -1): dp[j] += dp[j - num] return dp[target]

这个倒序为什么关键？你想想，如果正序遍历，当j从小变大时，dp[j-num]可能已经包含了当前num的贡献，这样同一个数就被用了多次，01背包就变成了完全背包。这在笔试里是经典错误，但这恰恰也是考察点。你需要不仅知道怎么写，还要知道为什么这么写。

还有个细节：方案数可能很大，题目往往会要求取模。如果你做题时没看到取模要求的数字大小，最好问自己几个问题：结果可能超过int范围吗？需要用long long吗？Python用户可能没这个烦恼，但C++用户必须提前考虑。

2.3 字符串处理中的边界细节

字符串处理类题目看起来平平无奇，实际上是最容易“90%用例通过，最后10%卡你半小时”的类型。有一道题是要求计算给定字符串中最长不重复子串的长度，比如输入“abcabcbb”，输出3。这个是LeetCode上的经典题，但在笔试现场，很多人会因为处理窗口左边界时差一个1而失分。

思路是滑动窗口加哈希表。我们用两个指针left和right维护当前窗口，right每次向右移动一格，如果s[right]在窗口中已经出现过，就把left跳转到上一次出现位置的下一个位置。同时用一个字典记录每个字符最近一次出现的下标。

def length_of_longest_substring(s): char_index = {} left = 0 max_len = 0 for right, ch in enumerate(s): if ch in char_index and char_index[ch] >= left: left = char_index[ch] + 1 char_index[ch] = right max_len = max(max_len, right - left + 1) return max_len

代码很短，但有两个地方容易写错。第一是char_index[ch] >= left这个判断不能省。因为如果字符之前出现过，但它出现的位置已经在当前窗口的左边了，说明它已经被窗口滑过，这时不应该把left拉回去。第二是更新char_index[ch]的时机，一定要在更新窗口后更新。如果先更新字典，就会导致窗口计算错误。

这道题在面试里还经常会被追问：如果字符串不是英文字母，而是Unicode字符集合，你的方案还成立吗？字典方案天然支持任意字符集，但如果用定长数组，就只能处理ASCII。这说明你在设计算法时，要有意识地区分“针对特定输入”和“通用性”的取舍。

3. 从思路到AC的完整过程

有了思路只是第一步。笔试现场真正消耗时间的，是“写代码”和“调试”这两个环节。很多同学思路清晰但代码写出来一堆bug，最后时间全砸在Debug上。所以我分享一套我自己的实战流程，能有效减少无谓的返工。

3.1 解题模板与代码骨架

我写题有一个习惯：先在注释里把函数框架写出来，包括输入、输出、算法描述和复杂度分析。不要小看这一步，它逼着你在写代码之前把逻辑理顺，减少边写边改的概率。

# 函数名: solve # 输入: # nums: List[int] - 候选数字列表 # target: int - 目标和 # 输出: # int - 满足条件的方案数量 # 算法: # 01背包动态规划，dp[j]表示和为j的方案数 # 倒序遍历j避免单个数字被重复使用 # 复杂度: # 时间 O(n * target)，空间 O(target) def solve(nums, target): dp = [0] * (target + 1) dp[0] = 1 for num in nums: for j in range(target, num - 1, -1): dp[j] += dp[j - num] return dp[target]

写注释不是浪费时间，它有两个好处。第一，在考试中如果被判题系统返回运行时错误，你可以快速定位到函数意图。第二，如果万一题目做不完，清晰的注释会给你后面检查代码提供方便。虽然笔试不会人工看注释，但这个习惯会降低你思考的负担。

代码骨架还应该包含一个专门处理边界情况的入口。我在写主逻辑之前，通常会先写两行：

if not nums and target == 0: return 1 if not nums: return 0

这种前置判断看似啰嗦，实际上能帮你避免很多空指针和索引错误。笔试时的测试用例最爱干的事，就是塞一个空输入给你。

3.2 调试过程中的常见坑

即使思路清晰，代码也很容易在细节上出问题。我总结了我最常踩的四个坑，如果你也在刷题，可以把下面这张表存下来。

有一个例子很典型。在“最长不重复子串”这道题里，如果我用Python写，enumerate(s)返回的下标是从0开始的。很多同学会习惯从1开始计数的业务思维，结果right - left + 1写成了right - left，导致长度永远少1。这种错误很难通过肉眼发现，唯有在脑子里把left=0, right=0, s[0]的情况过一遍才能看出来。

调试时的一个小技巧是：构造一个极小的测试用例，例如长度为3或4的字符串，并打印出每一步的left、right和当前窗口。虽然笔试一般不让你打印，但在本地IDE练习时这个方法非常管用。

3.3 现场时间分配建议

很多同学笔试失败不是不会做，而是时间分配崩了。网易内推笔试通常有两道编程题，时长大约80到100分钟。我的建议是：

1. 前5分钟通读所有题目，不做任何代码，只是记录每道题的难度和类型。
2. 先从模拟题或字符串处理题开始做，这类题分数好拿，不容易卡壳。
3. 动态规划题放在第二顺位，给它分配30到40分钟。
4. 最后一题如果卡了10分钟以上没有思路，果断放弃，把时间拿回来检查前两题的边界用例。

这个策略有一个前提：你做第一题的速度要够快。所以平时练习时，建议用计时器模拟考试环境，逼自己在25分钟内完成一道简单到中等难度的题目。时间压力上来了，你才能知道自己在什么环节慌，然后针对性训练。

另外，我强烈建议你练习“在纯文本编辑器里写代码”。很多同学依赖IDE的自动补全和括号匹配，一到笔试的在线编辑器就浑身不自在。这不是小事。提前适应无补全环境，才能保证考场上的手感。

4. 笔试现场容易翻车的点

很多时候，题目本身你会做，但最后还是挂了。为什么？因为笔试不只是考算法，还在考工程素养。下面这些坑，是我自己踩过或者看别人踩过的。

4.1 输入输出的坑

网易有道的笔试系统通常要求从标准输入读数据，输出到标准输出。很多同学在练习LeetCode时习惯了函数传参的模式，到了笔试现场忽然要自己处理多行输入，一下子就懵了。

举个例子，如果输入第一行是数字n，第二行是n个整数，你用Python写：

import sys def main(): data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) nums = list(map(int, data[1:1+n])) # 业务逻辑

这种一次性读入所有数据，再做切片的方式，比逐行input()更快、更不容易出错。因为sys.stdin.read()能一次性处理掉所有的空白字符，包括换行和多余空格，避免因为行尾有空格导致的解析错误。

还有一个细节：当题目要求“每行输出一个结果”时，很多人会用循环内print，这是没问题的。但如果结果需要按特定顺序输出，建议用一个列表收集结果，最后统一'\n'.join(results)输出。这样能避免print函数多次调用带来的性能损耗，也方便检查输出格式。

4.2 超时与内存的优化

内推笔试的判题机一般对时间卡得不紧，但也不是无限放水。如果数据范围是10^5，O(n^2)基本过不了；如果是10^3，O(n^2)还可以接受。所以拿到题第一步，先看数据范围，再决定算法。

我之前见过一个同学做数字和那道题，他用了递归枚举加剪枝，心想“剪枝应该能过”。结果测试用例里n是1000，直接超时。这就是对数据规模没有敏感的典型例子。

内存方面，一个常见的坑是用二维数组存动态规划表。当n是1000、target是10000时，二维数组就是1001 x 10001个整数，约为千万级。如果用C++的int，就是40MB，可能勉强能过；如果开成long long，内存直接翻倍到80MB，大概率碰线。所以能用滚动数组就尽量用滚动数组，这不是炫技，是生存需要。

4.3 代码风格与笔试细节

这部分很多人不在意，但在实际评卷中可能影响你能否进入下一轮。某些在线笔试系统在交卷后会把代码发给面试官人工审阅。如果你的代码变量名全是a、b、temp，注释全无，即使AC了也会给面试官留下差印象。反之，如果你的代码结构清晰、有必要的注释、边界处理完备，这在面试官眼里就是可维护性的证明。

我建议养成几个小习惯：

1. 变量名用可读性强的命名，比如用nums而不是n，用char_index而不是ci。
2. 函数单一职责，不要在一个函数里又做输入解析又做算法又做输出格式化。
3. 必要的注释写在关键算法行上方，不要每一行都注释。

另外，笔试前一定要确认判题环境使用的是哪个Python版本。Python 2和Python 3的整除、print语法完全不同。用Python 3写的代码如果在Python 2环境下编译，会大面积报错。遇到这种情况不是你不会做，只是环境不熟悉，特别亏。进场前花30秒确认语言版本，能省下大量的无意义debug时间。

5. 复盘与延伸：刷这套题的正确姿势

笔试结束不是终点，复盘才是把题目价值发挥到最大的关键。我建议你每做完一套题，都要做一次系统复盘，而不是对完答案就扔到一边。

5.1 刷这类题的意义在哪里

很多人刷题只关注“这道题怎么做”，但很少问“为什么这道题会出现在内推笔试里”。其实每一道题都对应着一种业务能力。字符串处理对应日志清洗、关键词提取；动态规划对应资源分配、路径规划；模拟题对应接口状态流转、订单状态机。如果你能从题目反推业务场景，你就不是在刷题，而是在模拟工作。

比如“数字和为sum的方法数”这道题，放到业务里就是一个凑单场景：已知商品价格列表，给定目标金额，问有几种凑单组合。如果你能在简历里写“熟悉状态压缩和动态规划，并能在实际业务场景中应用”，效果远比空泛地写“熟悉算法与数据结构”有说服力。

5.2 我的几点个人建议

说到底，笔试只是面试流程中的一个环节，它不是终极目的。我见过太多同学刷了几百道题，代码能力确实不错，但一到谈项目经验就支支吾吾。网易这类公司面试时非常看重候选人能不能把技术方案讲清楚，能否在一个模糊的需求中抓住关键点。所以，你在准备笔试的同时，不要忘记锻炼自己的表达能力和需求分析能力。

另外一点是要学会“适度写题”。不要为了刷题而刷题，每天做三四道并做深度复盘，效果比一天刷十几道然后全忘光要好得多。我自己的习惯是：每周挑一个固定时间，把这一周做过的错题重做一遍，不看题解，只凭记忆写代码。这种间隔重复的方法，远比我当年死记硬背题解有效。

5.3 最后分享一个检查代码的小技巧

无论你多熟练，提交前一定要花两分钟做一次“脑内执行”。选一个普通用例，把代码运行过程在脑子里过一遍。具体做法是：画一个状态表，行代表循环次数，列代表关键变量的值，手动推演一遍。这个方法看起来慢，但它是抓边界bug最有效的办法。时间越紧张，越要留出这一步。

比如做“最长不重复子串”时，我每次提交前都会脑内执行“abcabcbb”这个用例，逐个字符确认left和right的移动过程。实际做下来，这个动作只需要一分钟，但能让你躲掉至少90%的粗心错误。这种细节上的严谨，恰恰是网易笔试想要筛选出的特质。