关注我们，每天更新大厂最新笔试题解析
前言
文末给大家推荐一下我们的活动，针对校招笔面试全覆盖的全程真一对一的提高，参加活动前会给你安排一个全面的摸底，摸底后会针对你的情况进行分析和对于参加活动的介绍，然后你再决定是否参加!
在线做题链接：https://niumacode.com/
冲突约束：采用贪心算法求解一维最大独立集，先按升序尽可能多地选取不冲突的元素，再根据“配对删除”的规则确保总淘汰数为偶数即可。
小红书丝带AR特效：利用带约束的动态规划（DP）进行方案数递推，并引入辅助数组单独记录特定结尾的状态，从而精准剔除不合法的分段拼接。
星际能量枢纽：巧妙结合前缀和与 ST 表实现高效的区间最值查询，再利用前缀最大值的单调性，针对每个起点通过两次二分查找快速锁定合法的右端点范围
冲突约束
题目描述
小红书生态团队在评论审核中，需要对得分接近的评论判定观点相近，这一判断逻辑可以帮助团队灵活的调整评论区的观点统一性/观点多样性。 现在，将模型简化如下：给定长度为 的整数数组 和一个整数 。若 ，则称 与 观点相近。 一次操作可以选择一对元素，并将其同时从数组中删除（数组长度减少 ）。 经过若干操作后，需要保证数组中不含任何观点相近的元素，且希望保留的元素数量尽可能多。 请你计算，经过若干操作后，最终保留下来的最大元素数量。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 () 代表数据组数，每组测试数据描述如下： 第一行输入两个整数 和 ()，表示数组长度、观点相近的阈值。 第二行输入 个整数 ()，表示数组元素。 除此之外，保证单个测试文件的 之和不超过 。
输出描述
对于每组测试数据，新起一行输出一个整数，表示最终保留下来的最大元素数量。
样例输入
2
5 2
1 2 4 7 9
4 0
1 1 2 5
样例输出
3
2
提示
样例解释 对于第一组测试数据，保留 ，我们可以证明这是最优的。 对于第二组测试数据，在 时，相等元素冲突，保留 ，我们可以证明这是最优的。
思路与代码
这段代码的核心思路是利用贪心算法来寻找满足不冲突条件下的“最大独立集”。首先对整个数组进行升序排序，然后从左到右依次遍历，只要当前遍历到的元素与上一个决定保留的元素差值严格大于阈值 （即两者不冲突），就贪心地将其加入保留集合。这种从左到右取最小可行值的策略，能保证在有限的数值范围内塞下尽可能多的不冲突元素，从而求出理论上最多能保留的个数。
其次，需要处理题目中“每次必须同时删除一对（两个）元素”的限制。这意味着最终被剔除的元素总数必须是偶数。因此，在贪心求出最多保留个数后，代码会计算被淘汰的元素数量（数组总长度减去最多保留个数）。如果这个淘汰数量是奇数，说明剩余的元素无法完美两两组队删除，我们必须从刚才保留的集合中再多牺牲掉一个元素，让被删除总数变成偶数，最后得出的结果就是满足所有条件的最佳答案。
import java.util.Arrays;
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner reader = new Scanner(System.in);
if (reader.hasNextInt()) {
int testCases = reader.nextInt();
for (int t = 0; t < testCases; t++) {
int size = reader.nextInt();
int limit = reader.nextInt();
int[] elements = newint[size];
for (int idx = 0; idx < size; ++idx) {
elements[idx] = reader.nextInt();
}
Arrays.sort(elements);
int validCount = 0;
long previousVal = -3000000000L;
for (int idx = 0; idx < size; ++idx) {
if (elements[idx] - previousVal > limit) {
validCount++;
previousVal = elements[idx];
}
}
if ((size - validCount) % 2 == 1) {
validCount--;
}
System.out.println(validCount);
}
}
reader.close();
}
}
小红书丝带AR特效
题目描述
在小红书“品牌创意工坊”中，营销人员可以为直播和短视频活动创建定制化丝带AR特效，结合品牌ID与礼盒包装场景，实现动态丝带动画。为了支撑亿级日活的前端渲染，后端需要在活动发布时预先计算并缓存所有可能的切割方案数，确保小程序组件和Web端秒级响应。 现有一根虚拟丝带长度为 ，可以将其分割成若干段或保持一整段不动，但是每段长度只能取整数 、 或 中的一个，且不允许任何长度为 的段后面直接跟随长度为 的段。 请对所有长度 ()，统计合法的切割方案数，供小红书前端组件批量加载与渲染。由于答案可能很大，请将答案对 取模后输出。顺序不同视为不同方案。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 () 代表数据组数，每组测试数据描述如下： 在一行上输入四个整数 ()，代表最大丝带长度、可选分段长度 。保证 两两互不相等。 除此之外，保证单个测试文件的 之和不超过 。
输出描述
对于每组测试数据，新起一行，输出 个整数，其中第 个数表示长度为 的丝带的合法分割方案数对 取模的结果。
样例输入
2
5 1 2 3
4 1 2 3
样例输出
1 2 4 6 1
1 2 4 6
提示
样例解释 在第一个样例中，当 时：
- 时，按不带约束的方式共有 种方案，但其中 不合法，故为 种；
思路与代码
这段代码的核心思路是动态规划。为了统计所有的合法切割方案，程序使用了一个主数组（dpSum）来记录到达每一个指定长度时的总合法方案数；同时，为了处理题目中“长度 后面不能直接跟 ”的特殊约束，额外使用了一个辅助数组（stateX）来专门记录“以长度为 的段作为结尾”的方案数。
在状态转移的计算过程中，对于任意长度 ，其合法方案数由最后一步的三种切割选择累加而成：如果最后切的是 或 ，其方案数分别直接继承自长度为 和 时的总方案数；如果最后切的是 ，则必须从长度为 的总方案数中，减去那些以 结尾的方案（即 ），从而精准剔除掉“ 后面接 ”的不合法组合。最后将这三个分支的有效方案数相加并进行取模，即可递推得到答案。
import java.util.Scanner;
publicclassMain{
staticfinalint MODULO = 1000000007;
publicstaticvoidmain(String[] args){
Scanner input = new Scanner(System.in);
if (!input.hasNextInt()) {
return;
}
int t = input.nextInt();
int limit = 1000005;
int[] stateX = newint[limit];
int[] dpSum = newint[limit];
for (int k = 0; k < t; k++) {
int len = input.nextInt();
int x = input.nextInt();
int y = input.nextInt();
int z = input.nextInt();
dpSum[0] = 1;
stateX[0] = 0;
for (int idx = 1; idx <= len; idx++) {
int pickX = (idx >= x) ? dpSum[idx - x] : 0;
int pickY = (idx >= y) ? dpSum[idx - y] : 0;
int pickZ = 0;
if (idx >= z) {
pickZ = dpSum[idx - z] - stateX[idx - z];
if (pickZ < 0) {
pickZ += MODULO;
}
}
stateX[idx] = pickX;
long currentTotal = (long) pickX + pickY + pickZ;
dpSum[idx] = (int) (currentTotal % MODULO);
System.out.print(dpSum[idx]);
if (idx < len) {
System.out.print(" ");
}
}
System.out.println();
}
}
}
星际能量枢纽
题目描述
在《星际能量枢纽》游戏中，你作为宇宙能源工程师，需要修复古代文明遗留的“量子谐振核心”。星系中分布着 个能量节点（用数组 表示），每个节点包含正/负能量。当激活连续的非空节点序列 时，系统会计算从区间起始位置到区间内每一个位置的累计能量总和，并记录这些累计值中的最大者作为该区间的能量过载峰值。 只有当某个区间的能量过载峰值正好等于临界值 时，才能触发该区间的谐振反应。请计算所有能激活核心的区间数量，为星际舰队提供跃迁能量！
输入描述
第一行输入两个整数 ()，分别代表节点数量和临界值。 第二行输入 个整数 ()，代表每个节点的能量。
输出描述
输出一个整数，代表所有能激活核心的区间数量。
样例输入
5 2
0 2 -5 4 -3
样例输出
8
提示
样例解释1 在这个样例中，全部可选的区间为 、、、、、、、。
样例2输入 5 4 -7 9 2 -8 5
样例2输出 3
思路与代码
代码的核心思路是基于“前缀和 + ST表（稀疏表） + 二分查找”来实现的。首先，将区间累加能量的问题转化为前缀和来处理，区间 内的能量过载峰值，本质上等于该区间内前缀和的最大值减去起点前一个位置 的前缀和。为了在后续计算中能快速获取任意区间的前缀和最大值，代码在预处理阶段构建了 ST 表，这使得每一次区间最大值查询的时间复杂度降到了 。
在核心求解阶段，代码遍历每一个可能的区间起点 。由于固定起点 后，随着终点 向右延伸，区间 内包含的前缀和最大值呈现单调非递减的特性，这就满足了使用二分查找的条件。因此，针对每个起点 ，代码利用两次二分查找分别确定右端点 的有效范围：第一次找到刚好“大于等于”目标值（即 处前缀和 + ）的左侧边界，第二次找到“严格大于”目标值的右侧边界。这两个边界位置的差值，就是以 为起点且符合谐振条件的区间数量，最后将所有起点的有效数量累加即为最终答案。
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) return;
int numOfNodes = sc.nextInt();
long limitK = sc.nextLong();
int[] logVal = newint[numOfNodes + 1];
for (int idx = 2; idx <= numOfNodes; idx++) {
logVal[idx] = logVal[idx / 2] + 1;
}
long[] valArr = newlong[numOfNodes + 1];
long[] sumArr = newlong[numOfNodes + 1];
for (int idx = 1; idx <= numOfNodes; idx++) {
valArr[idx] = sc.nextLong();
sumArr[idx] = sumArr[idx - 1] + valArr[idx];
}
int maxDepth = logVal[numOfNodes] + 1;
long[][] rmqTable = newlong[numOfNodes + 1][maxDepth];
for (int idx = 1; idx <= numOfNodes; idx++) {
rmqTable[idx][0] = sumArr[idx];
}
for (int d = 1; d < maxDepth; d++) {
for (int idx = 1; idx + (1 << d) - 1 <= numOfNodes; idx++) {
long leftMax = rmqTable[idx][d - 1];
long rightMax = rmqTable[idx + (1 << (d - 1))][d - 1];
rmqTable[idx][d] = Math.max(leftMax, rightMax);
}
}
long finalRes = 0;
for (int start = 1; start <= numOfNodes; start++) {
long expectedMax = sumArr[start - 1] + limitK;
int leftB = start, rightB = numOfNodes;
int lowerBound = numOfNodes + 1;
while (leftB <= rightB) {
int m = leftB + (rightB - leftB) / 2;
int lenLog = logVal[m - start + 1];
long curMax = Math.max(rmqTable[start][lenLog], rmqTable[m - (1 << lenLog) + 1][lenLog]);
if (curMax >= expectedMax) {
lowerBound = m;
rightB = m - 1;
} else {
leftB = m + 1;
}
}
leftB = start;
rightB = numOfNodes;
int upperBound = numOfNodes + 1;
while (leftB <= rightB) {
int m = leftB + (rightB - leftB) / 2;
int lenLog = logVal[m - start + 1];
long curMax = Math.max(rmqTable[start][lenLog], rmqTable[m - (1 << lenLog) + 1][lenLog]);
if (curMax > expectedMax) {
upperBound = m;
rightB = m - 1;
} else {
leftB = m + 1;
}
}
if (upperBound > lowerBound) {
finalRes += (upperBound - lowerBound);
}
}
System.out.println(finalRes);
}
}
10个月宝宝每天需要喝多少奶粉？
