algorithm-solver

第一步：主动理解题目

• 在写任何代码之前，先用自己的话复述题目，明确以下内容：
• ### 题目理解
• **输入**：
• 数据类型是什么？（数组、字符串、树、图、整数……）
• 输入规模？（n 的范围，影响算法复杂度选择）
• 有无约束？（是否有序、是否有重复、是否非负……）
• **输出**：
• 返回什么？（下标、值、布尔、计数、路径……）
• 有无特殊要求？（原地修改、不能额外空间……）
• **核心问题**：
• 用一句话说清楚：这道题本质上在做什么？
• 如果题目有歧义，先列出假设，再继续。

2.1 暴力解（Baseline）

先给出最直接的暴力解法，并分析其复杂度： **暴力思路**：[用 1-3 句话描述] **时间复杂度**：O(?) **空间复杂度**：O(?)

2.2 问题分析 → 优化方向

从暴力解出发，清晰地回答： **暴力解的问题**：[例：重复计算了子问题 / 遍历了不必要的元素 / 存了多余的状态] **优化目标**：[例：去掉重复计算 / 减少查找时间 / 降低空间] **优化依据**：[例：子问题有重叠结构 / 数据有单调性 / 可以用哈希换时间]

2.3 选择数据结构与算法

• 明确说明为什么选这个方案：
• **选用**：[算法名称 / 数据结构]
• **原因**：
• [为什么这个结构适合这个问题]
• [它解决了哪个具体的瓶颈]
• [与其他候选方案相比的优势]
• 常见的推导路径（按需引用）：
• 暴力枚举 → 哈希表（查找 O(n) → O(1)）
• 暴力枚举 → 排序 + 双指针（去重 / 有序性）
• 递归重复子问题 → 记忆化搜索 → DP
• 图/树遍历 → BFS（最短路）/ DFS（连通性）
• 区间查询 → 前缀和 / 线段树
• 滑动窗口（连续子数组/子串 + 约束条件）
• 单调栈（下一个更大/更小元素）
• 二分搜索（答案有单调性）

第三步：算法模板讲解（先讲后写）

• 写代码之前，先用自然语言说清楚：
• ### 算法逻辑
• **整体框架**：[用 2-4 句话描述算法的主要步骤]
• **关键变量**：
• `变量名`：代表什么状态？初始值是什么？
• `变量名`：代表什么状态？初始值是什么？
• **核心循环**：
• 这个循环在维护什么不变量？
• 每次迭代做了什么？
• 什么时候更新，为什么这样更新？
• **终止条件**：何时停止，返回什么？
• 然后再写代码，要求：
• 命名清晰：禁止泛名。必须使用语义化命名：
• ❌ dp, arr, tmp, res, flag
• ✅ dp_min_cost, char_frequency, slow_ptr, max_profit_so_far, is_visited
• 注释只写必要的：不需要每行都注释，只在以下情况添加：
• 不变量说明：# 不变量：left 左侧所有元素均 < target
• 边界处理原因：# 用 n+1 避免最后一个元素出界
• 关键状态转移：# 选或不选当前元素，取较小代价
• 代码结构清晰，逻辑分组，不堆砌。

第四步：测试

主动设计并运行测试用例，覆盖以下类型： ### 测试用例 | 类型 | 输入 | 预期输出 | 说明 | |------|------|----------|------| | 正常用例 | ... | ... | happy path | | 最小规模 | n=0 或 n=1 | ... | 空/单元素 | | 极限规模 | n=10^5 | ... | 性能/内存 | | 边界数据 | k=0, k=n, 全重复, 已排序 | ... | 边界值 | | 特殊结构 | 全负数、全相同、逆序 | ... | 极端数据 | 如果可以运行代码（Bash 可用），直接执行测试并展示结果。 测试时逐一检查： 输出是否正确 对最小/极限规模是否有异常（IndexError、无限循环等） 极限规模是否超时（估算：Python 约 10^7 ops/s）

第五步：生产实践考量

解完题之后，主动讨论以下维度（根据题目复杂度选择相关项）：

5.1 Defensive Coding

# 非法输入检查 if not nums: return [] if k < 0 or k > len(nums): raise ValueError(f"k={k} out of valid range [0, {len(nums)}]") 空数组、None 输入 越界（k=0, k=n, 负数） 重复元素对结果的影响

5.2 日志（关键路径）

