做做记录 整理错题26.08.15 京东第一题题目给定一批离散交易记录和一个最小支持计数 min_sup请你实现 Apriori 算法挖掘所有频繁项集。1. 输入定义transactions: 二维列表transactions[i] 是一条交易的整数 item 编号列表元素不重复1 ≤ i ≤ 20列表 transactions[i] 的数据元素数量不超过 4min_sup: 是最小支持计数 (≥ 1, 整数)2. Apriori 过程候选生成k1: 统计所有交易中每个单项的总出现次数 → 频繁 1-项集集合 L₁k≥2: 用 Lₖ₋₁ 两两连接并剪枝生成 Cₖ连接条件: 前 k-2 个元素相同最后一个元素升序剪枝: 若 Cₖ 的任何 (k-1) 子集不在 Lₖ₋₁ 中则丢弃扫描计数对每条交易检查候选集是否是交易的子集 Cₖ 中所有候选的支持计数筛选满足 support ≥ min_sup 的候选进入 Lₖ直到 Lₖ 为空终止合并全部 Lₖ 得到频繁项集全集 F3. 输出排序先按项集大小升序若大小相同则按字典序 (item 升序比较)每个项集输出为升序 item 列表并附带支持计数输入描述{ transactions: [[1,2,3], [1,2], [2,3], [1,3], [1,2,3]], min_sup: 2 }输出描述单行 JSON 数组元素结构 [[item1,...], support]示例 [[[1], 4],[[2], 4],[[3], 4],[[1, 2], 3],[[1, 3], 3],[[2, 3], 3],[[1, 2, 3], 2]]考试时的想法k是什么support是什么“transactions[i]是一条交易的整数 item 编号列表” 这是说列是item还是行是item啊写题目能不能给我写清楚一点啊只限制python作答。不是推荐系统方向这个算法虽然有印象但不多。花了25min试图理解题目但最终放弃了直接没写。复盘》》》》》》》》》》》》》》》》》先来理解下题目《《《《《《《《《《《《《《《《《《输入是什么每行代表 一张购物小票transactions[0] [1, 2, 3]第 1 张小票买了 1 号、2 号、3 号商品。transactions[1] [1, 2]第 2 张小票买了 1 号、2 号商品。k是什么k 代表这个组合里包含几个商品。k为1时统计所有交易中每个单项也就是个数为1的总出现次数例如L_1 { [1], [2], [3]}k≥2: 用 Lₖ₋₁ 两两连接并剪枝生成 Cₖ连接条件: 前 k-2 个元素相同最后一个元素升序剪枝: 若Cₖ 的任何 (k-1) 子集不在 Lₖ₋₁ 中则丢弃现在看看k等于2时的内容连接生成候选集 C_2。前 0个元素相同最后一个元素升序。实际操作前 0 个元素相同意味着没有约束只要两两组合并且保证组合里小数字在前大数字在后升序即可得出候选集C_2 { [1, 2], [1, 3], [2, 3] }任何 (k-1) 子集是指从某个长度为 k 的候选项集中任意去掉 1 个元素后剩下的所有包含 (k-1) 个元素的子组合。剪枝如果候选集的某个子集连在上一步的 L_k-1里都没有说明那个子集本身就不频繁那这个候选集必然也不频繁直接丢弃现在看看k等于3时的内容连接生成候选集 C_3。前 1 个元素必须相同且最后一个元素升序。实际操作看 L_2 中哪两个组合的第一个元素前 1 个元素相同拿 [1, 2] 和 [1, 3] 比较第一个元素都是 1相同且最后一个元素 2 3满足升序。把它们拼起来得到候选集[1, 2, 3]。拿 [1, 2] 和 [2, 3] 比较第一个元素是 1 和 2不同不能连接。拿 [1, 3] 和 [2, 3] 比较第一个元素是 1 和 2不同不能连接。得出候选集 C_3 { [1, 2, 3] }对每条交易检查候选集是否是交易的子集 Cₖ 中所有候选的支持计数在所有交易小票中查找 [1, 2, 3] 出现的次数。[1, 2, 3] 出现的次数为 2 合格。得到 L_3 { [1, 2, 3] }代码诶我来写吗真的假的......import sys import json from collections import Counter from itertools import combinations def solve(): # 读取所有标准输入内容 (ACM 模式) input_data sys.stdin.read().strip() if not input_data: return # 解析 JSON 输入 data json.loads(input_data) transactions data[transactions] min_sup data[min_sup] # 将每条交易转为集合以便快速取交集/判断子集 trans [set(t) for t in transactions] # 1. 生成频繁 1-项集 L1 item_counts Counter() for t in trans: for item in t: item_counts[(item,)] 1 current_L {item: count for item, count in item_counts.items() if count min_sup} all_frequent_itemsets dict(current_L) k 2 while current_L: # A. 连接生成候选 C_k prev_itemsets sorted(list(current_L.keys())) C_k [] n len(prev_itemsets) for i in range(n): for j in range(i 1, n): itemset1 prev_itemsets[i] itemset2 prev_itemsets[j] # 连接条件前 k-2 个元素相同 if itemset1[:k-2] itemset2[:k-2]: candidate itemset1 (itemset2[-1],) # B. 剪枝 (Pruning) is_valid True for sub in combinations(candidate, k - 1): if sub not in current_L: is_valid False break if is_valid: C_k.append(candidate) if not C_k: break # C. 扫描计数 candidate_counts {c: 0 for c in C_k} for t in trans: for candidate in C_k: if set(candidate).issubset(t): candidate_counts[candidate] 1 # D. 筛选频繁项集 L_k current_L {c: count for c, count in candidate_counts.items() if count min_sup} all_frequent_itemsets.update(current_L) k 1 # 按照规则排序 # 1. 项集大小升序 # 2. 字典序 (item 升序) sorted_itemsets sorted( all_frequent_itemsets.items(), keylambda x: (len(x[0]), x[0]) ) # 转换为指定的输出结构: [[ [item1, ...], support ], ...] result [[list(itemset), count] for itemset, count in sorted_itemsets] # 单行输出 JSON 字符串格式紧凑 print(json.dumps(result, separators(, , : ))) if __name__ __main__: solve()第二题题目给你一个长度为2 * n的整数数组。你需要将nums分成两个长度为n的数组分别求出两个数组的和并最小化两个数组和之差的绝对值。nums中每个元素都需要放入两个数组之一。请你返回最小的数组和之差。1 n 15nums.length 2 * n-10e9 nums[i] 10e92035. 将数组分成两个数组并最小化数组和的差 - 力扣LeetCode考试时的想法动态规划但这个状态公式是什么直接二进制然后0和1对半开的数字留下作为方案0代表左边1代表右边然后运行每份方案看最小【其实也会超时】难道是状态压缩dp但是没怎么自己做出来过.....【其实会MLE】算了 暴力递归吧 能拿一点分是一点class Solution { public: long long ans1e18; long long solve(int n,int now,int req,long long value,long long sum,vectorint nums){ if(reqn/2)return abs(sum-2*value); if(n-nowreqn/2)return 1e18; ansmin(ans,solve(n,now1,req1,value(long long)nums[now],sum,nums)); ansmin(ans,solve(n,now1,req,value,sum,nums)) ; return 1e18; } int minimumDifference(vectorint nums) { int nnums.size(); long long sum0; for(int i0;in;i){ sumsum(long long)nums[i]; } solve(n,0,0,0,sum,nums); return ans; } };复盘暴力递归复杂度是2^30 (1e9) 级别。所以将数组一分为二在左半部分用递归生成所有可能的选择k个元素时的和并按选择的个数分类。对右半部分求出的和进行排序以便利用二分查找快速匹配左半部分简单来说就是左边和右边分别是二维表格每一行的列表里的元素是抓取了同样个数的数字的和然后每一行分别排序然后二分查找两边的和加起来最接近平均数就好了。代码知道算法后光写代码就花了一小时左右......class Solution { public: long long ans1e18; void solve(int start,int endd, int req,long long value,vectorint nums,vector vectorlong long sum ){ if (startendd){sum[req].push_back(value); return;} solve(start1,endd,req1,valuenums[start],nums,sum); solve(start1,endd,req,value,nums,sum); } int minimumDifference(vectorint nums) { int nnums.size(); long long sum0; int halfnums.size()/2; vector vectorlong long left_sum(half1),right_sum(half1); for(int i0;in;i){ sumsum(long long)nums[i]; } solve(0,n/2,0,0,nums,left_sum); solve(n/2,n,0,0,nums,right_sum); long long ans1e18; for(int k0;khalf;k){//我要竖着遍历这个vector sort(right_sum[half-k].begin(),right_sum[half-k].end()); for(int i0;ileft_sum[k].size();i){ auto ra lower_bound(right_sum[half-k].begin(), right_sum[half-k].end(), sum/2-left_sum[k][i]); if(ra!right_sum[half-k].end()){ ansmin(ans,abs(sum-2*(*raleft_sum[k][i]))); } if(ra!right_sum[half-k].begin()){ --ra; ansmin(ans,abs(sum-2*(*raleft_sum[k][i]))); } } } return ans; } };