1.联想题目邻项合并归序时间2026年8月7日题目内容产线质检得到一条长度为n的整型读数序列v1, v2, ..., vn。允许反复选取一对相邻读数将其合并为一个新读数新读数的值为两者之和。需要使整条序列从左至右保持非降任意相邻两项中左侧读数的数值不超过右侧读数。请计算达成上述目标所需的最少合并次数。输入描述首先输入一行一个正整数q表示随后有多少条记录。对于每条记录第一行输入一个正整数n表示该条记录中读数的个数。第二行输入n个正整数v1, v2, ..., vn表示读数序列。数据范围1 q 201 n 4 * 10^31 vi 10^9输出描述按记录顺序对每条记录各输出一行一个非负整数表示该条记录对应的最少合并次数。样例输入 1复制代码123456733213412343516样例输出 1复制代码123101样例说明 1第一条记录将v2与v3合并得到[2, 4]满足2 4共合并 1 次。第二条记录序列[1, 2, 3, 4]本身已单调不减无需合并。第三条记录将v1与v2合并得到[6, 6]共合并 1 次。样例输入 2复制代码1231532145样例输出 2复制代码11样例说明 2将中间的2与1合并得到[3, 3, 4, 5]相邻读数依次满足3 3 4 5共合并 1 次。题解第一步核心思维转换最重要的一步题目问的是最少需要合并多少次我们可以换个角度想最多能把数组切成多少段举个例子原数组[3, 2, 1, 4, 5]一共 5 个数n5。如果我们能把它切成 4 段比如[3],[2,1],[4],[5]段和分别是 3, 3, 4, 5满足递增。既然切成了 4 段说明我们只需要把原本 5 个数合并成 4 个数也就是只需要合并 1 次把 2 和 1 合并。核心公式最少合并次数 总长度 n - 最多能切出的段数 k第二步贪心策略怎么切为了让切出的段数尽可能多每一段就应该尽可能短。所以我们的策略是从左往右扫只要当前这一段的和 ≥≥ 上一段的和就立刻“切一刀”开启新的一段第三步Java 代码逐行解释import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int q sc.nextInt(); // 读取测试用例的数量有几组数据 // 循环处理每一组数据 while (q-- 0) { int n sc.nextInt(); // 读取当前数组的长度 n long[] v new long[n]; // 用 long 数组存储数据防止累加时 int 溢出 // 循环读取 n 个数字 for (int i 0; i n; i) { v[i] sc.nextLong(); } // 【核心逻辑开始】 long lastSum 0; // 记录“上一段”的总和初始为 0第一段前面没有段所以要求最宽松 long curSum 0; // 记录“当前正在累积的这一段”的总和 int count 0; // 记录成功切出了多少段 for (int i 0; i n; i) { curSum v[i]; // 把当前数字加到当前段的总和中 // 核心判断如果当前段的和 上一段的和说明满足非降条件了 if (curSum lastSum) { count; // 成功切出一段段数加 1 lastSum curSum; // 更新“上一段的和”下一段要拿它作比较 curSum 0; // 【关键】清零当前和准备开始累积下一段 } // 如果 curSum lastSum说明当前段还不够大什么都不做继续往后看下一个数字 } // 循环结束后最后剩下的数字如果没凑够会自动并入上一段因为题目保证有解 // 最终答案总长度 - 最多段数 最少合并次数 System.out.println(n - count); } } }京东题目1抽检共现项集时间2026年8.15日好的这道题其实是在模拟一个经典的数据挖掘算法。我们可以把它想象成超市的“购物篮分析”——比如发现“买啤酒的人通常也会买尿布”。通俗解释题目要做什么想象你是一个工厂的质检员手里有一大堆“故障报告单”。每张报告单上列出了这次故障中同时坏掉的几个零件比如[零件1, 零件2]。老板想知道哪些零件经常“结伴”坏掉但是老板有个要求只有当这组零件同时出现的次数超过一定数量题目叫min_cnt时才算数。偶尔一两次一起坏的不算我们要找的是那种“铁哥们”关系。举个例子假设min_cnt 2至少出现2次才算。记录1[1, 2, 3]记录2[1, 2, 4]记录3[1, 3, 5]分析过程单个零件零件1出现了3次零件2出现了2次... 它们都达标了。两个零件组合[1, 2]在记录1和2都出现了共2次达标[1, 3]在记录1和3都出现了共2次达标[2, 3]只在记录1出现1次淘汰三个零件组合[1, 2, 3]只在记录1出现淘汰最终你要交给老板的名单按规则排序先列出所有达标的单个零件再列出达标的两个零件组合以此类推。我们应该做什么解题思路这就用到了题目提到的Apriori 算法。它的核心思想非常聪明叫作**“层层递进不行就砍”**。我们不需要把1,2,3,4,5的所有组合都试一遍那样太慢了而是分步骤来第一步海选“单兵作战”强的k1先统计每个零件单独出现的次数。如果次数 min_cnt直接扔掉因为它连单打独斗都不行跟别人组队肯定更不行。剩下的就是频繁1项集 ($L_1$)。第二步组队“双人搭档”k2拿上一步剩下的零件两两配对。关键剪枝重点在配对之前先看一眼它的“子集”。比如我们要检查[A, B]如果A或者B在第一步已经被淘汰了那[A, B]绝对不可能达标直接不用算省时间对剩下的候选组合去原始数据里数数看它们一起出现了几次。次数够的留下不够的扔掉。这就是频繁2项集 ($L_2$)。第三步组建“三人小队”k3拿上一步留下的“双人搭档”尝试合并成三人组。同样利用剪枝如果[A, B, C]里面的[A, B]在上一步被淘汰了那[A, B, C]也不用看了。数数留强汰弱。第四步循环直到结束一直这样k4,k5... 直到某一轮再也组不出合格的队伍为止。第五步整理输出把刚才每一轮留下的“精英团队”收集起来。排序规则先比人数少的排前面人数一样比零件编号字典序。因为我们是按k从小到大算的所以天然就是排好序的。总结这道题就是让你写代码实现这个**“筛选 - 组队 - 再筛选 - 再组队”的过程。难点不在于算法原理而在于如何高效地表示集合**比如用元组或位运算以及如何快速判断子集是否存在剪枝。python版本# 抽检共现项集 - Apriori 频繁项集挖掘 import json import numpy as np data json.loads(input()) # 同一条抽检记录里的编号互异排好序后所有项集都以「升序元组」这一种形态存在 # 连接与去重才有唯一表示 records [tuple(sorted(set(r))) for r in data[records]] min_cnt int(data[min_cnt]) # 事务矩阵行是记录、列是编号mark[t][c] 表示第 t 条记录里有没有第 c 号编号。 # 有了它某候选是不是这条记录的子集就退化成按列做逻辑与不必反复建集合 ids sorted({v for r in records for v in r}) pos {v: c for c, v in enumerate(ids)} mark np.zeros((len(records), len(ids)), dtypebool) for t, r in enumerate(records): for v in r: mark[t, pos[v]] True def count_support(itemset): 支持计数候选的所有编号列同时为真的记录条数。 cols [pos[v] for v in itemset] # (n, k) 沿列做与 - (n,), True 的个数就是包含该候选的记录数 return int(np.all(mark[:, cols], axis1).sum()) def gen_candidates(freq_prev): 由 G_{k-1} 生成 D_k先两两连接再用子集剪枝滤掉不可能频繁的候选。 known set(freq_prev) out set() for i in range(len(freq_prev)): for j in range(i 1, len(freq_prev)): left, right freq_prev[i], freq_prev[j] # 只有前 k-2 位完全相同、且末元素严格递增才连接 # 这样同一个 k-项集只会被它字典序最小的那对父集生成一次天然不重复 if left[:-1] ! right[:-1] or left[-1] right[-1]: continue merged left[:-1] (left[-1], right[-1]) # 频繁项集的任意子集必频繁反过来只要有一个 (k-1) 元子集不在 G_{k-1} # 这个候选就绝无可能频繁连数都不用数 if all(merged[:d] merged[d 1:] in known for d in range(len(merged))): out.add(merged) return sorted(out) def gen_candidates(freq_prev): 由 G_{k-1} 生成 D_k先两两连接再用子集剪枝滤掉不可能频繁的候选。 known set(freq_prev) out set() for i in range(len(freq_prev)): for j in range(i 1, len(freq_prev)): left, right freq_prev[i], freq_prev[j] # 只有前 k-2 位完全相同、且末元素严格递增才连接 if left[:-1] ! right[:-1] or left[-1] right[-1]: continue merged left[:-1] (left[-1], right[-1]) # 频繁项集的任意子集必频繁反过来只要有一个 (k-1) 元子集不在 G_{k-1} # 主循环与输出 results [] # 用于存储所有层级的频繁项集 # 1. 初始化 k1 的频繁项集 # 遍历所有唯一的零件编号计算支持度 freq_k [] for v in ids: if count_support((v,)) min_cnt: freq_k.append((v,)) # 2. 迭代挖掘 (k2, 3, ...) while freq_k: # 将当前层级的频繁项集加入结果列表 results.append(freq_k) # 生成下一层级的候选集 candidates gen_candidates(freq_k) # 扫描数据库计算支持度并筛选出新的频繁项集 freq_k [] for c in candidates: if count_support(c) min_cnt: freq_k.append(c) # 3. 格式化输出 # 题目要求按层级输出每行一个项集 output_lines [] for level_items in results: for item in level_items: # 将元组转换为列表形式的字符串例如 (1, 2) - [1, 2] output_lines.append(str(list(item))) print(\n.join(output_lines))java版本import java.util.*; import java.util.stream.Collectors; public class Apriori { // 全局变量事务矩阵模拟 Python 的 mark和编号映射 private static BitSet[] mark; // mark[t] 表示第 t 条记录包含哪些零件 private static MapInteger, Integer posMap; // 零件号 - 矩阵列索引 public static void main(String[] args) { Scanner sc new Scanner(System.in); // 1. 读取输入 (假设输入是 JSON 格式这里简化解析逻辑) // 实际比赛中可能需要用 Jackson/Gson这里为了简洁手动模拟解析结构 // 假设输入格式如题目描述第一行 min_cnt后续行记录 // *注意如果题目严格是 JSON 输入请使用 JSON 库解析* // 为演示逻辑这里模拟读取过程 int minCnt sc.nextInt(); ListListInteger rawRecords new ArrayList(); while (sc.hasNextInt()) { ListInteger rec new ArrayList(); // 假设每行第一个数字是该行元素个数或者直接读到换行 // 这里简化为读取直到换行。若题目格式不同需调整读取逻辑 String line sc.nextLine().trim(); if(line.isEmpty()) continue; for(String s : line.split(\\s)) { if(!s.isEmpty()) rec.add(Integer.parseInt(s)); } if(!rec.isEmpty()) rawRecords.add(rec); } // 2. 数据预处理 (对应 Python: records [tuple(sorted(set(r)))...]) Listint[] records new ArrayList(); SetInteger allIdsSet new HashSet(); for (ListInteger r : rawRecords) { // 去重并排序 int[] arr r.stream().distinct().sorted().mapToInt(i-i).toArray(); records.add(arr); for(int v : arr) allIdsSet.add(v); } // 3. 构建映射与矩阵 (对应 Python: ids, pos, mark) ListInteger ids new ArrayList(allIdsSet); Collections.sort(ids); posMap new HashMap(); for (int i 0; i ids.size(); i) posMap.put(ids.get(i), i); mark new BitSet[records.size()]; for (int t 0; t records.size(); t) { mark[t] new BitSet(ids.size()); for (int v : records.get(t)) { mark[t].set(posMap.get(v)); } } // 4. 初始化 k1 的频繁项集 Listint[] freqPrev new ArrayList(); for (int id : ids) { if (countSupport(new int[]{id}) minCnt) { freqPrev.add(new int[]{id}); } } ListListint[] results new ArrayList(); results.add(freqPrev); // 5. 主循环 (对应 Python: while True...) while (!freqPrev.isEmpty()) { Listint[] candidates genCandidates(freqPrev); Listint[] freqCurr new ArrayList(); for (int[] cand : candidates) { if (countSupport(cand) minCnt) { freqCurr.add(cand); } } if (freqCurr.isEmpty()) break; results.add(freqCurr); freqPrev freqCurr; } // 6. 输出结果 System.out.println(results.size()); // 输出层数 for (Listint[] layer : results) { for (int[] item : layer) { // 格式化输出: id1 id2 ... count String idsStr Arrays.stream(item).mapToObj(String::valueOf).collect(Collectors.joining( )); System.out.println(idsStr countSupport(item)); } } } // 支持度计数 (对应 Python: count_support) // 利用 BitSet.and() 快速判断子集 private static int countSupport(int[] itemset) { if (itemset.length 0) return 0; // 获取第一个元素的位图作为基准 BitSet common (BitSet) mark[0].clone(); // 优化实际上应该找一个包含该 itemset 的记录开始或者遍历所有记录 int count 0; // 遍历所有事务记录 for (BitSet transaction : mark) { boolean isSubset true; for (int val : itemset) { if (!transaction.get(posMap.get(val))) { isSubset false; break; } } if (isSubset) count; } return count; } // 生成候选集 (对应 Python: gen_candidates) private static Listint[] genCandidates(Listint[] freqPrev) { SetString knownSet new HashSet(); // 用于快速查找子集是否存在 for (int[] p : freqPrev) knownSet.add(Arrays.toString(p)); SetString outSet new LinkedHashSet(); // 保持顺序且去重 Listint[] outList new ArrayList(); int size freqPrev.size(); for (int i 0; i size; i) { for (int j i 1; j size; j) { int[] left freqPrev.get(i); int[] right freqPrev.get(j); // 剪枝条件前 k-2 项必须相同 boolean canJoin true; for (int k 0; k left.length - 1; k) { if (left[k] ! right[k]) { canJoin false; break; } } if (canJoin left[left.length - 1] right[right.length - 1]) { // 连接操作 int[] merged new int[left.length 1]; System.arraycopy(left, 0, merged, 0, left.length); merged[merged.length - 1] right[right.length - 1]; // 子集剪枝 (Apriori Property) // 检查 merged 的所有 (k-1) 子集是否都在 freqPrev 中 boolean valid true; for (int d 0; d merged.length; d) { // 构造去掉第 d 个元素的子集 int[] sub new int[merged.length - 1]; System.arraycopy(merged, 0, sub, 0, d); System.arraycopy(merged, d 1, sub, d, merged.length - 1 - d); if (!knownSet.contains(Arrays.toString(sub))) { valid false; break; } } if (valid) { outList.add(merged); } } } } return outList; } }题目2双班次收益差 27届京东、联想秋招笔试刷题总结算法篇
1.联想题目邻项合并归序时间2026年8月7日题目内容产线质检得到一条长度为n的整型读数序列v1, v2, ..., vn。允许反复选取一对相邻读数将其合并为一个新读数新读数的值为两者之和。需要使整条序列从左至右保持非降任意相邻两项中左侧读数的数值不超过右侧读数。请计算达成上述目标所需的最少合并次数。输入描述首先输入一行一个正整数q表示随后有多少条记录。对于每条记录第一行输入一个正整数n表示该条记录中读数的个数。第二行输入n个正整数v1, v2, ..., vn表示读数序列。数据范围1 q 201 n 4 * 10^31 vi 10^9输出描述按记录顺序对每条记录各输出一行一个非负整数表示该条记录对应的最少合并次数。样例输入 1复制代码123456733213412343516样例输出 1复制代码123101样例说明 1第一条记录将v2与v3合并得到[2, 4]满足2 4共合并 1 次。第二条记录序列[1, 2, 3, 4]本身已单调不减无需合并。第三条记录将v1与v2合并得到[6, 6]共合并 1 次。样例输入 2复制代码1231532145样例输出 2复制代码11样例说明 2将中间的2与1合并得到[3, 3, 4, 5]相邻读数依次满足3 3 4 5共合并 1 次。题解第一步核心思维转换最重要的一步题目问的是最少需要合并多少次我们可以换个角度想最多能把数组切成多少段举个例子原数组[3, 2, 1, 4, 5]一共 5 个数n5。如果我们能把它切成 4 段比如[3],[2,1],[4],[5]段和分别是 3, 3, 4, 5满足递增。既然切成了 4 段说明我们只需要把原本 5 个数合并成 4 个数也就是只需要合并 1 次把 2 和 1 合并。核心公式最少合并次数 总长度 n - 最多能切出的段数 k第二步贪心策略怎么切为了让切出的段数尽可能多每一段就应该尽可能短。所以我们的策略是从左往右扫只要当前这一段的和 ≥≥ 上一段的和就立刻“切一刀”开启新的一段第三步Java 代码逐行解释import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int q sc.nextInt(); // 读取测试用例的数量有几组数据 // 循环处理每一组数据 while (q-- 0) { int n sc.nextInt(); // 读取当前数组的长度 n long[] v new long[n]; // 用 long 数组存储数据防止累加时 int 溢出 // 循环读取 n 个数字 for (int i 0; i n; i) { v[i] sc.nextLong(); } // 【核心逻辑开始】 long lastSum 0; // 记录“上一段”的总和初始为 0第一段前面没有段所以要求最宽松 long curSum 0; // 记录“当前正在累积的这一段”的总和 int count 0; // 记录成功切出了多少段 for (int i 0; i n; i) { curSum v[i]; // 把当前数字加到当前段的总和中 // 核心判断如果当前段的和 上一段的和说明满足非降条件了 if (curSum lastSum) { count; // 成功切出一段段数加 1 lastSum curSum; // 更新“上一段的和”下一段要拿它作比较 curSum 0; // 【关键】清零当前和准备开始累积下一段 } // 如果 curSum lastSum说明当前段还不够大什么都不做继续往后看下一个数字 } // 循环结束后最后剩下的数字如果没凑够会自动并入上一段因为题目保证有解 // 最终答案总长度 - 最多段数 最少合并次数 System.out.println(n - count); } } }京东题目1抽检共现项集时间2026年8.15日好的这道题其实是在模拟一个经典的数据挖掘算法。我们可以把它想象成超市的“购物篮分析”——比如发现“买啤酒的人通常也会买尿布”。通俗解释题目要做什么想象你是一个工厂的质检员手里有一大堆“故障报告单”。每张报告单上列出了这次故障中同时坏掉的几个零件比如[零件1, 零件2]。老板想知道哪些零件经常“结伴”坏掉但是老板有个要求只有当这组零件同时出现的次数超过一定数量题目叫min_cnt时才算数。偶尔一两次一起坏的不算我们要找的是那种“铁哥们”关系。举个例子假设min_cnt 2至少出现2次才算。记录1[1, 2, 3]记录2[1, 2, 4]记录3[1, 3, 5]分析过程单个零件零件1出现了3次零件2出现了2次... 它们都达标了。两个零件组合[1, 2]在记录1和2都出现了共2次达标[1, 3]在记录1和3都出现了共2次达标[2, 3]只在记录1出现1次淘汰三个零件组合[1, 2, 3]只在记录1出现淘汰最终你要交给老板的名单按规则排序先列出所有达标的单个零件再列出达标的两个零件组合以此类推。我们应该做什么解题思路这就用到了题目提到的Apriori 算法。它的核心思想非常聪明叫作**“层层递进不行就砍”**。我们不需要把1,2,3,4,5的所有组合都试一遍那样太慢了而是分步骤来第一步海选“单兵作战”强的k1先统计每个零件单独出现的次数。如果次数 min_cnt直接扔掉因为它连单打独斗都不行跟别人组队肯定更不行。剩下的就是频繁1项集 ($L_1$)。第二步组队“双人搭档”k2拿上一步剩下的零件两两配对。关键剪枝重点在配对之前先看一眼它的“子集”。比如我们要检查[A, B]如果A或者B在第一步已经被淘汰了那[A, B]绝对不可能达标直接不用算省时间对剩下的候选组合去原始数据里数数看它们一起出现了几次。次数够的留下不够的扔掉。这就是频繁2项集 ($L_2$)。第三步组建“三人小队”k3拿上一步留下的“双人搭档”尝试合并成三人组。同样利用剪枝如果[A, B, C]里面的[A, B]在上一步被淘汰了那[A, B, C]也不用看了。数数留强汰弱。第四步循环直到结束一直这样k4,k5... 直到某一轮再也组不出合格的队伍为止。第五步整理输出把刚才每一轮留下的“精英团队”收集起来。排序规则先比人数少的排前面人数一样比零件编号字典序。因为我们是按k从小到大算的所以天然就是排好序的。总结这道题就是让你写代码实现这个**“筛选 - 组队 - 再筛选 - 再组队”的过程。难点不在于算法原理而在于如何高效地表示集合**比如用元组或位运算以及如何快速判断子集是否存在剪枝。python版本# 抽检共现项集 - Apriori 频繁项集挖掘 import json import numpy as np data json.loads(input()) # 同一条抽检记录里的编号互异排好序后所有项集都以「升序元组」这一种形态存在 # 连接与去重才有唯一表示 records [tuple(sorted(set(r))) for r in data[records]] min_cnt int(data[min_cnt]) # 事务矩阵行是记录、列是编号mark[t][c] 表示第 t 条记录里有没有第 c 号编号。 # 有了它某候选是不是这条记录的子集就退化成按列做逻辑与不必反复建集合 ids sorted({v for r in records for v in r}) pos {v: c for c, v in enumerate(ids)} mark np.zeros((len(records), len(ids)), dtypebool) for t, r in enumerate(records): for v in r: mark[t, pos[v]] True def count_support(itemset): 支持计数候选的所有编号列同时为真的记录条数。 cols [pos[v] for v in itemset] # (n, k) 沿列做与 - (n,), True 的个数就是包含该候选的记录数 return int(np.all(mark[:, cols], axis1).sum()) def gen_candidates(freq_prev): 由 G_{k-1} 生成 D_k先两两连接再用子集剪枝滤掉不可能频繁的候选。 known set(freq_prev) out set() for i in range(len(freq_prev)): for j in range(i 1, len(freq_prev)): left, right freq_prev[i], freq_prev[j] # 只有前 k-2 位完全相同、且末元素严格递增才连接 # 这样同一个 k-项集只会被它字典序最小的那对父集生成一次天然不重复 if left[:-1] ! right[:-1] or left[-1] right[-1]: continue merged left[:-1] (left[-1], right[-1]) # 频繁项集的任意子集必频繁反过来只要有一个 (k-1) 元子集不在 G_{k-1} # 这个候选就绝无可能频繁连数都不用数 if all(merged[:d] merged[d 1:] in known for d in range(len(merged))): out.add(merged) return sorted(out) def gen_candidates(freq_prev): 由 G_{k-1} 生成 D_k先两两连接再用子集剪枝滤掉不可能频繁的候选。 known set(freq_prev) out set() for i in range(len(freq_prev)): for j in range(i 1, len(freq_prev)): left, right freq_prev[i], freq_prev[j] # 只有前 k-2 位完全相同、且末元素严格递增才连接 if left[:-1] ! right[:-1] or left[-1] right[-1]: continue merged left[:-1] (left[-1], right[-1]) # 频繁项集的任意子集必频繁反过来只要有一个 (k-1) 元子集不在 G_{k-1} # 主循环与输出 results [] # 用于存储所有层级的频繁项集 # 1. 初始化 k1 的频繁项集 # 遍历所有唯一的零件编号计算支持度 freq_k [] for v in ids: if count_support((v,)) min_cnt: freq_k.append((v,)) # 2. 迭代挖掘 (k2, 3, ...) while freq_k: # 将当前层级的频繁项集加入结果列表 results.append(freq_k) # 生成下一层级的候选集 candidates gen_candidates(freq_k) # 扫描数据库计算支持度并筛选出新的频繁项集 freq_k [] for c in candidates: if count_support(c) min_cnt: freq_k.append(c) # 3. 格式化输出 # 题目要求按层级输出每行一个项集 output_lines [] for level_items in results: for item in level_items: # 将元组转换为列表形式的字符串例如 (1, 2) - [1, 2] output_lines.append(str(list(item))) print(\n.join(output_lines))java版本import java.util.*; import java.util.stream.Collectors; public class Apriori { // 全局变量事务矩阵模拟 Python 的 mark和编号映射 private static BitSet[] mark; // mark[t] 表示第 t 条记录包含哪些零件 private static MapInteger, Integer posMap; // 零件号 - 矩阵列索引 public static void main(String[] args) { Scanner sc new Scanner(System.in); // 1. 读取输入 (假设输入是 JSON 格式这里简化解析逻辑) // 实际比赛中可能需要用 Jackson/Gson这里为了简洁手动模拟解析结构 // 假设输入格式如题目描述第一行 min_cnt后续行记录 // *注意如果题目严格是 JSON 输入请使用 JSON 库解析* // 为演示逻辑这里模拟读取过程 int minCnt sc.nextInt(); ListListInteger rawRecords new ArrayList(); while (sc.hasNextInt()) { ListInteger rec new ArrayList(); // 假设每行第一个数字是该行元素个数或者直接读到换行 // 这里简化为读取直到换行。若题目格式不同需调整读取逻辑 String line sc.nextLine().trim(); if(line.isEmpty()) continue; for(String s : line.split(\\s)) { if(!s.isEmpty()) rec.add(Integer.parseInt(s)); } if(!rec.isEmpty()) rawRecords.add(rec); } // 2. 数据预处理 (对应 Python: records [tuple(sorted(set(r)))...]) Listint[] records new ArrayList(); SetInteger allIdsSet new HashSet(); for (ListInteger r : rawRecords) { // 去重并排序 int[] arr r.stream().distinct().sorted().mapToInt(i-i).toArray(); records.add(arr); for(int v : arr) allIdsSet.add(v); } // 3. 构建映射与矩阵 (对应 Python: ids, pos, mark) ListInteger ids new ArrayList(allIdsSet); Collections.sort(ids); posMap new HashMap(); for (int i 0; i ids.size(); i) posMap.put(ids.get(i), i); mark new BitSet[records.size()]; for (int t 0; t records.size(); t) { mark[t] new BitSet(ids.size()); for (int v : records.get(t)) { mark[t].set(posMap.get(v)); } } // 4. 初始化 k1 的频繁项集 Listint[] freqPrev new ArrayList(); for (int id : ids) { if (countSupport(new int[]{id}) minCnt) { freqPrev.add(new int[]{id}); } } ListListint[] results new ArrayList(); results.add(freqPrev); // 5. 主循环 (对应 Python: while True...) while (!freqPrev.isEmpty()) { Listint[] candidates genCandidates(freqPrev); Listint[] freqCurr new ArrayList(); for (int[] cand : candidates) { if (countSupport(cand) minCnt) { freqCurr.add(cand); } } if (freqCurr.isEmpty()) break; results.add(freqCurr); freqPrev freqCurr; } // 6. 输出结果 System.out.println(results.size()); // 输出层数 for (Listint[] layer : results) { for (int[] item : layer) { // 格式化输出: id1 id2 ... count String idsStr Arrays.stream(item).mapToObj(String::valueOf).collect(Collectors.joining( )); System.out.println(idsStr countSupport(item)); } } } // 支持度计数 (对应 Python: count_support) // 利用 BitSet.and() 快速判断子集 private static int countSupport(int[] itemset) { if (itemset.length 0) return 0; // 获取第一个元素的位图作为基准 BitSet common (BitSet) mark[0].clone(); // 优化实际上应该找一个包含该 itemset 的记录开始或者遍历所有记录 int count 0; // 遍历所有事务记录 for (BitSet transaction : mark) { boolean isSubset true; for (int val : itemset) { if (!transaction.get(posMap.get(val))) { isSubset false; break; } } if (isSubset) count; } return count; } // 生成候选集 (对应 Python: gen_candidates) private static Listint[] genCandidates(Listint[] freqPrev) { SetString knownSet new HashSet(); // 用于快速查找子集是否存在 for (int[] p : freqPrev) knownSet.add(Arrays.toString(p)); SetString outSet new LinkedHashSet(); // 保持顺序且去重 Listint[] outList new ArrayList(); int size freqPrev.size(); for (int i 0; i size; i) { for (int j i 1; j size; j) { int[] left freqPrev.get(i); int[] right freqPrev.get(j); // 剪枝条件前 k-2 项必须相同 boolean canJoin true; for (int k 0; k left.length - 1; k) { if (left[k] ! right[k]) { canJoin false; break; } } if (canJoin left[left.length - 1] right[right.length - 1]) { // 连接操作 int[] merged new int[left.length 1]; System.arraycopy(left, 0, merged, 0, left.length); merged[merged.length - 1] right[right.length - 1]; // 子集剪枝 (Apriori Property) // 检查 merged 的所有 (k-1) 子集是否都在 freqPrev 中 boolean valid true; for (int d 0; d merged.length; d) { // 构造去掉第 d 个元素的子集 int[] sub new int[merged.length - 1]; System.arraycopy(merged, 0, sub, 0, d); System.arraycopy(merged, d 1, sub, d, merged.length - 1 - d); if (!knownSet.contains(Arrays.toString(sub))) { valid false; break; } } if (valid) { outList.add(merged); } } } } return outList; } }题目2双班次收益差