做做记录 整理错题
26.08.15 京东
第一题
题目
给定一批离散交易记录和一个最小支持计数 min_sup，请你实现 Apriori 算法挖掘所有频繁项集。
1. 输入定义
transactions: 二维列表，transactions[i] 是一条交易的整数 item 编号列表，元素不重复，1 ≤ i ≤ 20，列表 transactions[i] 的数据元素数量不超过 4
min_sup: 是最小支持计数 (≥ 1, 整数)
2. Apriori 过程
候选生成
k=1: 统计所有交易中每个单项的总出现次数 → 频繁 1-项集集合 L₁
k≥2: 用 Lₖ₋₁ 两两连接并剪枝生成 Cₖ
连接条件: 前 k-2 个元素相同，最后一个元素升序
剪枝: 若 Cₖ 的任何 (k-1) 子集不在 Lₖ₋₁ 中，则丢弃
扫描计数
对每条交易，检查候选集是否是交易的子集 Cₖ 中所有候选的支持计数
筛选
满足 support ≥ min_sup 的候选进入 Lₖ
直到 Lₖ 为空终止，合并全部 Lₖ 得到频繁项集全集 F
3. 输出排序
先按项集大小升序
若大小相同则按字典序 (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(), key=lambda 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] <= 10e9
2035. 将数组分成两个数组并最小化数组和的差 - 力扣（LeetCode）
考试时的想法
动态规划？但这个状态公式是什么？
直接二进制，然后0和1对半开的数字留下作为方案，0代表左边，1代表右边，然后运行每份方案看最小？【其实也会超时】
难道是状态压缩dp？但是没怎么自己做出来过.....【其实会MLE】
算了 暴力递归吧 能拿一点分是一点
class Solution { public: long long ans=1e18; long long solve(int n,int now,int req,long long value,long long sum,vector<int>& nums){ if(req==n/2)return abs(sum-2*value); if(n-now+req<n/2)return 1e18; ans=min(ans,solve(n,now+1,req+1,value+(long long)nums[now],sum,nums)); ans=min(ans,solve(n,now+1,req,value,sum,nums)) ; return 1e18; } int minimumDifference(vector<int>& nums) { int n=nums.size(); long long sum=0; for(int i=0;i<n;i++){ sum=sum+(long long)nums[i]; } solve(n,0,0,0,sum,nums); return ans; } };复盘
暴力递归复杂度是2^30 (1e9) 级别。所以，将数组一分为二，在左半部分用递归生成所有可能的选择k个元素时的和，并按选择的个数分类。对右半部分求出的和进行排序，以便利用二分查找快速匹配左半部分
简单来说，就是左边和右边分别是二维表格，每一行的列表里的元素是抓取了同样个数的数字的和
然后每一行分别排序，然后二分查找
两边的和加起来最接近平均数就好了。
代码
知道算法后，光写代码就花了一小时左右......
class Solution { public: long long ans=1e18; void solve(int start,int endd, int req,long long value,vector<int>& nums,vector< vector<long long> >& sum ){ if (start==endd){sum[req].push_back(value); return;} solve(start+1,endd,req+1,value+nums[start],nums,sum); solve(start+1,endd,req,value,nums,sum); } int minimumDifference(vector<int>& nums) { int n=nums.size(); long long sum=0; int half=nums.size()/2; vector< vector<long long> > left_sum(half+1),right_sum(half+1); for(int i=0;i<n;i++){ sum=sum+(long long)nums[i]; } solve(0,n/2,0,0,nums,left_sum); solve(n/2,n,0,0,nums,right_sum); long long ans=1e18; for(int k=0;k<=half;k++){//我要竖着遍历这个vector sort(right_sum[half-k].begin(),right_sum[half-k].end()); for(int i=0;i<left_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()){ ans=min(ans,abs(sum-2*(*ra+left_sum[k][i]))); } if(ra!=right_sum[half-k].begin()){ --ra; ans=min(ans,abs(sum-2*(*ra+left_sum[k][i]))); } } } return ans; } };
