小红书笔试真题解析：完美数字与算法优化

1. 小红书2026.03.11笔试真题解析作为一名经历过多次大厂算法笔试的过来人我深知笔试真题对准备面试的重要性。今天我将详细解析小红书2026年3月11日的笔试真题这三道题都对应历史原题考察点非常经典值得认真研究。2. 题目一完美数字2.1 问题理解与解法思路完美数字这道题要求我们找出所有满足条件的连续正整数乘积。题目给出的条件是给定一个正整数n判断是否存在k个连续正整数的乘积等于n。这道题的关键在于认识到满足条件的连续正整数乘积其实非常少。我们可以利用这个特性预先计算出所有可能的合法答案然后在查询时直接判断是否命中即可。2.2 数学原理分析从数学角度看k个连续正整数的乘积可以表示为 x(x1)(x2)...(xk-1) n这个乘积的增长速度非常快。例如2个连续数x(x1) ≥ 23个连续数x(x1)(x2) ≥ 64个连续数x(x1)(x2)(x3) ≥ 24...因此对于给定的n我们只需要检查k从2到某个上限比如log₂n的情况即可。2.3 预处理实现方案我们可以预先计算出所有可能的连续乘积并存储起来。具体步骤如下初始化一个哈希表或字典来存储结果对于k从2到最大可能值比如20对于x从1开始计算x(x1)...(xk-1)如果乘积超过n的上限则停止将乘积作为键k作为值存入哈希表查询时只需检查n是否在哈希表中2.4 代码实现示例from math import prod def preprocess_perfect_numbers(max_n): perfect {} for k in range(2, 20): # 尝试不同的k值 x 1 while True: product prod(range(x, x k)) if product max_n: break if product in perfect: perfect[product].append(k) else: perfect[product] [k] x 1 return perfect # 预处理所有可能的完美数字 perfect_dict preprocess_perfect_numbers(10**6) def is_perfect_number(n): return n in perfect_dict2.5 复杂度分析预处理阶段的时间复杂度取决于k和x的范围但实际运行时会很快因为乘积增长迅速。查询阶段是O(1)的时间复杂度非常高效。2.6 注意事项乘积可能会很大要注意数值溢出问题预处理的范围需要根据题目给定的n上限来确定同一个n可能有多个k满足条件需要全部记录下来3. 题目二A先生的收藏品评估系统3.1 问题理解这道题要求我们统计数组中与查询值存在整除关系的元素个数。具体来说给定一个数组和多个查询对于每个查询值q需要统计数组中能被q整除的元素个数以及能整除q的元素个数。3.2 解法思路直接遍历数组进行统计的方法在查询次数多时会很慢。更高效的做法是预处理阶段统计数组中每个数字出现的次数使用筛法预处理因子贡献和倍数贡献查询阶段对于每个查询q使用预处理结果快速得到答案3.3 数学原理这个问题涉及到数论中的因子和倍数的概念。对于数组中的每个元素a和查询值q我们需要统计a是q的倍数即q能整除a的元素个数q是a的倍数即a能整除q的元素个数3.4 预处理实现我们可以使用筛法来高效预处理def preprocess(arr): max_val max(arr) freq [0] * (max_val 1) for num in arr: freq[num] 1 # 预处理倍数贡献能被q整除的数的个数 multiple_contribution [0] * (max_val 1) for q in range(1, max_val 1): for multiple in range(q, max_val 1, q): multiple_contribution[q] freq[multiple] # 预处理因子贡献能整除q的数的个数 factor_contribution [0] * (max_val 1) for q in range(1, max_val 1): for factor in range(1, int(q**0.5) 1): if q % factor 0: if factor max_val: factor_contribution[q] freq[factor] counterpart q // factor if counterpart ! factor and counterpart max_val: factor_contribution[q] freq[counterpart] return multiple_contribution, factor_contribution3.5 查询处理预处理完成后查询就变得非常简单def process_query(q, multiple_contribution, factor_contribution, max_val): if q max_val: # q比数组中所有数都大只能统计能整除q的数 divisible 0 for factor in range(1, int(q**0.5) 1): if q % factor 0: if factor max_val: divisible freq[factor] counterpart q // factor if counterpart ! factor and counterpart max_val: divisible freq[counterpart] return (0, divisible) else: return (multiple_contribution[q], factor_contribution[q])3.6 复杂度分析预处理阶段计算频率数组O(n)计算multiple_contributionO(max_val log max_val)计算factor_contributionO(max_val √max_val)查询阶段O(1)或O(√q)当q max_val时3.7 优化技巧可以只预处理到数组最大值对于更大的查询值q可以现场计算使用更高效的筛法实现可以进一步优化性能对于频繁查询的值可以缓存结果4. 题目三A先生的古籍修复4.1 问题理解这道题描述了一个古籍修复的场景。给定一些已知位置的字符和大量缺失部分要求计算出所有可能的修复方案数。具体来说古籍可以看作一个长字符串其中某些位置的字符已知未知部分需要填充填充的字符必须满足非降序的条件需要计算所有可能的填充方案数4.2 解法思路这个问题可以分解为多个独立的子问题将整个字符串根据已知字符分割成多个缺失段对每个缺失段计算非降序列的填充方案数将所有段的方案数相乘得到总方案数4.3 数学原理每个缺失段的填充问题实际上是一个多重组合计数问题。具体来说给定一个区间[l, r]需要填充r-l-1个字符使得第一个字符 ≥ 前一个已知字符最后一个字符 ≤ 后一个已知字符中间字符非降序这相当于在给定范围内计算非降整数序列的数量可以使用星和条Stars and Bars定理来解决。4.4 具体解法对于两个已知字符a和b之间的缺失段长度为m方案数为C(m b - a, m)其中C是组合数。证明我们需要选择m个数x₁, x₂, ..., x_m满足a ≤ x₁ ≤ x₂ ≤ ... ≤ x_m ≤ b令y₁ x₁ - a, y₂ x₂ - x₁, ..., y_m x_m - x_{m-1}, y_{m1} b - x_m则y₁ y₂ ... y_{m1} b - a且所有y_i ≥ 0这个方程的解数为C((b - a) m, m)4.5 代码实现from math import comb def count_restoration_sequences(known_positions, max_char): known_positions.sort() total 1 for i in range(1, len(known_positions)): prev_pos, prev_char known_positions[i-1] curr_pos, curr_char known_positions[i] m curr_pos - prev_pos - 1 # 缺失的字符数 a prev_char b curr_char if m 0: if a b: return 0 continue if a b: return 0 # 计算C(m b - a, m) total * comb(m b - a, m) return total4.6 边界情况处理开头和结尾的缺失段可以假设前面有字符0后面有字符max_char相邻已知字符相同方案数为1所有缺失字符也必须相同已知字符不按位置顺序给出需要先排序4.7 复杂度分析排序已知位置O(k log k)k是已知位置数量计算每个缺失段O(1)假设组合数预计算或快速计算总复杂度O(k log k)4.8 优化建议预计算阶乘和逆阶乘以便快速计算组合数对于大质数取模的情况使用卢卡斯定理等优化处理极大数字时使用高精度计算或模数运算5. 笔试准备建议5.1 刷题策略重点掌握基础算法排序、搜索、动态规划、贪心、图论等熟练常见数据结构数组、链表、树、哈希表、堆、并查集等多做真题和模拟题了解大厂出题风格5.2 时间管理快速阅读和理解题目先解决最有把握的题目合理分配时间不要在一道题上卡太久5.3 代码实现技巧编写清晰易读的代码注意边界条件和特殊情况的处理使用有意义的变量名和适当的注释5.4 调试技巧先通过小样例测试打印中间结果帮助调试考虑极端情况和大数据测试6. 总结这三道题目各有特点考察了不同的算法和数学知识完美数字数学洞察力预处理技巧收藏品评估数论知识筛法应用古籍修复组合数学问题分解能力在实际笔试中遇到这类题目时我的经验是先充分理解题意明确输入输出要求思考暴力解法然后寻找优化方向考虑是否有数学规律或特殊性质可以利用编写代码时注意边界条件和效率通过这三道题的练习可以很好地提升对数学类算法题的解题能力。建议读者不仅要理解这些解法还要尝试自己实现代码并在类似题目上练习应用这些技巧。