从牛客一模看集合编程题：递归建模、BFS判重与哈希优化

这套2019牛客一模的编程题我印象一直挺深。不是因为题目有多难而是它把集合这个最基础的数据结构从头到尾考了一遍有递归定义的集合有藏在数学背景里的自然数集合还有需要用哈希集合优化暴力的题目。当时在牛客上做完这一套最大的感受是——真正拉开差距的不是会不会某个经典算法而是能不能在看懂题目之后迅速把问题翻译成集合操作的思路。这篇文章不是官方题解是我自己当年参加一模的复盘。我会把题目形态、解题思路、代码细节和踩过的坑整理出来尤其会围绕集合这条主线展开。如果你正在准备春招秋招或者想找一套有代表性的编程题检验自己的水平这套题值得认真做一遍。看完你至少能明白在线笔试里的集合题考点到底藏在哪。1. 试卷整体印象四道题的难度阶梯和我的时间分配1.1 题型分布与难度阶梯2019年牛客一模的编程题整体排布是比较典型的上阶梯结构。印象里四道题大体可以分成三个档次。题号题目形态核心考点难度感知第一题签到题字符串或基础数组操作输入输出、简单模拟热身级别第二题数学背景的构造题数论推导、等差数列公式中等偏易第三题集合定义类题目递归展开、集合判重、BFS中等偏难第四题数据结构和算法的综合应用图论或动态规划结合集合去重压轴这个排布非常典型前面的题保底分后面的题拉开区分度。不要小看第一题在线笔试里签到题翻车的人每次都有大部分原因是读题不仔细把多组输入当成了单组输入。1.2 我的做题顺序先吃软柿子再啃硬骨头开考之后我先把四道题都扫了一遍这种做法救了我。第二题和高斯求和有关一看就是公式题第三题是递归定义的集合核心在于建模第四题明显需要更多的思考时间。我当时定的策略是第一题十分钟内解决第二题二十分钟解决第三题主攻第四题如果有剩余时间再碰。整套卷子做完复盘我发现一个规律前三题几乎都围绕集合这个概念展开。这就引出了一个很重要的问题——为什么一模的编程题集体指向集合2. 为什么一模把集合当成核心考点2.1 集合在笔试题里的三种出场方式刷题多了你会发现集合在编程题里一般有三种出场方式。第一种是显式考集合。题目会直接定义一个集合让你判断某个元素是否属于它、求集合大小、求交集并集。这种题表面上在考数学定义实际上考的是怎么把定义翻译成代码。第二种是工具型考集合。题目本身和集合无关但解法中必须用集合做去重或标记。比如图论里的visited数组、动态规划里的状态判重本质都是集合思想。第三种是语言层面考集合。这种更多出现在面试题里比如Java面试喜欢问HashSet和TreeSet的区别、底层数据结构C#面试会问怎么创建一个集合并保证不重复。虽然笔试不一定直接考语言API但你在写代码时选择的集合类型会直接影响复杂度和正确性。一模这套题恰好把三种出场方式都覆盖了。所以做完之后你会感觉集合这个词无处不在这不是巧合是出题人刻意设计的。2.2 集合考的不是API是建模能力很多同学看到集合题第一反应是我会用set我会用HashSet题目稳了。但这套题告诉你会用API远远不够。比如以a为基的集合Ba那道题题目给的是一组递归规则你看着像数学题但本质上要你做的是把一句若x属于集合则f(x)也属于集合翻译成一个可执行的状态扩展过程。这里思路如果没转过来就会卡在怎么用集合表示无限元素这个点上。再比如高斯自然数集合那道题看起来是求和实际上要你意识到连续正整数集合的数学结构再用等差数列公式去优化。这里考察的是从具体例子中抽象出数学模型的能力这和纯粹的API调用完全是两码事。所以我把这套题的价值总结成一句话它逼你把集合从数据结构升级成思维方式。这才是笔试真正想挑出来的能力。2.3 在线笔试环境对集合题特别友好还有一个容易被忽略的因素在线笔试的判题系统对集合题很友好。因为集合操作的结果是确定的不涉及浮点数精度、不涉及随机化、不容易产生歧义非常适合机器判题。这也解释了一个现象模考卷子里集合题多不是偶然而是出题人为了保证题目质量、控制判题难度会优先选择这类结果明确的题。3. Ba集合递归定义下的集合到底怎么建模3.1 题目还原你看到的定义和实际要算的东西这道题我当时拿到手题目大概长这样对于以a为基的集合Ba定义如下 1a属于Ba 2若x属于Ba则 xa 和 x*a 也属于Ba 3Ba是满足上述条件的最小集合。 给定 a 和 n判断 n 是否属于Ba若属于输出它是由多少步生成的。第一眼看上去集合元素是无限多的a, 2a, a², 3a, a³……越往后膨胀得越厉害。如果没转换思路很容易陷入把所有元素都生成出来的误区。其实题目真正要你做的是沿着规则进行状态扩展。这本质上是图的遍历每个集合元素是一个节点规则1是起点规则2是边的定义判断n是否属于Ba就是在问从a出发经过若干次加a或乘a操作能不能走到n。3.2 BFS展开加set判重最稳的解法建模思路定了之后解法就很直接了从a出发做BFS每一步生成两个新状态 xa 和 x*a用set记录已经访问过的元素防止重复扩展扩展过程中如果遇到n就说明n属于集合。如果元素值超过n就直接剪枝——因为加法和乘法都是递增操作继续扩展只会更大不可能回到n。from collections import deque def can_reach(a, n): if n a: return False if n a: return True q deque([a]) visited {a} while q: x q.popleft() for nxt in (x a, x * a): if nxt n: return True if nxt n and nxt not in visited: visited.add(nxt) q.append(nxt) return False这个代码里set承担了两个职责一是判重防止同一条路径反复扩展二是标记保证算法的复杂度是O(n)级别的而不是指数级的。当时我写完之后自己测了几组数据发现一个关键点只要n能表示成 a^k 或 某个a的倍数组合的形式算法就能找到。这让我意识到集合定义题表面上考规则实际考的是你有没有想到用BFS去生成集合。3.3 考场上容易翻车的三个细节第一乘法的爆炸速度。如果n是10^9级别x*a可能在一次扩展后就远远超过n。所以扩展时一定要先判断 nxt n 再入队否则队列会越积越大直到内存撑爆。第二重复扩展的问题。如果不做visited标记同一个元素会被多条路径访问到。比如 a2 时22 和 2×2 都等于4两条路径都会生成4第二次生成时如果没有set判重就会重复入队指数级膨胀。第三递归和BFS的选择。有些同学习惯写DFS递归但这道题的状态空间可能是环形的——xa 和 x*a 的结果之间可能互相到达递归深度不可控容易栈溢出。BFS配合显示队列更稳。4. 高斯自然数集合把求和公式变成解题工具4.1 题目背景与高斯求和的迁移看到高斯两个字第一反应应该是1加到100等于5050的故事。这道题也确实用到了等差数列求和公式。题目大概是说高斯发现任意一个正整数都可以拆成若干个连续正整数的和。比如 9 234 45而 8 就没有任何连续正整数拆分。给定 n求有多少种不同的拆分方式。这里连续正整数集合是解题的关键。连续正整数的和从首项a开始、长度为len时和可以写成sum len × a len × (len - 1) / 2这个公式就是高斯求和公式的变形。推导过程很简单len个连续整数的和是 len × a (0 1 ... len-1)后面的括号里正好是 len×(len-1)/2。4.2 从暴力到数学优化枚举长度而不是枚举起点第一直觉是枚举起点a然后往里加数判断和是否等于n。但这么做复杂度是O(n²)n一大就废了。换个思路枚举长度len通过公式反推起点a是否存在。根据上面的公式给定len之后a (n - len × (len - 1) / 2) / len要让a是正整数需要满足两个条件n - len×(len-1)/2 必须大于0这个差值必须能被len整除。于是我们可以写出完整的代码def count_ways(n): ans 0 len_ 2 while len_ * (len_ - 1) // 2 n: remain n - len_ * (len_ - 1) // 2 if remain 0 and remain % len_ 0: ans 1 len_ 1 return anslen的最大值范围也很好估算因为a最小是1所以 n ≥ len×(len-1)/2也就是 len 大约在 sqrt(2n) 量级。对于10^9的n只需要枚举到大约45000个长度复杂度可以接受。4.3 边界情况和输出格式的坑这道题代码写对不难但边界情况特别容易出错。当 n1 时没有任何长度满足条件答案是0。当 n2 时同样没有满足条件的长度。这个当时很多同学没注意。还有一点题目如果要求输出具体的拆分方案那就不能只计数了。需要在把可行的len筛出来之后再计算对应的首项a然后循环输出a到alen-1的区间。这里要注意输出格式数字之间用空格分隔、末尾是否允许有多余空格在线判题对空格非常敏感。我当年在这题上犯过一个低级错误输出答案是0而不是换行导致格式错误。所以大家做题时一定要确认输出的每个数字后面跟的是空格还是换行最后一组数据后面要不要加换行。5. 编程语言的集合实现细节Python/Java/C横向对比5.1 Python的set笔试中最省心的集合用Python写集合题体验是最好的。set自带去重、交集、并集、差集操作写起来几乎就是数学语言基本不用关心底层实现。s {1, 2, 3} t {3, 4, 5} print(s t) # 交集 {3} print(s | t) # 并集 {1, 2, 3, 4, 5} print(s - t) # 差集 {1, 2}需要注意的一点是frozenset。Python的set是可变的不能作为另一个set的元素。如果你想做一个集合的集合必须把内部集合转成frozenset。这个问题在做某些题目时会出现我当时第一次碰到还愣了一会儿。元素必须是可哈希的这意味着list不能放进set。如果需要用list做元素先转成tuple。这些细节平时写脚本无所谓笔试的时候一旦踩到就是运行时错误。5.2 Java和C有序集合和无序集合的选择Java里用HashSet还是TreeSetC里用set还是unordered_set底层机制完全不同。HashSet和unordered_set底层是哈希表查找、插入、删除平均O(1)但元素没有顺序。TreeSet和set底层是红黑树操作是O(log n)但元素保持有序。笔试中如果题目只要求判重优先用HashSet/unordered_set因为常数更小。但如果题目要求输出有序的集合结果比如从小到大输出所有不重复元素用TreeSet/set会省很多事省去手动排序。Java的HashSet里面存放自定义对象时需要重写hashCode和equals方法否则集合判重会按对象地址判断导致两个内容相同的对象都被放进去。笔试里经常有人在这上面翻车尤其是定义了一个坐标类Point然后想对它去重时。5.3 集合输出乱码这个坑是怎么踩出来的热词列表里有一条集合输出是乱码我一看就想起来自己确实踩过这个坑而且不止一次。第一次是用C写set的时候set里存的是char*。这个坑非常隐蔽C的set在比较两个char*时比较的是指针地址而不是字符串内容所以两个内容相同的字符串会被当成不同元素。更离谱的是如果用printf直接输出set里的char*遇到中文字符串在某些终端下就会显示乱码。第二次是Java的System.out.println直接打印HashSet集合里的中文对象如果没有正确设置编码Windows控制台上就可能显示为乱码。解决方法是启动参数加-Dfile.encodingUTF-8或者干脆用循环逐个输出元素不要直接println整个集合。写到这里我想多说一句笔试环境一般不会让你调试太久遇到这种看起来和算法无关的玄学问题最稳妥的做法是确保集合的泛型类型是字符串对象而不是字符数组同时在本地就配置好UTF-8编码。这种细节看着小但真的能卡掉一大半人。6. 从模考到面试集合考点还能怎么延伸6.1 集合的底层实现和面试追问一模考完之后如果只是把题改完就扔一边那这套题的价值就只发挥了一半。更好的做法是把集合这条线延伸成一套完整的面试知识点。Java面试里关于集合的经典追问包括HashSet的底层是怎么实现的为什么用HashMap就能实现HashSetTreeSet的排序和比较器是怎么回事ConcurrentHashMap为什么不能存null键值这些问题看起来是语言问题其实核心还是集合如何保证不重复、如何保证有序这两个基础点。我后来在准备面试时把一模的集合题整理成一页纸的笔记笔试里的set用来判重面试里的Set用来考哈希原理。两者殊途同归。6.2 多重集合排列的计数模板热词里有一条多重集合排列这个知识点也值得一提。有时候题目会给一个包含重复元素的集合问这些元素能构成多少种不同的排列。公式是n! / (cnt1! × cnt2! × ... × cntk!)其中cnt1到cntk是每种重复元素的个数。这个公式看起来简单但配合大数取模时需要预处理阶乘和逆元。笔试中这种题出现的频率不低而且经常藏在字符串重排字母统计之类的外壳下面。更好的消息是Python的math.comb可以直接做组合数计算配合循环就能实现多重排列计数不需要自己写逆元。刷题时合理利用语言特性能省下不少时间。6.3 刷完这套题我建议你顺手做的两件事第一件事把每道题的输入输出部分单独提取出来改造成可以复用的一套模板。比如统一的读取整数、读取一行字符串、输出用空格分隔的数组等函数。在线笔试时间紧张能少敲几行代码都是好的。第二件事把BFS配合set判重的代码背下来。这套模板在集合定义题、状态搜索题、迷宫题、字符串变换题里通用性极强。你只需要做的是定义清楚状态是什么、规则是什么、terminate条件是什么剩下的就是套模板。聊到这儿集合这条主线差不多就串完了。有些人刷题追求数量一套一套往下刷但迟迟不见长进。问题往往出在人没有停下来做归纳同样是集合递归定义的集合考的是建模高斯自然数集合考的是数学公式和枚举优化语言层面的集合考的是底层原理。归纳完之后你会发现你刷的不是一道一道的题而是一类一类的解法。这套2019一模的题目技巧不算高深胜在典型。我建议你找一个完整的时间段按笔试的标准时间把四道题过一遍然后对照我今天写的思路重新整理自己的解法。尤其是Ba集合那题真正能把BFS加set玩顺了再遇到任何按规则生成集合的题目你都会觉得不过如此。