网易2017内推笔试编程题合集全解析：六道题吃透字符串模拟与二分答案

这套“网易2017内推笔试编程题合集二”我一直把它当成研究国内互联网大厂笔试出题思路的活标本。和现在动不动就 hard 难度、系统设计题的校招不同2017 年的内推笔试题更偏向“代码基本功 脑子清不清楚”六道题覆盖字符串、模拟、数学、排序题量不大但每一道都有区分度。我刷了很多遍也拿它给不少准备秋招的朋友当过练手材料。今天就把这套题从题目拆解、解题思路到完整实现、易错点一次性讲透。1. 先看全局这套题到底在考什么1.1 六道题的分布与难度曲线这套题集一共包含六道编程题分别是彩色的砖块、交错01串、操作序列、独立的小易、小易喜欢的单词、等差数列。从题型分布上看没有复杂的图论、动态规划、线段树甚至连链表的影子都看不到全部集中在笔试最基础、也最容易被忽略的几个点上字符串判重与集合计数线性扫描与状态维护双端队列模拟或找规律数学建模与二分答案字符串合法性校验排序后做差分验证难度曲线也比较典型前两题属于“暖场题”基本送分但前提是你得冷静。中间两题开始有区分度尤其是“操作序列”和“独立的小易”一个考模拟方向感一个考数学建模能力。最后两题又回到基础但埋着边界陷阱。整体看下来网易想筛的不是“学过多少算法”而是“能不能在有限时间内把思路理清楚把代码写稳”。1.2 网易选人逻辑不考偏题怪题考工程思维我后来复盘这套题时发现网易的笔试出题风格其实偏“工程向”。什么是工程向就是题目本身不绕弯子但要求你把题目描述翻译成代码时足够严谨把边界条件处理干净。举个例子“独立的小易”这题如果不懂把现实生活抽象成“每天消耗多少资源、产生多少开销”很容易把公式记错或者漏掉免费住宿期的限制。再比如“操作序列”如果你只在纸上模拟而不去找规律代码写出来会很啰嗦还容易在奇偶性上翻车。这些能力恰恰是实际开发中最需要的理解需求、抽象建模、写出可维护的代码而不是炫技。1.3 时间分配建议我建议按 40 分钟来限时训练这套题。前两题每题 5 分钟中间两题每题 10 分钟最后两题每题 5 分钟剩下 5 分钟用来检查和调试。别小看这个节奏笔试现场是没有 IDE 自动补全的很多人的代码其实都挂在编译不过、输入输出格式错误这种低级问题上。如果你在某个题上卡了 15 分钟还没思路果断跳过。笔试是分数制不是一题定生死先把能拿的分拿到手。2. 字符串与逻辑判断三类送分但易错的题2.1 彩色的砖块数颜色就完了题目给出一串小写字母每个字母代表一种砖块颜色。要求计算摆成一排后能让相邻砖块颜色不同的摆放方案数。如果颜色种类超过两种输出 0否则输出颜色种类数。这题的第一步是去理解“为什么答案不是排列数”。假设有三种颜色 A、B、C你无论怎么排必然会有相邻两块颜色相同因为鸽巢原理在这个场景下直接生效只有两个相邻关系约束而颜色有变化需求当颜色数大于 2 时无法保证整串相邻都不同。反过来如果只有一种颜色方案数是 1只有两种颜色第一个位置定下来后第二个位置就定了所以方案数是 2。代码实现非常简单s input().strip() k len(set(s)) if k 2: print(k) else: print(0)这里最容易犯错的地方是直接输出len(set(s))忘了判断大于 2 的情况。还有人会把“方案数”理解成“颜色数”以外的组合数越绕越远。我的建议是拿到这种题目先动手列几个小例子比如“ABAB”“ABC”把答案先手算出来再写代码基本不会错。2.2 交错01串最长交替子串题目给一个只包含 0 和 1 的字符串要求找出最长的连续子串使得相邻字符不相同也就是形如 0101 或 1010 的交替串。这题的核心是“交替串”在相邻字符变化上的连续性。假设当前已经维护了一个交替串长度那么当新字符和前一个字符不同时交替串可以继续扩展否则当前交替串断裂只能从这个新字符重新开始。每次扩展完都更新一下最大长度。实现上就是一次线性扫描s input().strip() max_len 1 cur 1 for i in range(1, len(s)): if s[i] ! s[i - 1]: cur 1 if cur max_len: max_len cur else: cur 1 print(max_len)有一个细节要注意如果字符串长度为 1答案应该是 1所以max_len和cur的初始值都应该是 1。很多人写成 0或者循环从 0 开始导致结果差 1。另外这道题不能用set去重之类的思路它要的是连续子串不是子序列顺序和连续性都不能丢。2.3 小易喜欢的单词条件别漏题目定义了一个“喜欢的单词”需要同时满足三个条件单词长度至少为 3没有两个相邻的字符相同没有三个相邻字符在字母表中连续递增比如 abc、bcd、xyz输出字符串Likes或Dislikes。这题考的是多条件判定没有算法难度但漏条件的人特别多。有一个常见错误是只判断了相邻相同字符忘了判断三个连续递增字符另一个是把“三个连续递增字符”理解成“任意三个递增字符”比如 abx 也算这就不对了题目要求的是三个连续字符在位置上相邻。代码实现s input().strip() ok True if len(s) 3: ok False else: for i in range(len(s) - 1): if s[i] s[i 1]: ok False break if ok: for i in range(len(s) - 2): if ord(s[i 1]) ord(s[i]) 1 and ord(s[i 2]) ord(s[i 1]) 1: ok False break print(Likes if ok else Dislikes)我建议在判断连续递增字符时用ord的差值比较这样比字符串拼接s[i:i3] in abcdefghijklmnopqrstuvwxyz更高效也不容易写错。另外注意括号匹配这种双重循环加 break 的写法很容易在笔试时手滑漏掉一个if或者break写完后最好在脑子里逐行走一遍。3. 数学推导与模拟真正的分水岭3.1 独立的小易先把“每天开销”算明白这道题是整份题单里我觉得最有意思的一道因为它非常贴近现实小易有 x 天免费住宿期、f 个水果、d 元钱每天要吃一个水果免费期结束后每天还要付 1 元房租每个水果卖 p 元问他最多能活多少天。我第一次做这题时直接用公式ans f d / (p 1)结果错得离谱因为忘记考虑免费住宿期和已有水果。后来我改用二分答案的思路反而简单很多因为判断某个天数是否可行是非常直观的。假设要活 t 天那么需要的水果总数是 t 个已经免费拥有 f 个如果不够就需要买需要买的个数是max(0, t - f)需要交房租的天数是max(0, t - x)因为前 x 天免费总开销就是p * max(0, t - f) max(0, t - x)只要这个开销不超过 d 元就能活 t 天。我们要求的是最大的 t这里 t 的取值有明显二段性如果能活 t 天那么一定能活小于 t 天如果不能活 t 天那大于 t 天也一定不行。所以直接二分x, f, d, p map(int, input().split()) def can_live(t): return p * max(0, t - f) max(0, t - x) d lo, hi 0, d f x 1 while lo hi: mid (lo hi 1) // 2 if can_live(mid): lo mid else: hi mid - 1 print(lo)二分上界可以取d f x 1这是一个绝对安全的上限因为即使每天开销很大也不可能活过f d天再加上免费住宿期加一块儿肯定足够。这里有个很关键的地方can_live里的两个max是配套的不能省略。比如 t 小于 f 时水果不需要买但房租可能在 t 超过 x 时已经开始产生又比如 t 小于 x 时房租免费但水果如果不够还得买。只有把两个约束条件同时考虑进去答案才对。这也是为什么我不推荐背公式理解了数学表达式之后即使题目变化也能从容应对。3.2 操作序列模拟还是找规律题目的描述是小易有一个长度为 n 的数组 a1, a2, ..., an然后依次对数组 a 中的元素进行 n 次操作第 i 次操作会把 ai 放到当前序列的末尾如果 i 是奇数或开头如果 i 是偶数最后输出整个序列。比如输入 1 2 3 4操作过程是把 1 放到末尾序列为 [1]把 2 放到开头序列为 [2, 1]把 3 放到末尾序列为 [2, 1, 3]把 4 放到开头序列为 [4, 2, 1, 3]最终的输出是4 2 1 3。最简单的做法是直接用双端队列deque从头到尾模拟一遍最后从左到右输出。在 Python 里deque.appendleft和deque.append都是 O(1) 的操作完全不会有性能问题。from collections import deque n int(input()) a list(map(int, input().split())) dq deque() for i in range(n): if i % 2 0: dq.append(a[i]) else: dq.appendleft(a[i]) print( .join(map(str, dq)))注意这里 i 从 0 开始题目里的“第 i 次”从 1 开始所以第一次操作对应 i0是放到末尾第二次操作对应 i1是放到开头。如果你在if条件里把奇偶写反结果就完全反过来了。如果你不想用deque也可以直接从最终序列的规律入手最后一个元素永远在结果的最前面然后间隔一个取一个剩下的元素按原顺序排列在末尾。这个规律写出来的代码更短但前提是你对奇偶性足够敏感。我个人的建议是笔试时用deque模拟更稳妥不容易想错。3.3 等差数列排序后的一行代码题目给出 n 个整数问能否通过重新排列让它们成为一个等差数列如果能输出Possible否则输出Impossible。思路非常简单先把数组排序然后检查相邻两个数的差值是否全部相等。n int(input()) a list(map(int, input().split())) a.sort() diff a[1] - a[0] ok True for i in range(2, n): if a[i] - a[i - 1] ! diff: ok False break print(Possible if ok else Impossible)这里有个边界情况值得注意当 n 1 时a[1]会越界。不过题目一般会保证 n 2但为了保险前面对if n 2可以直接输出Possible。另外差值diff可能为负数所以不能用绝对值去比较直接用原值做差就行。排序后即使有负数相邻差值依然是确定值。4. 完整代码与本地自测4.1 输入输出约定这套题在牛客网上的输入格式通常是每道题单独一个测试用例不是多组输入所以不需要写while True循环。字符串可能带换行符要用strip()清理整数直接map(int, input().split())接收。4.2 一个文件跑六道题我习惯把六道题的逻辑封装成六个函数然后在本地用一个简单的分发器同时测这样自测起来很方便。下面是我整理的一版完整代码可以直接复制到本地运行也可以把每个函数单独拆出去提交。from collections import deque def colorful_bricks(s): k len(set(s)) return k if k 2 else 0 def alternating_01(s): max_len 1 cur 1 for i in range(1, len(s)): if s[i] ! s[i - 1]: cur 1 max_len max(max_len, cur) else: cur 1 return max_len def operation_sequence(a): dq deque() for i, v in enumerate(a): if i % 2 0: dq.append(v) else: dq.appendleft(v) return list(dq) def independent_xiaoyi(x, f, d, p): def can_live(t): return p * max(0, t - f) max(0, t - x) d lo, hi 0, d f x 1 while lo hi: mid (lo hi 1) // 2 if can_live(mid): lo mid else: hi mid - 1 return lo def liked_word(s): if len(s) 3: return False for i in range(len(s) - 1): if s[i] s[i 1]: return False for i in range(len(s) - 2): if ord(s[i 1]) ord(s[i]) 1 and ord(s[i 2]) ord(s[i 1]) 1: return False return True def arithmetic_progression(a): a.sort() diff a[1] - a[0] for i in range(2, len(a)): if a[i] - a[i - 1] ! diff: return False return True4.3 边界用例自测我在本地跑这几组用例时专门测了最容易出错的边界情况# 彩色的砖块 print(colorful_bricks(AA)) # 1 print(colorful_bricks(ABAB)) # 2 print(colorful_bricks(ABC)) # 0 # 交错01串 print(alternating_01(1)) # 1 print(alternating_01(0101)) # 4 print(alternating_01(00110)) # 3 对应 011 或 110 # 操作序列 print(operation_sequence([1, 2, 3, 4])) # [4, 2, 1, 3] print(operation_sequence([1, 2, 3])) # [3, 1, 2] # 独立的小易 print(independent_xiaoyi(10, 2, 100, 1)) # 56 print(independent_xiaoyi(1, 1, 1, 1)) # 1 # 小易喜欢的单词 print(liked_word(abc)) # False print(liked_word(aba)) # True print(liked_word(abca)) # True 吧没有连续相同没有连续递增 # 等差数列 print(arithmetic_progression([3, 1, 2])) # True print(arithmetic_progression([1, 3, 2])) # True print(arithmetic_progression([1, 2, 4])) # False这里面最值得关注的是independent_xiaoyi(10, 2, 100, 1)的输出。按我最早记错的公式算出来是 51但实际答案是 56。因为小易在前 10 天里虽然有 8 天需要额外买水果但不需要交房租所以每日开销其实只有 1 元而不是 2 元。这就再次说明背公式不如把约束条件列出来二分答案虽然多写了几行代码但正确率有保障。5. 笔试现场容易踩的坑5.1 输入解析与多组数据很多人栽在输入解析上。牛客网的样例输入里字符串可能带空格或换行如果直接用input()不去空格set(s)就会多一个换行符导致判重出错。我见过有人因为少写了strip()导致len(set(s))恒等于 2怎么查都查不出来。我的习惯是凡是读字符串一律先strip()宁多勿少。另外这套题不是多组输入不需要while True。如果你之前刷过一些题库可能习惯性写上while True加try except EOFError在这套题里反而会因为读不到输入而卡死或者输出多一个多余换行。5.2 二分边界mid 怎么取“独立的小易”这题用二分时很多人会写成mid (lo hi) // 2结果导致死循环。当lo和hi相邻时如果can_live(mid)为真lo没有前进程序就卡住了。正确写法是mid (lo hi 1) // 2配合lo mid/hi mid - 1这样才能保证收敛。这个模板值得背下来找最大可行值时用上取整找最小可行值时用下取整。如果你觉得二分不放心直接 O(1) 解也可以但一定要把免费住宿期和已有水果分开讨论。我建议还是二分逻辑简单不容易漏。5.3 操作序列的方向很容易搞反“操作序列”这题最大的坑就是奇偶方向的判断。题目说第 i 次i 从 1 开始操作如果 i 是奇数放到末尾偶数放到开头。代码里i从 0 开始所以第一次操作i0是偶数下标对应放到末尾。如果你写成if i % 2 1: append结果就会变成一个完全不同的序列。我自己的记忆技巧是用 n2 的用例去验证比如输入[1, 2]正确输出应该是[2, 1]如果程序跑出来是[1, 2]那就是判断条件写反了。这种小技巧在实际做题时非常管用比硬记规则靠谱。5.4 输出格式大小写别错“小易喜欢的单词”输出的是Likes/Dislikes“等差数列”输出的是Possible/Impossible。这些词首字母大写其余小写中间没有下划线、没有空格。我见过有人把Dislikes写成Dislike或者把Impossible写成impossible结果答案明明算对了还是判错。提交前一定要对着题目描述检查一遍输出字符串。5.5 数据类型溢出“独立的小易”里d f x 1的中间结果可能很大在 C 里要用long long在 Python 里不用管。但是如果你用 C 写千万别用int存二分上下界否则一些极端数据会直接溢出变成负数导致二分直接崩掉。这也解释了为什么我推荐用 Python 刷题省心。6. 从笔试到面试这套题带给我的启发6.1 基础题其实是面试聊天的素材我后来面试时和面试官聊过这套题发现很多面试官对自家公司的笔试题是有印象的。你如果在自我介绍里提一句“我刷过贵公司的 2017 年内推笔试题里面那道理财题很有意思”面试官往往会追着问你的思路。这时候你如果能讲清楚“为什么用二分而不是背公式”会比单纯报答案加分很多。6.2 把这套题当“算法翻译练习”来刷我的建议是不要把这套题当题库刷一遍就完事而是当成“翻译练习”。给你一段中文描述你能不能在 5 分钟内把关键约束条件列出来然后翻译成代码这套题里的每个题目都有一个核心的“翻译点”彩色的砖块颜色数大于 2 是什么含义交错01串交替性如何用s[i] ! s[i-1]表达操作序列奇偶下标与操作类型的映射独立的小易两个max约束的抽象小易喜欢的单词连续递增的判定条件等差数列排序后差分验证如果你能做到一看到“相邻不同”“连续递增”“免费期后交租”这些词立刻条件反射出对应的代码结构那笔试基本就稳了。6.3 后续还可以怎么扩展这套题虽然老但可以做的扩展很多。比如交错01串可以改成“至多翻转 k 个字符后的最长交替子串”就变成滑动窗口双指针题独立的小易可以把水果价格改成每天递减变成贪心加堆的题。我自己在准备面试时经常会拿这种基础题进行变形把一题吃透比盲目刷十道新题更有效。如果你正在准备校招笔试我建议把这六道题每个都手写三遍以上第一遍看题解写第二遍合上书自己推第三遍模拟笔试限时写。三轮下来你对字符串、模拟、二分和排序的理解会有一个质的提升。