每日练习与编程练习

我会把任务建模成带成本约束的在线最优停止任务，而不是简单二分类。目标函数可以写成最大化期望效用：E[Correct] - λ * E[GeneratedTokens] - μ * SLA_penalty，其中 λ 控制 token 成本，μ 控制延迟约束。在线动作至少包括 continue、stop、restart、escalate-to-stronger-model、summarize-and-continue。

离线阶段先收集历史完整推理轨迹。每条样本包含 prompt、每个 checkpoint 的前缀特征、最终是否正确、是否耗尽预算、最终 token 数、验证器打分等。checkpoint 不必每 token 取一次，可以按 128/256 token stride 或指数间隔采样。对每个前缀构造标签：1）当前停止是否能给出正确答案；2）继续到预算上限的成功概率；3）未来再生成 Δ token 的边际收益；4）是否属于非收敛轨迹，例如长循环、高困惑度震荡、答案反复翻转、验证器持续不通过。训练时不只训练一个分类器，而是训练校准后的风险模型：p_stop_correct(s_t)、p_eventual_success(s_t, b)、p_non_converge(s_t)、E[Δsuccess | Δtokens]。模型可以是轻量 GBDT/MLP，输入包括 token 数、剩余预算、熵均值/方差、top-k margin、重复 ngram 比例、语义相似度震荡、验证器分数趋势、答案候选稳定性、工具调用失败率等。输出必须做 isotonic/temperature calibration，并按任务类型、长度桶、模型版本分桶校准。

在线阶段在每个 checkpoint 做决策。给定状态 s_t 和剩余预算 b，估计几个动作的 Q 值： Q_stop = V * p_stop_correct(s_t) Q_continue(Δ) = V * p_eventual_success(s_t, b-Δ) - λΔ - μ latency_risk Q_restart = V * p_success_restart - λ * restart_cost Q_escalate = V * p_success_large_model - λ_large * cost - μ latency_risk 如果 Q_stop 最大且置信度超过阈值，就停止；如果 p_non_converge 高、边际收益 E[Δsuccess | Δtokens] 低于成本阈值，就早停或重启；如果当前练习难但仍有收益，则继续。阈值不能固定死，可以通过满足“正确率下降不超过 1%”的约束优化得到，例如在验证集上选择最激进但满足 recall of correct-trajectories ≥ 99% 的阈值。

多请求并发时可以做动态预算分配。每个请求在 checkpoint 上报“下一个 token block 的边际收益密度”：gain_i / cost_i。调度器在 GPU token budget 和 p95 latency 约束下，优先给边际收益高的请求分配下一个 block，边际收益低且非收敛概率高的请求进入 stop/restart/escalate 分支。这近似一个在线 knapsack。实现上用优先队列维护请求，复杂度 O(N log N) 每轮调度。

复杂度方面，若最大预算 B、checkpoint 间隔 S、特征维度 d，则单请求检测开销约 O((B/S) * d)，远小于解码 O(B * model_cost)。如果加验证器，验证器不应每步跑，可以只在候选答案变化、循环风险升高或关键里程碑时调用。批量调度复杂度约 O(R log R)，R 是活跃请求数。整体目标是让检测开销小于节省 token 成本的 5%。

风险控制上，最重要的是避免误杀正在收敛的长推理。做法包括：1）上线初期 shadow mode，只记录不干预；2）使用保守阈值，优先截断明显循环和验证器连续失败样本；3）对高价值请求使用 stop 后强验证，验证不过则继续或升级；4）对长练习、低资源语言、新练习型单独校准；5）监控 early-stop 后的用户改问率、人工评测正确率、token 节省率、p95 延迟、非收敛召回率、误停率。遇到数据漂移时，通过 PSI/KL 检测特征分布变化，自动回退到保守策略。

工程落地还要注意在线/离线一致性。离线训练不能用未来 token 特征；日志要精确记录 checkpoint 状态和动作；模型版本、prompt 模板、采样参数变化都要作为特征或分桶；KV cache 在 stop/restart/escalate 时要有清理策略；批量解码中请求提前停止后要做 batch compaction，避免 GPU 空洞。最终系统不是“看到像循环就停”的规则，而是一个经过校准的价值决策器，在正确率约束下最小化 token 和延迟成本。

参考解法使用“建父指针 + 从 target 开始 BFS”。二叉树本身只能从父到子走，但距离可以向上经过父结点，所以先用 DFS/BFS 记录每个结点的父结点，再把整棵树看成无向图，从 target 做层序遍历，走到第 k 层时收集答案。

python
from collections import deque
from typing import Optional, List, Dict, Set


class TreeNode:
    def __init__(self, val: int = 0,
                 left: Optional["TreeNode"] = None,
                 right: Optional["TreeNode"] = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        # 1. 建立每个结点到父结点的映射
        parent: Dict[TreeNode, Optional[TreeNode]] = {root: None}

        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                return
            if node.left:
                parent[node.left] = node
                dfs(node.left)
            if node.right:
                parent[node.right] = node
                dfs(node.right)

        dfs(root)

        # 2. 从 target 开始 BFS，把 left、right、parent 都看作相邻结点
        ans: List[int] = []
        queue = deque([(target, 0)])
        visited: Set[TreeNode] = {target}

        while queue:
            node, dist = queue.popleft()

            if dist == k:
                ans.append(node.val)
                # 已经到达距离 k，不能继续向外扩展，否则会超过 k
                continue

            for nxt in (node.left, node.right, parent.get(node)):
                if nxt is not None and nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, dist + 1))

        return ans