题目要求 给你一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。 你只能完成一次交易： 选择某一天买入一支股票 选择未来某一天卖出这支股票 返回能获得的最大利润。如果无法盈利，返回 0。 输入输出 输入：prices: List[int] 输出：最大利润 int 只能买一次、卖一次。 买入日必须早于卖出日。 可以选择不交易，此时利润是 0。 示例 输入：prices = [7,1,5,3,6,4] 输出：5 最优做法是在价格为 1 时买入，在价格为 6 时卖出，利润是 6 - 1 = 5。 输入：prices = [7,6,4,3,1] 输出：0 价格一直下降，任何买入后再卖出都会亏钱，所以返回 0。 约束 1 <= prices.length <= 10^5 0 <= prices[i] <= 10^4 Step 1：先固定买卖顺序 先看这个例子： prices = [7,1,5,3,6,4] 如果只看价格差，最大利润来自： 1 -> 6 profit = 5 这是合法的，因为价格 1 出现在价格 6 之前。 ...
LeetCode 55：跳跃游戏，用最远覆盖范围判断能否到达终点
题目要求 给你一个整数数组 nums。 你一开始站在下标 0。nums[i] 表示从位置 i 最多可以向右跳多少步。 题目要求判断：能不能到达最后一个下标。 输入输出 输入：nums: List[int] 输出：bool 从下标 0 出发。 每个位置的数字表示最大跳跃长度，不是必须跳这么远。 只需要判断能否到达最后一个下标，不需要返回具体路径。 示例 输入：nums = [2,3,1,1,4] 输出：true 一种跳法是： 0 -> 1 -> 4 从下标 0 可以跳到下标 1，再从下标 1 跳到最后一个下标。 输入：nums = [3,2,1,0,4] 输出：false 无论怎么跳，都会被下标 3 的 0 卡住，无法到达最后一个下标 4。 约束 1 <= nums.length <= 10^4 0 <= nums[i] <= 10^5 Step 1：不要先猜路径，先看覆盖范围 先看失败样例： nums = [3,2,1,0,4] 从下标 0 最多可以跳到下标 3。 看起来选择很多： 0 -> 1 0 -> 2 0 -> 3 当前 baseline 是： ...
LeetCode 200：岛屿数量，把网格陆地看成连通分量
题目要求 给你一个 m x n 的二维字符网格 grid： "1" 表示陆地 "0" 表示水 题目要求返回岛屿数量。 一个岛屿由水平或垂直相邻的陆地组成。对角线相邻不算连通。可以认为网格四周都被水包围。 输入输出 输入：grid: List[List[str]] 输出：岛屿数量 int 只看上下左右四个方向。 "0" 水格子不能算作岛屿的一部分。 示例 输入： [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1 这些陆地通过上下左右连成一整块，所以答案是 1。 输入： [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3 这里有三块互不连通的陆地，所以答案是 3。 约束 m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] 只会是 "0" 或 "1" 这一题可以用 DFS 或 BFS 做。这里的目标是练并查集：把每块陆地当成一个节点，把相邻陆地合并，最后留下的陆地连通分量数量就是岛屿数量。 ...
LeetCode 684：冗余连接，用 union 失败找到成环边
题目要求 题目给你一个无向图。这个图原本是一棵有 n 个节点的树，节点编号是 1..n，后来额外加了一条边。 树的定义是： 连通 没有环 加上一条额外边之后，图仍然连通，但会出现一个环。 现在给定边数组 edges，其中 edges[i] = [a, b] 表示节点 a 和节点 b 之间有一条无向边。题目要求返回一条可以删除的边，使剩下的图重新变成树。 如果有多个答案，返回在输入中最后出现的那条。 输入输出 输入：edges: List[List[int]] 输出：一条边 List[int] n == len(edges) 节点编号是 1..n 图中没有重复边 给定图是连通的 示例 输入：edges = [[1,2],[1,3],[2,3]] 输出：[2,3] 前两条边形成一棵树： 1 - 2 | 3 再加入 [2,3]，2 和 3 之间已经能通过 2 -> 1 -> 3 连通。现在再加直接边，就形成环。 输入：edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] 输出：[1,4] 加入 [1,4] 之前，1 和 4 已经能通过 1 -> 2 -> 3 -> 4 连通，所以 [1,4] 是冗余边。 ...
并查集模板：find / union / count 从零推导
副标题 / 摘要 并查集不是从 find 和 union 这两个函数名开始背。它要解决的问题是：怎样判断两个点是否已经属于同一个集合，并在看到一条连接关系时把两个集合合并。 预计阅读时长：10~12 分钟 标签：Hot100、并查集、Union-Find、DSU、图 SEO 关键词：并查集, Union-Find, DSU, find, union, count, 路径压缩 元描述：用 Python 从零推导并查集模板，讲清 parent、find、union、count、路径压缩和连通分量计数。 A — Algorithm（从集合合并压力开始） 小任务：不断合并集合，并回答连通性 假设有 5 个点： 0, 1, 2, 3, 4 一开始，每个点都是一个独立集合： {0}, {1}, {2}, {3}, {4} 现在依次发生两次合并： union(0, 1) union(1, 2) 我们想回答三个问题： 0 和 2 是否在同一个集合？ 3 和 4 是否在同一个集合？ 当前一共有几个集合？ 手工看答案是： {0, 1, 2}, {3}, {4} 所以： 0 和 2 在同一个集合 3 和 4 不在同一个集合 当前 count = 3 这就是并查集要解决的核心任务： ...
LeetCode 208：实现 Trie（前缀树）模板题解析
副标题 / 摘要 208 题的难点不在算法变化，而在把 Trie 模板按平台接口写稳：insert 建路径，search 查完整单词，startsWith 只查前缀路径。 预计阅读时长：8~10 分钟 标签：Hot100、Trie、前缀树、LeetCode 208 SEO 关键词：LeetCode 208, Implement Trie, Prefix Tree, startsWith 元描述：从接口要求出发实现 LeetCode 208，讲清 Trie 节点、children、is_end、insert/search/startsWith 的区别。 A — Algorithm（题目与算法） 先看最小操作压力 208 题最关键的操作序列是： Trie trie = new Trie() trie.insert("apple") trie.search("apple") -> true trie.search("app") -> false trie.startsWith("app") -> true trie.insert("app") trie.search("app") -> true 这个例子说明： app 可以是 apple 的前缀 但只有插入过 app 后，search("app") 才能返回 True 所以这题不是“路径存在就算命中”。 我们必须同时维护： 路径是否存在 这条路径是否刚好是完整单词 题目接口 设计一个 Trie，也叫前缀树，支持三个操作： ...
Trie 模板：从节点字段到插入查询 invariant
副标题 / 摘要 Trie 的重点不是背代码，而是理解“一个节点代表一个前缀”。只要这个模型稳定，插入、完整单词查询和前缀查询都会变成同一个循环。 预计阅读时长：8~10 分钟 标签：Hot100、Trie、前缀树、字典树 SEO 关键词：Trie, 前缀树, 字典树, children, is_end 元描述：用 Python 写一个最小 Trie 模板，讲清节点字段、children 走法、结束标记和循环 invariant。 A — Algorithm（从一个小任务开始） 小任务：同时回答完整单词和前缀 假设已经插入： app apple bat 现在要问： app 是不是完整单词？ ap 是不是某个单词的前缀？ apply 是否存在？ 这个小任务暴露了两个缺口： 只用哈希集合，可以快速判断完整单词，但不能自然回答前缀问题 只看路径存在，又会把 app 和 apple 的前缀关系混成一件事 Trie 要解决的就是：让很多字符串共享公共前缀，同时还能区分“前缀存在”和“完整单词存在”。 从压力反推要支持什么 我们先不管任何题目接口，只定义一个自己的模板： insert(word)：把一个单词插入 Trie search(word)：判断完整单词是否存在 starts_with(prefix)：判断是否存在以 prefix 开头的单词 最小结构图 插入 app 和 apple 后，结构可以想成： root └─ a └─ p └─ p [end] └─ l └─ e [end] 这里最重要的是： ...
Python Callable 类型标注：怎么描述一个 handler 函数？
Python Callable 类型标注：怎么描述一个 handler 函数？ 副标题： Callable[[dict[str, Any]], Any] 不是一个新类，而是在类型层面说明： 这个参数是一个“能被调用的对象”，它接收什么参数，返回什么结果。 标签： Python / 类型标注 / Callable / Type Alias / Pipeline 适读人群： 正在写回调、handler、pipeline step、插件机制的 Python 开发者 阅读时间： 6 min 背景：为什么 handler 类型看起来这么长？ 在 pipeline runner 里，经常会有这种 handler 表： handlers = { "prepare": prepare, "enrich": enrich, } 每个 handler 都接收同一个运行时上下文： def prepare(context: dict[str, Any]) -> dict[str, bool]: context["prepared"] = True return {"prepared": True} 如果直接给 handler 表写类型，会变成： from collections.abc import Callable, Mapping from typing import Any handlers: Mapping[str, Callable[[dict[str, Any]], Any]] 这一串不难，但读起来吵。它把“workflow name 到 workflow handler 的映射”写成了一段类型语法。 ...
Python 从 dict/list 原型到稳定接口：什么时候该整理类型？
Python 从 dict/list 原型到稳定接口：什么时候该整理类型？ 副标题： 验证想法时先用普通变量和 dict/list 跑通行为；模型稳定后，再把它们整理成函数参数、dataclass、helper 和类型标注。 标签： Python / 原型验证 / 类型标注 / 接口设计 / Pipeline 适读人群： 正在从脚本式代码过渡到可维护模块的 Python 开发者 阅读时间： 7 min 背景：为什么一开始不用把类型设计得很完整？ 写一个新功能时，经常会卡在这个问题上： 我应该一开始就写 dataclass、class、Mapping、Callable 吗？ 还是先用普通 dict/list 把行为跑通？ 答案不是固定的，但有一个很实用的判断： 模型还不确定时，先用 dict/list 验证行为； 模型稳定后，再把稳定的东西整理成接口。 这不是偷懒，而是在降低错误抽象的成本。 比如你想验证一个 graph pipeline runner，最早可以只写： graph_plans = { "parallel": { "prepare": (), "enrich": ("prepare",), "extract": ("prepare",), } } 这个变量一开始不是“最终架构”，只是为了回答一个问题： dependency map 能不能表达 prepare 之后 enrich 和 extract 同时 ready？ 如果这个问题都没验证清楚，提前设计完整类层次反而会遮住真正的行为压力。 第一阶段：用普通变量验证模型 最早的脚本里，很多东西看起来像“常量”： ...
Python 类型标注里为什么用 Mapping、Sequence 这类抽象接口？
Python 类型标注里为什么用 Mapping、Sequence 这类抽象接口？ 副标题： 当一个函数只读取配置，不修改调用方传入的字典时，用 Mapping 比直接写 dict 更能表达接口意图；同理，Iterable、Sequence 和 Callable 也在表达“我需要什么能力”。 标签： Python / 类型标注 / Mapping / Sequence / Callable / 接口设计 适读人群： 正在写 Python 配置对象、runner、pipeline、SDK 参数的开发者 阅读时间： 7 min 背景：为什么不是所有字典参数都写成 dict？ 写 Python 配置型代码时，经常会有这种参数： graph_plans = { "parallel": { "prepare": (), "enrich": ("prepare",), "extract": ("prepare",), } } 如果一个 runner 只是读取它： runner = GraphPipelineRunner(graph_plans=graph_plans, handlers=handlers) 那么类型标注可以写成： from collections.abc import Mapping def __init__( self, *, graph_plans: Mapping[str, Mapping[str, tuple[str, ...]]], handlers: Mapping[str, WorkflowHandler], ) -> None: ... 刚开始看会觉得复杂：为什么不直接写 dict？ ...