题目难度自动标注：用机器学习预测"这道题有多难"
一、为什么 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_len=text_feat["problem_len"], constraint_count=text_feat["constraint_count"], example_count=text_feat["example_count"], keyword_density=text_feat["keyword_density"], max_input_size=struct_feat["max_input_size"], variable_count=struct_feat["variable_count"], nesting_depth=struct_feat["nesting_depth"], data_structures=data_structures, algorithms=algorithms, historical_pass_rate=round(historical_pass_rate, 4), avg_solve_time_min=round(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, dtype=float) 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, dtype=float) # 分层采样划分训练/验证集（按难度分层） X_train, X_val, y_train, y_val = train_test_split( X, y, test_size=0.2, stratify=None, random_state=42 ) # LightGBM 训练 train_data = lgb.Dataset(X_train, label=y_train) val_data = lgb.Dataset(X_val, label=y_val, reference=train_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_round=n_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, dtype=float) X_train, X_val, y_train, y_val = train_test_split( X, y, test_size=0.2, random_state=42 ) self.model = GradientBoostingRegressor( learning_rate=lr, n_estimators=n_est, max_depth=max_d, random_state=42 ) 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 小时，确保难度标签不会因为用户水平变化而严重过时
这三点做到了，才能让推荐引擎说出来的"下一道题"真正匹配用户的当前能力，而非凭感觉拍出来的。
)