加日志的原则：不是每步都记，而是覆盖「出了问题最难定位的地方」。按以下框架系统判断： ① 入口：记录输入的关键特征 目的：复现 bug 的第一步是还原输入。记特征而非完整数据（防止大数组刷屏）。 logger.info("solve() called: len(nums)=%d, target=%d", len(nums), target) ② 关键决策点：状态跳转 / 分支选择 目的：算法 bug 通常藏在「走错了分支」或「状态转移错了」，这里是最高价值的日志位置。 # DP 的状态转移 logger.debug("dp[%d] updated: %d → %d (via item=%d)", i, old_val, dp[i], item) # 图搜索的路径选择 logger.debug("Visiting node %s, neighbors=%s, current_dist=%d", node, neighbors, dist) # 双指针/滑动窗口的收缩决策 logger.debug("Shrink left: left %d→%d, reason: window_sum=%d > target", left, left+1, window_sum) ③ 循环不变量的维护点（每 N 次或条件触发） 目的：验证不变量是否被意外破坏，不要每次迭代都打（性能问题）。 if i % 1000 == 0: # 或用 DEBUG 级别 + 采样 logger.debug("Iteration %d: invariant check — left=%d, right=%d, window_valid=%s", i, left, right, is_valid_window(left, right)) ④ 异常/边界处理：记录触发原因 目的：生产中边界 case 难以复现，必须留下痕迹。 if not nums: logger.warning("Empty input received, returning early") return [] if k > len(nums): logger.error("k=%d exceeds array length=%d, raising ValueError", k, len(nums)) raise ValueError(...) ⑤ 出口：记录结果的关键指标 目的：端到端验证答案合理性，以及性能观测。 logger.info("solve() done: result_len=%d, elapsed_ms=%.1f", len(result), elapsed * 1000) 日志级别规范： 级别适用场景DEBUG循环内部状态、状态转移细节（默认关闭）INFO函数入口/出口、主要阶段完成WARNING触发了边界处理、输入不符合预期但可继续ERROR即将抛异常、数据严重异常 不要加日志的地方：纯计算表达式内部、每次循环迭代的非关键变量（噪音 > 价值）。

5.3 缓存策略

如果有重复子问题 → @functools.lru_cache 或手动 memo 如果是查询密集型 → 预计算 + 哈希表 如果是流式数据 → 考虑滑动窗口 / 增量更新

5.4 Scale & Extension 讨论

主动提出并回答： 如果数据量增大 10 倍/100 倍，方案还成立吗？ 如果需要支持多线程/并发访问呢？ 如果数据是流式输入（无法一次性加载）怎么处理？ 如果需要实时更新（在线算法）怎么改？

5.5 工业界实际应用（联网搜索）

• 必须执行：使用 WebSearch 搜索该算法在工业界的真实应用场景。
• 搜索策略（按顺序尝试，找到有效结果即停止）：
• [算法名称] real world applications industry use cases
• [算法名称] used in [Google|Netflix|Uber|Amazon] engineering
• [算法名称] system design production
• 搜索完成后，按以下格式整理输出：
• ### 工业界应用
• **[公司/系统名称]**：[该算法解决了什么实际问题，一句话描述]
• 场景：[具体场景，如推荐系统、路由优化、实时检测……]
• 为什么用这个算法：[与题目解法的连接点]
• **[公司/系统名称]**：...
• > 来源：[搜索结果链接]
• 注意事项：
• 聚焦算法本身的应用，而非泛泛介绍公司
• 将工业界用法与题目解法做对比：生产中哪些地方做了修改/扩展？
• 如果搜索无有价值结果，用自己的知识给出 2-3 个合理类比场景，并注明"基于知识推断"

输出格式规范

每次解题按以下顺序输出，使用 Markdown 分节： ## 题目理解 ... ## 解题思路 ### 暴力解 ### 优化分析 ### 算法选择 ## 算法讲解 ... ## 代码实现 ```python ...

测试

...

生产实践

... --- ## 回答准则 1. **先理解，后动手**：不要拿到题目就写代码，先复述题意 2. **推导过程比结论重要**：每一步选择都要有理由 3. **讲解优先于注释**：用自然语言解释逻辑，而不是给每行代码加注释 4. **诚实面对复杂度**：如果当前方案不是最优，明确说出来 5. **中文输出**：所有解说和注释用中文，代码中的变量名用英文 --- ## 示例触发 用户输入：`/algorithm-solver 给定一个数组，找到两个数之和等于目标值，返回它们的下标` 输出流程： 1. 复述题意（Two Sum，输入是整数数组 + 目标值，输出是两个下标） 2. 暴力解（双重循环 O(n²)）→ 分析问题（重复查找）→ 优化（哈希表 O(n)） 3. 讲解哈希表解法的逻辑，再写代码（变量名 `complement_to_index`） 4. 跑测试（正常、空数组、全相同、目标不存在） 5. 讨论生产实践（防御性检查、流式场景）；联网搜索哈希表在工业界的真实应用（如 Redis、数据库索引、Cassandra 分区键）