题目难度自动标注：用机器学习预测“这道题有多难“

题目难度自动标注用机器学习预测这道题有多难一、为什么 LeetCode 的难度标签经常不准LeetCode 把题目分成 Easy、Medium、Hard 三个等级但实际刷题体验却不是线性的。最长回文子串标着 Medium难度远超不少 Hard 题接雨水是 Hard思路理清后反而比某些 Medium 更好写。更糟的是同一道寻路题对于熟悉 BFS 的用户来说最多算 Medium对没接触过图的初学者则是 Hard——难度不只是题目属性更和用户背景相关。一个优秀的刷题系统不能完全依赖平台的静态标签。它需要动态评估一道题对特定用户群体的真实难度用于推荐引擎下一道推荐什么难度、学习路径规划什么时候可以挑战 Hard、评测系统这个用户的得分相对于题目难度是高还是低。难度预测不是单因素的标签 → 难度映射。同一道 BFS 题如果约束条件从 n ≤ 100 放宽到 n ≤ 10^5难度直接翻倍如果测试样例覆盖了全部边界情况难度又降一档。所以特征工程必须同时覆盖题面复杂度和历史统计数据两个维度。二、特征工程什么样的题目难一道题的难体现在三个层面概念层涉及的数据结构和算法有多深前缀和 线段树 莫队算法实现层代码要写多长有多少个边界条件观察层核心 trick 需要多看穿几层包装一眼看出用 DP → 需要先转化为图 → 需要先建模import re import math import json from typing import List, Dict, Tuple from collections import Counter from dataclasses import dataclass, field dataclass class ProblemFeatures: 一道题的多维特征 # 文本特征 problem_len: int # 题面长度字符数 constraint_count: int # 约束条件数量 example_count: int # 样例数量 keyword_density: float # 算法关键词密度 # 结构特征 max_input_size: int # 最大输入规模 variable_count: int # 题面中出现的变量/符号数 nesting_depth: int # 约束条件嵌套深度 # 标签特征one-hot → 向量 data_structures: List[str] # [array, tree, graph] algorithms: List[str] # [dp, bfs, binary_search] # 统计特征从历史数据中获取 historical_pass_rate: float # 历史通过率 avg_solve_time_min: float # 平均解题时间分钟 class FeatureExtractor: 从题目原始数据中提取多维特征 特征分为四类 - 文本特征从题面文本中统计 - 结构特征分析约束条件和输入规模 - 标签特征从预设标签中编码 - 统计特征从历史提交数据中计算 # 算法关键词词典关键词 → 难度权重 ALGO_KEYWORDS { 暴力: 0.2, 枚举: 0.3, 双指针: 0.5, 滑动窗口: 0.6, 二分: 0.7, 贪心: 0.6, 动态规划: 1.0, dp: 1.0, 记忆化: 0.8, 回溯: 0.9, 深度优先: 0.7, 广度优先: 0.7, dfs: 0.7, bfs: 0.7, dijkstra: 1.2, 并查集: 0.8, 拓扑排序: 0.9, 线段树: 1.5, 树状数组: 1.3, 莫队: 1.8, 状态压缩: 1.4, 位运算: 0.8, 数学: 0.5, 数论: 1.0 } # 数据结构权重越复杂权重越高 DS_WEIGHTS { array: 0.2, string: 0.3, hashmap: 0.4, linked_list: 0.5, stack: 0.4, queue: 0.4, tree: 0.7, bst: 0.8, graph: 0.9, segment_tree: 1.5, fenwick: 1.3, trie: 0.9, disjoint_set: 0.8, heap: 0.6 } staticmethod def extract_text_features(description: str) - dict: 提取文本特征 题面长短本身是难度信号更长的题面通常意味着更复杂的情景描述。 但更重要的是关键词密度——如果一份题面里充满了动态规划 状态转移等词汇说明这道题的核心就是DP。 # 题面长度 problem_len len(description) # 约束条件数量通过匹配1 n 10^5等模式 constraint_pattern r\d\s*\s*\w\s*\s*\d constraints re.findall(constraint_pattern, description) # 样例数量通过匹配示例 1、Example 1等模式 example_pattern r(?:示例|Example|样例)\s*\d examples re.findall(example_pattern, description) # 关键词密度 keyword_hits 0 total_weight 0.0 desc_lower description.lower() for kw, weight in FeatureExtractor.ALGO_KEYWORDS.items(): count desc_lower.count(kw.lower()) if count 0: keyword_hits count total_weight count * weight keyword_density total_weight / max(keyword_hits, 1) if keyword_hits 0 else 0.0 return { problem_len: problem_len, constraint_count: len(constraints), example_count: len(examples), keyword_density: round(keyword_density, 4) } staticmethod def extract_structural_features( description: str, constraints: List[str] ) - dict: 提取结构特征 最大输入规模是难度上限的硬约束 - n ≤ 100 → O(n²) 能过 - n ≤ 10^5 → 必须 O(n log n) - n ≤ 10^9 → 需要 O(1) 或 O(log n) # 解析最大输入规模 max_input 0 size_pattern r(?:n|N|m|M)\s*[≤]\s*(\d(?:\^{[^}]}|e\d)?) matches re.findall(size_pattern, description) for m in matches: try: # 处理 10^5 这种指数表示 if ^ in m: base, exp m.split(^) val int(base) ** int(exp) elif e in m.lower(): val int(float(m)) else: val int(m) max_input max(max_input, val) except (ValueError, OverflowError): continue # 变量/符号数量题面中出现的 Python 风格的变量名 var_pattern r\b[a-z_][a-z0-9_]*\b variables set(re.findall(var_pattern, description)) # 嵌套深度通过分析约束条件的括号嵌套 nesting_depth 0 for c in constraints: depth 0 max_depth 0 for ch in c: if ch in ({[: depth 1 max_depth max(max_depth, depth) elif ch in )}]: depth max(0, depth - 1) nesting_depth max(nesting_depth, max_depth) return { max_input_size: max_input, variable_count: len(variables), nesting_depth: nesting_depth } staticmethod def encode_labels( data_structures: List[str], algorithms: List[str] ) - Tuple[float, float]: 编码标签特征为难度得分 每个标签有一个预设权重加权求和得到标签层面的难度估计。 ds_score sum( FeatureExtractor.DS_WEIGHTS.get(ds.lower(), 0.3) for ds in data_structures ) algo_score sum( FeatureExtractor.ALGO_KEYWORDS.get(algo.lower(), 0.3) for algo in algorithms ) return round(ds_score, 4), round(algo_score, 4) classmethod def extract( cls, problem_id: int, description: str, constraints: List[str], data_structures: List[str], algorithms: List[str], historical_pass_rate: float 0.5, avg_solve_time_min: float 20.0 ) - ProblemFeatures: 提取所有维度的特征 text_feat cls.extract_text_features(description) struct_feat cls.extract_structural_features(description, constraints) return ProblemFeatures( problem_lentext_feat[problem_len], constraint_counttext_feat[constraint_count], example_counttext_feat[example_count], keyword_densitytext_feat[keyword_density], max_input_sizestruct_feat[max_input_size], variable_countstruct_feat[variable_count], nesting_depthstruct_feat[nesting_depth], data_structuresdata_structures, algorithmsalgorithms, historical_pass_rateround(historical_pass_rate, 4), avg_solve_time_minround(avg_solve_time_min, 2) )特征的选择原则是可解释性和覆盖度的平衡。关键词密度反映题目说了什么最大输入规模反映算法必须达到什么复杂度历史通过率反映别人做这道题的真实体验。三者组合才能给出准确的难度预测。三、模型训练LightGBM 用于数值回归难度预测本质上是回归问题——输出一个 0.0~10.0 的连续值而非 Easy/Medium/Hard 的离散分类。选择 LightGBM 而非深度神经网络的原因特征量少几十维GBDT 足够捕捉非线性关系可解释性强可以看到每个特征的贡献度训练快1000 道题的训练在单机 CPU 上几秒完成import numpy as np from sklearn.model_selection import train_test_split from sklearn.metrics import mean_absolute_error, r2_score class DifficultyPredictor: 基于 LightGBM 的题目难度预测器 输入ProblemFeatures → 特征向量~30维 输出连续难度分0.0-10.0 置信度 def __init__(self): self.model None self.feature_names [] self.scaler_mean 0.0 self.scaler_std 1.0 def _features_to_vector(self, feat: ProblemFeatures) - np.ndarray: 将 ProblemFeatures 转为固定维度的特征向量 vec [] # 数值特征标准化处理 vec.append(feat.problem_len / 5000) # 归一化到 [0, 1] vec.append(feat.constraint_count / 10) vec.append(feat.example_count / 5) vec.append(feat.keyword_density) vec.append(math.log2(max(feat.max_input_size, 1)) / 30) # log 缩放 vec.append(feat.variable_count / 100) vec.append(feat.nesting_depth / 5) vec.append(feat.historical_pass_rate) vec.append(min(feat.avg_solve_time_min / 60, 1.0)) # 截断到1小时 # 标签特征one-hot 编码关键标签 ds_set set(d.lower() for d in feat.data_structures) algo_set set(a.lower() for a in feat.algorithms) for ds in [array, tree, graph, linked_list, hashmap]: vec.append(1.0 if ds in ds_set else 0.0) for algo in [dp, bfs, dfs, binary_search, greedy, backtracking, two_pointers, sliding_window]: vec.append(1.0 if algo in algo_set else 0.0) return np.array(vec, dtypefloat) def train( self, features: List[ProblemFeatures], labels: List[float], learning_rate: float 0.05, n_estimators: int 200, max_depth: int 6, early_stopping_rounds: int 20 ) - dict: 训练 LightGBM 回归模型 Args: features: 训练样本的特征列表 labels: 真实难度分需人工标注或使用历史通过率反推 learning_rate: 学习率越低越稳但需要更多树 n_estimators: 决策树数量 max_depth: 最大深度防止过拟合GBDT 通常 ≤ 6 early_stopping_rounds: 早停轮次 Returns: 训练评估指标字典 try: import lightgbm as lgb except ImportError: # 如果没有 lightgbm使用 sklearn 的 GradientBoostingRegressor 作为降级方案 from sklearn.ensemble import GradientBoostingRegressor return self._train_sklearn( features, labels, learning_rate, n_estimators, max_depth ) # 构建特征矩阵 X np.array([self._features_to_vector(f) for f in features]) y np.array(labels, dtypefloat) # 分层采样划分训练/验证集按难度分层 X_train, X_val, y_train, y_val train_test_split( X, y, test_size0.2, stratifyNone, random_state42 ) # LightGBM 训练 train_data lgb.Dataset(X_train, labely_train) val_data lgb.Dataset(X_val, labely_val, referencetrain_data) params { objective: regression, metric: mae, learning_rate: learning_rate, num_leaves: 2 ** max_depth, max_depth: max_depth, feature_fraction: 0.8, bagging_fraction: 0.8, bagging_freq: 5, min_data_in_leaf: 5, verbose: -1 } self.model lgb.train( params, train_data, num_boost_roundn_estimators, valid_sets[train_data, val_data], valid_names[train, val], callbacks[lgb.early_stopping(early_stopping_rounds)] ) self.feature_names [ problem_len, constraint_count, example_count, keyword_density, log_input_size, variable_count, nesting_depth, pass_rate, solve_time, ds_array, ds_tree, ds_graph, ds_list, ds_hashmap, algo_dp, algo_bfs, algo_dfs, algo_bsearch, algo_greedy, algo_backtrack, algo_2ptr, algo_sliding ] # 验证集指标 y_pred self.model.predict(X_val) mae mean_absolute_error(y_val, y_pred) r2 r2_score(y_val, y_pred) return { mae: round(mae, 4), r2: round(r2, 4), feature_importance: dict(zip( self.feature_names, self.model.feature_importance().tolist() )) if hasattr(self.model, feature_importance) else {} } def predict(self, features: ProblemFeatures) - Tuple[float, float]: 预测难度分和置信度 Returns: (difficulty_score, confidence) if self.model is None: return 5.0, 0.0 vec self._features_to_vector(features).reshape(1, -1) pred float(self.model.predict(vec)[0]) # 置信度基于输入特征的完整性 confidence min( 0.9, features.keyword_density * 0.3 (1.0 - abs(features.historical_pass_rate - 0.5)) * 0.3 min(features.constraint_count / 5, 0.3) ) if hasattr(features, historical_pass_rate) else 0.6 return round(pred, 2), round(confidence, 2) def _train_sklearn( self, features, labels, lr, n_est, max_d ) - dict: 使用 sklearn 作为降级方案 from sklearn.ensemble import GradientBoostingRegressor X np.array([self._features_to_vector(f) for f in features]) y np.array(labels, dtypefloat) X_train, X_val, y_train, y_val train_test_split( X, y, test_size0.2, random_state42 ) self.model GradientBoostingRegressor( learning_ratelr, n_estimatorsn_est, max_depthmax_d, random_state42 ) self.model.fit(X_train, y_train) y_pred self.model.predict(X_val) return { mae: round(mean_absolute_error(y_val, y_pred), 4), r2: round(r2_score(y_val, y_pred), 4) }训练完成后预测器可以批量为题库中的所有题目生成难度分。这个过程不需要在线实时推理——用离线批处理把结果写入题目元数据即可推荐引擎和学习路径规划直接读缓存。四、边界分析难度预测的不确定性边界 1标签缺失或错误如果一道题没有任何算法标签新题上线时预测器只能依赖文本特征和结构特征。此时 keyword_density 可能为 0预测置信度会很低。处理方式返回默认难度 5.0标记为待人工标注。边界 2难度随时间漂移随着用户刷题水平提高一道题的通过率可能从 30% 涨到 60%。需要定期用最新历史数据重训模型——建议每周一次用滑动窗口最近 30 天数据。边界 3冷启动问题新题没有历史通过率和解题时间统计特征一栏全空。此时模型会过度依赖文本特征——而文本特征本身有噪声。解决方式使用半监督学习先用老题训练新题上线后收集前 100 次提交的通过率触发一次微调。def cold_start_estimate(features: ProblemFeatures, predictor: DifficultyPredictor) - dict: 冷启动场景的难度估计 新题上线时先用模型预测一个初始值标记为 low_confidence。 收集到足够数据后≥ 100 次提交用实际通过率修正。 pred_score, confidence predictor.predict(features) if features.historical_pass_rate 0.0 and features.avg_solve_time_min 0.0: confidence min(confidence, 0.5) # 冷启动上限50% status cold_start else: status warm return { difficulty: pred_score, confidence: confidence, status: status, recommendation: ( 初始评估建议收集更多提交数据后重算 if status cold_start else 置信度达标可用于推荐系统 ) }五、总结精度、时效与冷启动的三角权衡难度预测系统的核心挑战不是选什么模型而是在精度、时效、冷启动三者之间做权衡历史数据越多 → 精度越高但对新题的响应最慢文本特征 → 即时可用但脱离真实用户反馈有偏差冷启动 渐进微调初始预测基于特征工程收集 100 次提交后触发重训三个关键指标MAE平均绝对误差≤ 0.8 分满分 10 分说明预测难度与真实难度偏差不到一个等级冷启动置信度≥ 0.3说明模型在无历史数据时至少有一个模糊但合理的估计重训延迟≤ 24 小时确保难度标签不会因为用户水平变化而严重过时这三点做到了才能让推荐引擎说出来的下一道题真正匹配用户的当前能力而非凭感觉拍出来的。