小红的慕斯模具统计 [题目链接](https://www.nowcoder.com/practice/c016abeeac86418db4ae97319de04af5) 思路 本题需要对多个等长的时间区间查询，统计每个区间内使用过的不同模具种类数。 离线排序 + 双指针 注意到所有查询的时间窗口宽度都是 ，这意味着如果我们按起始时间排序所有查询，那么每个窗口的左端点  和右端点  都是单调不减的。这正是双指针（滑动窗口）的经典适用场景。 具体步骤：  预处理记录：将所有使用记录按时间排序。 离线排序查询：将所有查询按起始时间排序，同时记录原始下标，以便最后按原始顺序输出答案。 双指针滑动：维护...

小红的岁晚可可塔 [题目链接](https://www.nowcoder.com/practice/6b06f501f8154f57801590ca495f37ac) 思路 本题是经典的最大子数组和问题。给定  层蛋糕，每层有一个甜度值（可正可负），要求找到一段连续的蛋糕层，使得甜度值之和最大。 Kadane 算法 我们用贪心的思想来解决这个问题。维护一个变量 cur 表示以当前元素结尾的最大子数组和：  遍历数组，将当前元素加到 cur 上。 用 cur 更新全局答案 ans。 如果 cur < 0，说明前面的子数组对后续只有负贡献，不如从下一个元素重新开始，将 cur 置为 0。  ...

多项式岭回归 题目分析 智慧城市供水监测系统有  天的连续用水量数据，其中  条记录缺失（标记为 Gap）。对每个缺失位置，用其前后最近的连续真实数据段拟合二阶多项式岭回归模型来预测。 思路 逐 Gap 独立建模预测 对每个缺失位置 ，确定训练数据的范围：  前向区间 ：从  向前搜索，遇到第一个 Gap 时停止， 为该 Gap 的下一天；若无 Gap 则  后向区间 ：从  向后搜索，遇到第一个 Gap 时停止， 为该 Gap 的前一天；若无 Gap 则   合并两个区间的真实数据作为训练集，用天数 （绝对天号）构造设计矩阵 （每行为 ），通过岭回归公式求解系数： $$ 其中 ， 为  单位...

用户分群 题目分析 电商平台需要根据用户的购物行为（月均消费金额、月均访问次数、退货率三个维度）对用户进行聚类分群。给定  个初始聚类中心和指定迭代次数，实现标准 KMeans 算法，输出最终的聚类中心坐标，保留两位小数。 思路 KMeans 算法模拟 这道题不需要任何花哨的优化，就是忠实模拟 KMeans 的两个核心步骤，反复执行指定次数即可。 每轮迭代分两步：  分配阶段：对每个数据点，计算它到所有  个聚类中心的欧氏距离（比较距离时用距离平方即可，省去开根号），将其归入距离最近的聚类 更新阶段：对每个聚类，将中心更新为该聚类内所有点各维度的算术平均值。若某聚类没有点被分配到，中心保持不变...

关闭工位 题目分析 工厂有  个工位，需要关闭恰好  个工位以节能。给定  个偏差值，分别对应工位  到  的质量偏差。要求不能同时关闭相邻的两个工位，在满足约束的前提下最小化总偏差。若无合法方案则输出 。 思路 经典不相邻选取 DP 从  个物品中选  个不相邻的，使权值之和最小。这是经典问题。  个物品中，最多能选  个不相邻的。若 ，直接返回 。 设  为从前  个物品中选  个不相邻物品的最小偏差和： $$  不选第  个：继承  选第  个：第  个不能选，从  转移  初始条件：，，。 用滚动数组优化空间，只保留前两行。 以样例验证：，，。选物品 2 和 4（不相邻），偏差 。 复...

加速优化问题 题目分析 一条物流路线有  个中转段，每段有若干运输方式可选，每种方式有延误风险和费用。需要为每段选择恰好一种运输方式，使所有段的延误风险之和不超过阈值 ，且总费用最小。 思路 拿到这道题，第一反应是枚举所有组合，但如果每段有  种选择、共  段，枚举量是 ，显然不可行。 仔细观察，这本质上是一个带约束的多阶段决策问题——每一段做一次选择，累积风险不超过 ，总费用最小。自然联想到背包类 DP。 但和经典背包不同的是，这里的"容量"（风险）是浮点数，没法直接开数组做背包。怎么办？ 关键思路是：我们不需要对风险值做离散化，而是直接维护一组 Pareto 最优状态。...

对称INT8量化方案 题目分析 实现神经网络推理中的对称 INT8 量化方案：对激活矩阵 A 和参数矩阵 B 分别量化，在整数域完成矩阵乘法后还原为浮点结果。 量化规则：  矩阵 A：按行（per-sample）量化，每行的缩放因子  矩阵 B：按列（per-channel）量化，每列的缩放因子  量化值： 还原：  思路 本题是一道模拟题，按照量化流程逐步实现即可。  量化矩阵 A：遍历每一行，计算该行绝对值最大值，求缩放因子，对每个元素做 round + clip 得到 INT8 值。 量化矩阵 B：遍历每一列，计算该列绝对值最大值，求缩放因子，对每个元素做 round + clip 得到...

连续子序列 题目分析 给定一个由 ASCII 字母和数字组成的字符串，找出其中不含重复字符的最长子串的长度。 思路 本题是经典的滑动窗口问题。 维护一个窗口 [left, right]，保证窗口内没有重复字符：  用哈希表 last 记录每个字符最后一次出现的位置。 右指针 right 从左到右遍历字符串，对于当前字符 s[right]：   - 如果该字符在窗口内出现过（即 last[ch] >= left），则将 left 跳到 last[ch] + 1，跳过重复字符。  - 更新 last[ch] = right。  - 更新答案 ans = max(ans, right - le...

遗迹探险家小红 题目分析 小红在遗迹中收集宝物，共  件宝物，每件宝物有耗时  和价值 。限制条件：  总探索时间不超过  分钟 耗时超过 30 分钟的"沉重宝物"最多选  件 每件宝物最多选一次  求能获得的最大总价值。 本题是带额外维度约束的 0/1 背包问题。 思路 二维费用背包 经典 0/1 背包只有"容量"一个维度的约束。本题多了一个约束：沉重宝物（）的数量不能超过 。因此需要在状态中多记录一个维度。 定义  为"使用时间恰好为 ，且选了  件沉重宝物时的最大价值"。 对于每件宝物 ，判断它是否为沉重宝物（），转移方程为： ...

幻兽防御战 题目分析 小红守护遗迹，有  只幻兽正在靠近，第  只幻兽初始距离为 ，速度为 ，到达时间为 。小红的弩每分钟只能发射一次：在第  分钟开始时（），她可以消灭一只尚未到达的幻兽。若此时存在某只存活的幻兽满足 ，则遗迹在射击前就被摧毁。求最多能消灭多少只幻兽。 思路 贪心（最早截止时间优先） 这是一个经典的调度问题：每分钟只能处理一个任务，每个任务有一个截止时间（幻兽到达时间），要在截止前完成尽可能多的任务。 关键观察：如果按到达时间从小到大排序，在第  分钟优先消灭到达时间最早的幻兽，一定不会比其他策略更差。这就是贪心策略——最早截止时间优先（Earliest Deadline F...

魔法相册的重复记忆 题目分析 小红在整理魔法相册时，发现有些照片因为备份出现在了多个相册中。每张照片有唯一标识符和时间戳，同一相册内所有照片 ID 不同，但不同相册之间可能出现相同 ID 的照片（时间戳一定相同）。需要找出所有出现在超过一个相册中的照片，统计它们在所有相册中的总出现次数，并按时间戳升序输出。 思路 哈希表计数 遍历所有相册中的照片，用哈希表记录每个照片 ID 的：  时间戳：首次遇到时记录，后续不变（题目保证同 ID 时间戳相同）。 出现次数：每次遇到该 ID 就加 1。  遍历结束后，筛选出出现次数大于 1 的照片，按时间戳升序排序输出。 示例推演 输入 4 个相册：  相册...

RAG系统最大收益 题目分析 RAG 系统需要在  个连续自然日内规划操作，使净收益最大化。知识库初始为"过期"状态，在第  天执行更新后，知识库在  天内有效。每天最多执行一项操作：更新并查询（付出 ，获得 ）、仅查询（知识库有效时获得 ）、或什么都不做。 思路 DP + 单调队列优化 核心观察：知识库的有效性完全取决于最近一次更新的时间。因此可以围绕"更新日"来设计 DP。 设  表示在第  天执行更新时，从第  天到第  天能获得的最大净收益（包含第  天的更新成本和查询收益）。 基础情况： 第  天是第一次更新（之前没有任何更新），则 。 状态转...

多分类加权指标计算 [牛客链接](https://www.nowcoder.com/practice/dec560ebcd8c47c9a37f6df692c38d25) 思路 本题是机器学习中经典的多分类评估指标计算问题，需要根据预测标签和真实标签，计算加权精确率（Precision）、召回率（Recall）和 F1 分数。 核心步骤：  逐类统计混淆矩阵元素：对每个类别 ，遍历所有样本，统计：   - ：预测为  且真实也为  的样本数  - ：预测为  但真实不为  的样本数  - ：真实为  但预测不为  的样本数  计算每类指标：   - ，分母为 0 时结果为 0  - ，分母为 0...

小红的能量校准 题目分析 给定一个关于变量  的一元一次方程，形如 左侧表达式=右侧整数。左侧表达式包含变量 、非负整数、运算符 +、*、(、)，且存在隐式乘法——当数字、变量、括号直接相邻时，中间省略了乘号。例如 2(x+1) 表示 ，x3 表示 。  在左侧恰好出现一次，方程保证有整数解，求  的值。 思路 递归下降解析 + 线性多项式运算 由于  只出现一次，左侧表达式关于  是线性的，可以表示为  的形式。我们用一个二元组  来表示每个子表达式的值，其中  是  的系数， 是常数项。 定义运算规则：  加法： 减法： 乘法：（因为线性，）  用递归下降解析表达式，按优先级从低到高分三层...